# Follow up on “Proof of $X \times X \hookrightarrow X$ implies $[X]^2 \hookrightarrow X$”

This is a follow up on this earlier question of mine.

We have the following statements:

(HSO) For every infinite set $X$ there exists an injection $f: X \times X \hookrightarrow X$

(HSU) For every infinite set $X$ there exists an injection $f: [X]^2 \hookrightarrow X$

One can prove (HSO) $\rightarrow$ (HSU) as follows:

Assume (HSO). Since $h: X \to X \times X$, $x \mapsto (x,x)$ is an injection by (HSO) and Cantor-Schröder-Bernstein, $X \approx X \times X$ for every infinite set $X$. By a result of Tarski, the latter implies the Axiom of Choice. Once we have AC we can prove HSU as follows: let $f: X \times X \to X$ be an injection. For each unordered pair $\{x,y\}$ choose $g(\{x,y\})$ from the set $\{f((x,y)), f((y,x))\}$.

The following is an exercise I have been unable to solve:

Exercise 40: Find a simpler proof of the implication (HSO) $\rightarrow$ (HSU) in ZF.

Can someone help me solve this exercise? Thanks for your help.

-
Thanks for the upvote that reminded me of this question! – Rudy the Reindeer Jun 6 '13 at 5:20

Assume (HSO). Consider the following injection $\varphi:[X]^2\to X\times X$ defined by $\{x, y\} \mapsto (\text{min}\{x,y\}, \text{max}\{x,y\})$. Then using (HSO) we get an injection $f: X\times X \to X$. Since the composition of injections is an injection, the map $f\circ \varphi:[X]^2\to X$ is an injection, which proves (HSU).
Uhh, what's $\min\{x,y\}$? Is there some sort of linear order defined on $X$ that we were not aware of? – Asaf Karagila Jan 26 '15 at 17:35