# What does $X \times \{0\}$ and $Y \times \{1\}$ mean in this proof?

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.

Thank!

$$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|.$