2
$\begingroup$

I am almost finished with this proof, but I am having some trouble.

$\#$ denotes cardinality, and the sets are arbitrary, so finite or infinite.

First, I know that since there is a bijection between $A$ and $C$, there is an injection between those sets as well. Also, we have the identity functions $I(a)=a \in A \subseteq B$, and $I(b)=b \in B \subseteq C$ and since the identity function is bijetive, there is an injection between the sets $A$ and $B$, and the sets $B$, and $C$.

I am trying to prove that there is also an injection from $B$ to $A$ or $C$ to $A$ to invoke the Schroeder-Bernstein theorem and declare a bijection between those two sets, finally proving that the cardinality of $A$, $B$, and $C$ is equal. I am having trouble with this last part though. Could you give me some help please? Thank you! :)

UPDATE:

Because $A \subseteq B$, we have the identity function $I(a)=a∈A⊆B∴I(a)=a∈B$. The identity function is injective. Thus, there is an injection between A and B. Similarly, we use this same argument with an identity function $I(b)=b∈B⊆C∴I(b)=b∈C$. Thus, there is an injection between B and C. By definition of an injection, the elements of the domain might be equal to those in the range if it is also a bijection, and less than the elements of the domain if it is not. Thus, because these injections exist, $\#A≤\#B≤\#C∴\#A≤\#C$, but, by definition, because there exists a bijection from A to C, $\#A=\#C$, so $\#A=\#B=\#C$.

$\endgroup$
2
$\begingroup$

Good work so far, now to finish: There is a bijection $C\to A;$ resitrict it to $B$ to get an injection $B\to A.$

$\endgroup$
  • $\begingroup$ So if we have a bijection between the sets $A$ and $C$, that means that the bijection goes both ways right? (From $A$ to $C$ and from $C$ to $A$). Also, why can I restrict it to $B$? $\endgroup$ – The Bosco Mar 6 '17 at 12:45
  • $\begingroup$ Yes, a bijection $f\colon A\to C$ has an inverse function $f^{-1}\colon C\to A,$ given by $f(a)\mapsto a$ for all $a\in A$ (this definition makes sense precisely because $f$ is bijective), and $f^{-1}$ is also a bijection. By "restrict it to $B$" I mean "consider the function $g\colon B\to A$ given by $b\mapsto f^{-1}(b)$" (note that $b\in B\subseteq C$ so $f^{-1}(b)$ is defined). It's up to you to prove that this $g$ is injective. $\endgroup$ – Will R Mar 6 '17 at 12:56
  • $\begingroup$ So can I just take a composition of functions, such as: $h: C \to B$ and $g: B\to A$, and $f^{-1} = g(h(c)): C \to A$, and because $h$ has to be injective for the composition to be injective, then $h$ is injective. Is this what you mean? $\endgroup$ – The Bosco Mar 6 '17 at 13:03
  • $\begingroup$ I don't understand what you are trying to prove there. $\endgroup$ – Will R Mar 6 '17 at 13:19
  • $\begingroup$ Can I say that the function $f^{-1}=g \circ h$? Thus, because $f^{-1}$ is a bijection, it is also an injection. And, in composition of functions, only $g$ has to be injective for $g \circ h = f^{-1}$ to be injective. $\endgroup$ – The Bosco Mar 6 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.