The question defines the '$\le$' operation on the cardinality of arbitrary sets A, and B as follows:
Let $\mathcal F$ be defined as the family of all injections from subsets of A onto B. Since $\mathcal F$ can be considered a family of subsets of the cartesian product of A and B, $A \times B$, it can be partially ordered by inclusion. Applying Zorn's Lemma, we conclude that $\mathcal F$ has a maximal element, $\mathcal f$. If the domain of $\mathcal f$ is A, then $card\,A \le card\,B$. The reason I believe it was defined this way was to show that '$\le$' is a linear ordering. I am not sure if that proof is necessary to solve this question. But that proof can be accessed here: Applying Zorn's lemma in the proposition about cardinality of sets.
It goes on to show that if $card\,A \le card\,B$ and $card\,B \le card\,A$, then $card\,A = card\,B$. The question asks to complete the proof. This is how it goes:
Let $f: A \to B$ and $g: B \to A$ be injections.
If $a \in A \cap rng\,g$, we have $g^{-1}(a) \in B$.
If $g^{-1}(a) \in rng\,f$, we have $f^{-1}(g^{-1}(a)) \in A$.
The process is to continue indefinitely or till it terminates with an element in $A$ \ rng $g$ or $B$ \ rng $f$. The three cases become disjoint sets $A_{\infty}, \, A_A, \, A_B$ whose union is A. Similarly, B can be decomposed into $B_{\infty}, \, B_B, \, B_A$.
It states that f maps $A_{\infty}$ onto $B_{\infty}$ and $A_A\,onto\,B_A$ and g maps $B_B\,onto\,A_B$.
- How exactly does this mapping work? It intuitively makes sense but I have not been able to put something concrete down.
If we define $h: A \to B$ by $h(a) = f(a)$ if $a \in A_{\infty} \cup A_A$ and $h(a) = g^{-1}(a)$ if $a \in A_B$, we find that h is injective. The question ends there.
-
I have an idea of how to show that h is surjective. If $b \in B_{\infty}$ then $b \in B \cap rng\,f$ and $f^{-1}(b) \in A$. Since the process has to continue indefinitely, $f^{-1}(b) \in rng\,g$. Thus, $f^{-1}(b) \in A \cap rng\,g$, meaning that $g^{-1}(f^{-1}(b)) \in B$ and so on. Thus, $f^{-1}(b)$ is in $A_{\infty}$. A similar argument can be used to show that if $b \in B_B$, then there exists $f^{-1}(b) \in A_B$ and if $b \in B_A$ then there exists $f^{-1}(b) \in A_A$. All of these pre-images would satisfy the condition of h (due to its injectivity I presume) and thus, h is surjective. I ask for help in making this proof more rigorous.
-
Even if h has been proven to both be surjective and injective, how does that show the equality of the cardinalities of the sets? I checked the question and equality was not defined for cardinality. Is there some trivial notion of equality I could apply here that I could link to my proof of subjectivity and injectivity and that would not be circular in nature? Is this the right way to go? If it was, why couldn't I use the fact that we had two injective functions from one set to the other to prove the equality instead?
-
If it is necessary to do so, how can I link this proof with the ordering, '$\le$'? I have not mentioned it once in the proof and that worries me.
Best Answer
The whole point of the proof of the Cantor-Bernstein Theorem (the statement that if there is an injection $f\colon A\to B$ and an injection $g\colon B\to A$, then there is a bijection $h\colon A\to B$) is to prove that the relation $\leq$ among cardinalities is a partial order. You don't know that ahead of time.
Say two sets $A$ and $B$ are equipollent, denoted $A\approx B$, if and only if there is a bijection between $A$ and $B$. It is easy to verify this is an equivalence relation. Now define the relation $\preceq$ on sets by saying that $A\preceq B$ if and only if there is an injective function $f\colon A\to B$. It is easy to show that:
The point of the statement you are trying to prove is to show that
This will prove that $\preceq$ is a (partial) order among the equipollency equivalence classes of sets.
The page you linked to is irrelevant to these facts. Instead, it proves that, assuming the Axiom of Choice, the relation $\preceq$ is a total relation among sets. Together with the fact that $\preceq$ is a partial order on equipollency equivalence classes, it will show that $\preceq$ is a total order on those equivalence classes. (In fact, this statement, known as Bernstein's Theorem, is equivalent to the Axiom of Choice.)
You want to prove that if $A\preceq B$ and $B\preceq A$, then $A\approx B$. Because we are assuming $A\preceq B$, there is an injective function $f\colon A\to B$. Because we are assuming $B\preceq A$, then there is an injective function $g\colon B\to A$. The existence of these functions comes directly from the definition of $\preceq$.
You have partitioned $A$ into three sets: $A_{\infty}$, $A_A$, and $A_B$. You have likewise partitioned $B$ into $B_{\infty}$, $B_A$, and $B_B$.
Note that because of how they are defined, if $a\in A_{\infty}$, then $f(a)\in B_{\infty}$. If $a\in A_A$, then $f(a)\in B_A$; and if $a\in B_B$, theN $f(b)\in B_B$. Similarly, if $b\in B_{\infty}$ then $g(b)\in A_{\infty}$; if $b\in B_A$, then $g(b)\in A_A$; and if $b\in B_{B}$, then $g(b)\in A_B$.
Moreover, because every element in $B_A$ lies in $\mathrm{range}(f)$, it follows that $f(A_A)=B_A$: we saw above that $f(A_A)\subseteq B_A$; and that if $f(a)\in B_A$ then $a\in A_A$, so $B_A=B_A\cap\mathrm{range}(f)=f(A_A)$. A symmetric argument shows that $g(B_B)=A_B$. Likewise, if $b\in B_{\infty}$, then $b$ lies in $\mathrm{range}(f)$ and must be the image of an element of $A_{\infty}$, so $f(A_{\infty})=B_{\infty}$. That addresses your point 1.
For point 2, that $h$ is surjective follows from the fact that $B_A$, $B_B$, and $B_{\infty}$ form a partition of $B$. Given any $y\in B$, if $y\in B_A$, then $y\in f(A_A)$, so there exists $a\in A_A$ with $f(a)=y$. Then $h(a)=y$ by definition of $h$. If $y\in B_{\infty}$, then there exists $a\in A_{\infty}$ such that $f(a)=y$, and then $h(a)=y$ by the definition of $h$. Finally, if $y\in B_B$, then $g(y)\in A_B$, and $h(g(y)) = y$ by the way that $h$ is defined. Thus, $h$ is surjective.
For point 3: since $h$ is both injective and surjective, then it is bijective. Therefore, $A\approx B$, since "$\approx$" means "there is a bijection between them.
Now, we define "two sets have the same cardinality" to mean, precisely, "there is a bijection between them". That is, $\mathrm{card}(A)=\mathrm{card}(B)$ is shorthand for $A\approx B$ ($A$ is equipollent to $B$), which is shorthand for "there is a bijection between $A$ and $B$). So once you prove that there is a bijection between two sets, you are proving that they have the same cardinality, because that is what "have the same cardinality" means: that there is a bijection between the two sets. That's point 3.
For point 4, you don't know that $\leq$ is an ordering (among equipollence equivalence classes). So you shouldn't use it until you prove Cantor-Bernstein; so of course you are not using that it is an ordering: you are trying to prove that it is one.