9
$\begingroup$

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.

  • 1
    Thanks for the upvote that reminded me of this question!2013-06-06

1 Answers 1

0

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

  • 0
    Uhh, what's $\min\{x,y\}$? Is there some sort of linear order defined on $X$ that we were not aware of?2015-01-26