Prove that transitivity holds for "the cardinality of A does not exceed the cardinality of B".

800 Views Asked by At

Shen's Set Theory book claims that the transitivity holds for "the cardinality of $A$ does not exceed the cardinality of $B''$:

If the cardinality of $A$ does not exceed the cardinality of $B$ and the cardinality of $B$ does not exceed the cardinality of $C$, then the cardinality of $A$ does not exceed the cardinality of $C$. (Indeed, consider a one-to-one correspondence between $A$ and some $B' \subset B$, and another one-to-one correspondence between $B$ and some $C' \subset C$. The latter maps $B'$ onto some $C'' \subset C' \subset C$ (see Figure 1), and $C''$ has the same cardinality as $A$.)

enter image description here

Still I don't understand how $C''$ has the same cardinality as $A$. Perhaps the key point to prove is to show that if we remove $B-B'$ from $B$, also $C'-C''$ from $C'$ still the one-to-one correspondence or in-same-cardinality remains unchanged; but if so, how to prove that?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $f:A\to B'$ and $g:B\to C'$ be one-to-one correspondences. The claim is then that the function $h:A\to C''$ defined by $h(a)=g(f(a))$ is a one-to-one correspondence, where $C''=g(B')$. Note that it makes sense to write $h$ as a function $A\to C''$, since if $a\in A$ then $f(a)\in B'$ and so $h(a)=g(f(a))\in g(B')=C''$.

So we have to show $h$ is one-to-one and onto. To show it is one-to-one, suppose $h(a)=h(a')$. That means $g(f(a))=g(f(a'))$, so $f(a)=f(a')$ since $g$ is one-to-one. Since $f$ is one-to-one, this implies $a=a'$. Thus $h$ is one-to-one.

To show $h$ is onto, let $c\in C''$. By definition of $C''$, this means there exists $b\in B'$ such that $g(b)=c$. Since $f$ is onto, there exists $a\in A$ such that $b=f(a)$. Then $h(a)=g(f(a))=g(b)=c$. Thus $h$ is onto.