Set Theory- Introduction & Orders

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!

Posets

Let $A$ be a set. A partial order on $A$ is a collection of ordered pairs $R\subseteq A\times A$ with the following properties:

Anti-reflexive: $(a,a)\notin R$ for everty $a\in A$ .
Transitivity: for every $a,b,c\in R$ if $(a,b)\in R,(b,c)\in R$ then $(a,c)\in R$

If $A$ is a set, and $R$ is a partial order on $A$ , then $\langle A,R \rangle$ is called Partially ordered set, or Poset.

If am going to write $aRb$ instead of $(a,b)\in R$ . In addition, I am going to write $"<"$ instead of $R$ , and now the defenition makes more sense intuitivly, let’s write it again, but with the new symbols:

$a\nless a$ for every $a\in A$
if $a<b, b<c$ then $a<c$ .

Isn’t it a lot easier on the eyes? Let’s see some exapmles of posets:

The sets $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ are all posets with the ‘normal’ order , for example, in all the sets: $1<2, 2<3,\dots$
Let $A$ be a set of sets, we can define the following order: $A<B$ if and only if $A\subsetneq B$ .
This one will be important later: Let $A$ be a set of functions, we say that $f<g$ if $\text{dom}(f)\subsetneq \text{dom}(g)$ and $g|_{\text{dom}(f)}=f$ . You can think of $g$ as an “extension” of $f$ .

Notice that if $R$ is a partial order, then it is also anti-symetric, i.e $(a,b)\in R \Rightarrow (b,a) \notin R$ . Why? suppose that there are $a,b\in R$ such that $(a,b)\in R$ , and $(b,a)\in R$ . By the second property of partial order (transitivity) we get $(a,a)\in R$ which is a contradiction to the first property (anti-reflexive).

An order $R$ is said to be a Linear order / Total order, if you can ‘compare’ any two elementes. i.e. for any $a,b\in A$ , $(a,b)\in R$ or $(b,a)\in R$ . 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, $A=\{1,2,3\},B=\{2,3,4\}$ , 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 $A$ of the power set $P(\mathbb{N})$ such that $|A|=\aleph$ , where $A$ 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 $|\mathbb{N}|=|\mathbb{Q}|=\aleph_0$ . thus, there is a bijection $f:\mathbb{N}\to\mathbb{Q}$ . This fact allows us to translate our problem to the raitonals. Now here comes the trick, for every real number $a\in\mathbb{R}$ consider the set of rationals: $B_a=\{x\in\mathbb{Q}|x<a\}$ . That’s the set of rationals that are smaller than $a$ . It is not hard to see that if $a<b$ then $B_a\subseteq B_b$ . However, since the rationals are a dense set in the real numbers, there exits $q\in\mathbb{Q}$ such that $a<q<b$ . This implies that $q\in B_b\setminus B_a$ , thus $B_a\subsetneq B_b$ . From that we conclude that $f^{-1}(B_a)\subsetneq f^{-1}(B_b)$ . We can now define the subset $A$ as the set $A=\{B_a|a\in\mathbb{R}\}$ . this set’s cardinality is cleary $\aleph$ , while at the same time, is a subset of the power set $P(\mathbb{N})$ .

Ok, let’s proceed. If $\langle A,<\rangle$ is a poset, a subset $B\subset A$ is cofinal in $A$ if for every $a\in A$ there exits $b\in B$ such that $a<b$ or $a = b$ . You can think of the set $B$ as a dominant subset of $A$ , let’s give some exapmles:

for every poset $A$ , $A$ itself is cofinal.
The set of even numbers inside the natural numbers.
$\{\mathbb{N}\} \subset P(\mathbb{N})$

Just 2 more definitions:

An element $a\in A$ is called the First element of the poset, if $a<b$ or $a=b$ for every $b\in A$ .
An element $a\in A$ is called the Last element of the poset, if $a>b$ or $a=b$ for every $b\in A$ .

We are now ready to prove another statement: The set $\{a\}$ is cofinal if and only if $a$ is the last element.

First, assume that $\{a\}$ is cofinal. Let $b\in A$ be an arbitrary element. By the definition of cofinal set, $b$ must be ‘smaller’ or equals one of the elements of the poset. However, This element has to be $a$ , thus, $a>b$ or $a=b$ .

On the other hand, suppose that $a$ is the last element, and pick any $b\in A$ . $a\in\{a\}$ will ‘do the job’, thus $\{a\}$ 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 $\langle A,<\rangle$ is a linearly ordered poset without last element, then, $B\subset A$ is cofinal if and only if $B$ is not bounded. Recall that a set is bounded if there exits $a\in A$ such that $a> b$ or $a=b$ for each $b\in B$ .

Suppose that $B$ is cofinal, while also being bounded. Then, there exits $a\in A$ such that $a> b$ or $a=b$ for each $b\in B$ . since $A$ is linearly ordered and doesn’t have last element, there is an element $c\in A$ such that $a < c$ . Then $b <c$ for every $b\in B$ which is a contradiction to the fact that $B$ is cofinal.

On the other hand, suppose that $B$ is not bounded and pick an arbitrary element $a\in A$ . $a$ is not an upper bound of $B$ since the set is unbounded, therefore, there is some element $b\in B$ such that $b > a$ or $b = a$ , 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’.

Set Theory- Introduction & Orders

Posets

Like this:

Leave a Reply Cancel reply

Posets

Share

Like this:

Leave a Reply Cancel reply