Welcome to the first set theory post! I am going to discuss here some more advanced set theory topics than the one thought usually at the first year. However, we are going to give better foundation to math and discuss the most basic things. Before all of that, I want to start with something else, I want to define an Order on a set and start proving theorems realted to it, since it will help us in the future. Let’s begin!
Let be a set. A partial order on is a collection of ordered pairs with the following properties:
- Anti-reflexive: for everty .
- Transitivity: for every if then
If is a set, and is a partial order on , then is called Partially ordered set, or Poset.
If am going to write instead of . In addition, I am going to write instead of , and now the defenition makes more sense intuitivly, let’s write it again, but with the new symbols:
- for every
- if then .
Isn’t it a lot easier on the eyes? Let’s see some exapmles of posets:
- The sets are all posets with the ‘normal’ order , for example, in all the sets:
- Let be a set of sets, we can define the following order: if and only if .
- This one will be important later: Let be a set of functions, we say that if and . You can think of as an “extension” of .
Notice that if is a partial order, then it is also anti-symetric, i.e . Why? suppose that there are such that , and . By the second property of partial order (transitivity) we get which is a contradiction to the first property (anti-reflexive).
An order is said to be a Linear order / Total order, if you can ‘compare’ any two elementes. i.e. for any , or . However, recall that only one of them is true.
Linear order is stronger than just order, notice that there are orders where you just can’t compare two elements. For example, If we consider the second example, we can pick two sets, , according to the order there, we can’t compare them since none of them is a subset of the other.
Linear orders are really comfortable, I think it is pretty clear why, I mean, we will be happy to be able to compare two elements from a set in order to understand the elements and the set better. We will see more benefits of a linear order in this post and in the furture posts. Also. if you wonder why thry are called that way, think of a directed graph where each vertex represents an element of a set, and an edge represents the relation. The graph will look like a line
I think we are ready to prove a pretty interesting result now. I state that there is a subset of the power set such that , where equipped with the order from the second example, is lineraly orderd. This is kind of a tough statement to proof. Despite that, there is a really nice trick that solves the problem.
Recall that . thus, there is a bijection . This fact allows us to translate our problem to the raitonals. Now here comes the trick, for every real number consider the set of rationals: . That’s the set of rationals that are smaller than . It is not hard to see that if then . However, since the rationals are a dense set in the real numbers, there exits such that . This implies that , thus . From that we conclude that . We can now define the subset as the set . this set’s cardinality is cleary , while at the same time, is a subset of the power set .
Ok, let’s proceed. If is a poset, a subset is cofinal in if for every there exits such that or . You can think of the set as a dominant subset of , let’s give some exapmles:
- for every poset , itself is cofinal.
- The set of even numbers inside the natural numbers.
Just 2 more definitions:
- An element is called the First element of the poset, if or for every .
- An element is called the Last element of the poset, if or for every .
We are now ready to prove another statement: The set is cofinal if and only if is the last element.
First, assume that is cofinal. Let be an arbitrary element. By the definition of cofinal set, must be ‘smaller’ or equals one of the elements of the poset. However, This element has to be , thus, or .
On the other hand, suppose that is the last element, and pick any . will ‘do the job’, thus is cofinal.
I like this statement. In my opinion, it connects the last two definitons in an elegant way. Now I want to prove one last statement for this post, which is also pretty neat. Suppose that is a linearly ordered poset without last element, then, is cofinal if and only if is not bounded. Recall that a set is bounded if there exits such that or for each .
Suppose that is cofinal, while also being bounded. Then, there exits such that or for each . since is linearly ordered and doesn’t have last element, there is an element such that . Then for every which is a contradiction to the fact that is cofinal.
On the other hand, suppose that is not bounded and pick an arbitrary element . is not an upper bound of since the set is unbounded, therefore, there is some element such that or , and that completes the proof!
I think that this is enough for one post. In the next post I am going to discuss about order preserving maps between posets, that will help us identify if two given posets are the ‘same’.