3
$\begingroup$

Proof:

Suppose $X$ and $Y$ are any infinite sets.

Then

$ \exists f:X \rightarrow X \text{ such that}\; f \;\text{ is injective }\;\land\; f(X) \neq X,\;\;\text{and}$ $\exists g:Y \rightarrow Y \text{ such that}\;\; g \text{ is injective}\;\;\land\;\;g(Y) \neq Y.$

I'm sure that it's simple, but I don't see what I should do after this.

  • 2
    Don't be afraid to use more words to make your argument; if you need to have a proof in mostly symbolic notation, you can translate to logical notation once you tackle the proof in words expressing what you need to express.2012-12-11

2 Answers 2

4

Since $X \subset X \cup Y$, the same injection $f$ demonstrating that $X$ is infinite can also be made to demonstrate that $X \cup Y$ is infinite.

For ease of notation, suppose $X$ and $Y$ are disjoint. (We won't count duplicates in the union, so this is a fair assumption.) Define $h : X \cup Y \rightarrow X \cup Y$ by $ h(z) = \begin{cases} f(z) & \text{ if } z \in X\\ z & \text { if } z \in Y \end{cases} $

Since $f$ is an injection, so is $h$. Now, $ h(X \cup Y) = h(X) \cup h(Y) = f(X) \cup Y \neq X \cup Y,$ where the inequality comes from the fact that $f(X) \neq X$.


If the assumption that $X$ and $Y$ are disjoint makes you uncomfortable, you can do without it by replacing $Y$ with $Y \setminus X$ in the definition of $h$ and throughout the proof.

  • 0
    AHA now I see your point. I was confused, in that first you assumed X,Y disjoint, and later added "replace$Y$by Y-X". So the map$h$is the identity only on Y-X, and your proof is, now that I get it, a lot simpler than the way I ended up doing it in my answer. +1.2012-12-11
0

Assume it is not true. Then there is a bijection with $(1, 2, ...., n)$ for some $n$ that counts all elements of the union. Then it (over-)counts all elements of, say, $X$. Then, for some $m, $(1, 2, ..., m)$ counts $X$, which is a contradiction.

  • 0
    Sure, but why do it complicated if it doesn't have to be? I would be surprised if as part of his class (or earlier in the book he learns this from, whatever it is) it was not proved that 'finite means not infinite,' so this is a complete answer. There is nothing in his question demanding to use a particular definition; just his solution attempt which I still find unnecessarily abstract and complicated.2012-12-11