3
$\begingroup$

Consider the following two statements (where $[X]^2$ denotes the set of all unordered two-element subsets of $X$):

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

The following is an exercise from a book I'm currently reading:

enter image description here

So I thought I could argue as follows: We know that there are more ordered pairs ($|X|^2$) than unordered pairs (${|X| \choose 2}$), hence there exists an injection $i: [X]^2 \hookrightarrow X \times X$ hence $f \circ i$ is an injection $[X]^2 \hookrightarrow X$. But since the exercise is rated uber-difficult, this argument must be flawed. Can you tell me what's wrong with it? Thanks a lot.

1 Answers 1

2

More and less are not well-defined without the axiom of choice. Does more mean injection from one side or a surjection from the other? What does less mean?

Clearly there is a surjection from ordered pairs onto unordered pairs, but it does not have to be reversible. Indeed without the axiom of choice it is consistent that such counterexamples exist.

The existence of an injection from unordered pairs into ordered pairs requires you to choose an ordering for each unordered pair. This, of course, is not provably possible. Of course, if you assume that there is an injection from $X\times X$ into $X$ then you can prove that the axiom of choice holds and therefore the surjection has an injective inverse, but that would probably miss the point.

  • 0
    :-) it's a nice exercise. I'll have to think about it a bit myself.2012-12-01