Proof $$f:X \to Y$$ and $$g:Y \to X$$ be injections. We may assume that $X$ and $Y$ are disjoint

Discussion: If $X$ and $Y$ are not disjoint, we can replace $X$ with $X \times \{0\}$ and $Y$ with $Y \times \{1\}$. The existence of a bijection $$g: X \times \{0\} \iff Y \times \{1\}$$

clearly implies the existence of a bijection from $X$ to $Y$.

What does the notation $X \times \{0\}$ and $Y \times \{1\}$ mean in this proof? Why does this imply bijection?

There are more in this proof, which is part of the Schroder Bernstein Theorem proof. I just need to understand the part above.



$$A \times B = \{(a,b) : a \in A, b \in B\}.$$

This is called the Cartesian product. For example $$\{a,b,c\} \times \{0,1\} = \{(a,0),(b,0),(c,0),(a,1),(b,1),(c,1)\}$$

In the context of the proof, this is replacing an element $x$ of $X$ with the element $(x,0)$ of $X \times \{0\}$ (this is a bijection! you can go backwards by taking $(x,0)$ to $x$). Note that $X \times \{0\}$ and $Y \times \{1\}$ are disjoint because the first only contains elements of the form $(\text{something},0)$ and the second only contains elements of the form $(\text{something},1)$ and you cannot have $(\text{something},0) = (\text{something},1)$ because $0 \ne 1$.


The notations are cartesian products. For instance $X\times \{0\}$ is the cartesian product of $X$ and $\{0\},$ i.e. the set of all ordered pairs $\langle x,y\rangle$ where $x\in X$ and $y\in \{0\}.$ Since there is only one possible value for $y$ in this case, $X\times\{0\}$ is the set of all pairs $\langle x,0\rangle$ where $x\in X.$

Since $X'= X\times\{0\}$ has the same cardinality as $X$ and $Y'=Y\times\{1\}$ has the same cardinality as $Y,$ and regardless of what $X$ and $Y$ are, $X'$ and $Y'$ are disjoint, this shows that you can find two disjoint sets with cardinality $|X|$ and $|Y|.$


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.