Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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).

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.