# Problem in Cardinality and Order

Recently, I have read a Schaum's book. General Topology, and it introduced the concept of cardinality and order, but it points out something that I really don't understand.

1. If $A\preceq B$ and $B\preceq A$, then $A \sim B$.

If $X\supseteq Y\supseteq X_1$ and $X\sim X_1$, then $X\sim Y$

Prove these statements are equivalent which are both Schroeder-Berstein Theorem. In fact, I know how to prove them separately but is there a easy way to prove equivalent?

2.In the book, it mentions 'axiom of choice' a lot. So I search it from wiki and I found that it means: $$\forall X[\emptyset\notin X\Rightarrow \exists f:X\rightarrow\cup X \forall A\in X(f(A)\in A)]$$

It is quite easy to understand. But the book said this is equivalent to Zorn's Lemma:

Let $X$ be a non-empty partially ordered set in which every totally ordered subset has an upper bound. Then X contains at least one maximal element.

Wiki also mention that $\aleph_0$ is the smallest cardinality of a infinite set. This is directly derive from axiom of choice. Both of them I don't understand why.

3.Prove Law of trichotomy: Given any pair of set , either $A\prec B$ , $B\prec A$, or $A\sim B$. It said it can be proved ny using Zorn's Lemma.

• This is really too much for one question; you should split this into three or even four questions. I’ve answered the first one. You can find a proof that the axiom of choice implies Zorn’s lemma here and the easier proof of the converse here. There is a proof of trichotomy from Zorn’s lemma here. – Brian M. Scott Jun 29 '13 at 6:05
• @Brian is right. Although one can easily find all these questions (except for the first) on the site itself. So instead of asking more questions, you should find the others. – Asaf Karagila Jun 29 '13 at 9:02

These questions require fairly extensive answers; you should split them up and ask them separately. I’ll answer the first one here.

Assume that $A\prec B$ and $B\prec A$ imply $A\sim B$ for all sets $A$ and $B$, and suppose that $X\supseteq Y\supseteq X_1$, where $X\sim X_1$. Since $Y\subseteq X$, the identity map $\mathrm{id}_Y:Y\to X$ is an injection (one-to-one); to complete the proof, we must show that there is also an injection $g:X\to Y$. Since $X\sim X_1$, there is a bijection $h$ mapping $X$ onto $X_1$; in particular, $h:X\to X_1$ is then an injection (one-to-one). The identity map $\mathrm{id}_{X_1}:X_1\to Y$ is an injection, so the composition $\mathrm{id}_{X_1}\circ h:X\to Y$ is an injection, and we’re done: we set $g=\mathrm{id}_{X_1}\circ h$.

Now assume that if $X\supseteq Y\supseteq X_1$, and $X\sim X_1$, then $X\sim Y$, and suppose that $A\prec B$ and $B\prec A$. Then there are injections $f:A\to B$ and $g:B\to A$. Let $A_1=f[A]$; clearly $A_1\subseteq B$, and $A_1\sim A$. We can almost apply our assumption, but not quite, because $B$ isn’t (necessarily) a subset of $A$. But we can use $g$ to get the same effect: let $X_1=g[A_1]$ and $Y=g[B]$, and observe that $X_1\subseteq Y\subseteq A$ and $X_1\sim A_1\sim A$. Thus, $Y\sim A$, and since $Y\sim B$ (because $g$ is injective), we have $A\sim Y\sim B$, i.e., $A\sim B$.

Here is a list of answers to your questions, from this very site. You might a lot more if you open up Google and search. In either case, let me preface that understanding "why something happens" will usually require that you understand the mathematical theory in which the phenomenon takes place. If you have no experience with ordinals and transfinite recursion then you may find these proofs somewhat difficult and mysterious. If you don't understand the structure of cardinals very well, then you will find the fact that $\aleph_0$ is the minimum of the infinite cardinals strange. And so on.

2. $\aleph_0$ is the minimum of the infinite cardinals