An alternative succinct proof needed for trivial cardinality fact

67 Views Asked by At

Let $|X|$ denote the cardinality of a set, i.e. the least ordinal $\alpha$ such that there is a bijection between X and $\alpha$. For any sets $X$ and $Y$ we write $X\preccurlyeq Y$ if the exists an injection from $X$ to $Y$ So it should be obvious that $$X\preccurlyeq Y \Leftrightarrow |X|\leq|Y|,$$ But I am having trouble showing this trivial fact in a neat succinct way. For the $(\Leftarrow)$ direction if $|X|\leq|Y|$, then as they are ordinals we have $|X|\subset|Y|$ or $|X|=|Y|$, so of course there is an injection from $|X|$ to $|Y|$ which can be composed with the bijections from $X$ to $|X|$ and $|Y|$ to $Y$, to get $X\preccurlyeq Y$. The $(\Rightarrow)$ is giving me problems, and can not see a simple way to show this trivial fact. The best I can come up with is to use a contradiction argument, which is very ugly. So then if we assume $|X|>|Y|$ then we have that $|Y|\subsetneq |X|$ and as these are cardinals there cannot be a bijection between $|X|$ and $|Y|$ as this would contradict the leastness of $|X|$, thus $|Y|\preccurlyeq |X|$, then composing with the bijections from $Y$ to $|Y|$ and $|X|$ to $X$, we have $Y\preccurlyeq X$, and with the premise (viz. $X\preccurlyeq Y$) which with then imply that there is a bijextion between $X$ and $Y$, and therefore $|X|=|Y|$-a contradiction. So anyone with a better laconic and neater proof of this trivial statement please can you show it to me, and if there is a mistake in my reasoning please correct me. Thanks in advance.

1

There are 1 best solutions below

2
On

Let $f_X\colon X\to\alpha_X$ be some bijection from $X$ to $|X|$, and similarly define $f_Y$.

Since $X\preccurlyeq Y$ we have some injection $g\colon X\to Y$. Therefore we have $f_Y\circ g\circ f_X^{-1}\colon\alpha_X\to\alpha_Y$ is an injection.

However the definition of a cardinal is an ordinal $\alpha$ such that there is no injection from $\alpha$ into any $\beta\in\alpha$ (note that if there is such injection, then there is a bijection, due to the Cantor-Bernstein theorem). Since $\alpha_X$ and $\alpha_Y$ are cardinals this means that $\alpha_X\leq\alpha_Y$.