3

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.

amWhy
  • 209,954
Bill
  • 31
  • 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. – amWhy Dec 11 '12 at 02:37

2 Answers2

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.

Austin Mohr
  • 25,662
  • 1
    If the definition of A infinite is the existence of a nonsurjective injection from A to A, then we need an injection from $X \cup Y$ to itself, which is not surjective. A map from $X$ to $X \cup Y$ diesn't precisely fit the definition, at least as cited above, that A be infinite. – coffeemath Dec 11 '12 at 02:39
  • 1
    Yes I was actually questioning exactly what coffeemath has said. Don't I need to show a map from $X \cup Y$ to $X \cup Y$ to prove that it is infinite? – Bill Dec 11 '12 at 02:40
  • 1
    You are both correct. Let me answer it a little more carefully. – Austin Mohr Dec 11 '12 at 02:41
  • Thanks for your answer, it's very helpful. I guess the only problem I'm having with this proof is that I don't understand why you defined h(z) like you did. This is the main thing that is holding me back from understanding infinite set proofs. Also, why do we know that h is an injection because f is an injection? – Bill Dec 11 '12 at 03:09
  • In the case where X and Y overlap, it may happen that the only x0 missed by f happens to be hit by g, and also the only y0 missed by g happens to be hit by f. even if you work with Y-X for the map g, there may yet be some y in Y-X which maps to x0 under g, thus making it all depend on y0 missed by g, but it still seems this y0 might be hit by f, since in case one splits X versus Y-X, one still uses f on all of X. (This snag led me to delete my too easy answer, maybe I'm missing something... – coffeemath Dec 11 '12 at 03:23
  • @Bill I defined $h$ in that way because I really just wanted to work with $f$ and didn't care much about $g$. So, I made a function that behaves as though it were $f$ for elements of $X$ and is just the identity for elements of $Y$. The only thing to be careful about is that $h$ is still an injection. – Austin Mohr Dec 11 '12 at 03:40
  • @coffeemath I don't make use of the function $g$ at all. In fact, my proof would work equally well if $Y$ was any set (even empty). Elements of $X$ get mapped back into $X$ (since that's how $f$ is defined) and elements of $Y$ get mapped to themselves (so they also stay in $Y$). Have I addressed your complaint? – Austin Mohr Dec 11 '12 at 03:42
  • @coffeemath If $X$ and $Y$ overlap, then I would have defined $h$ to be the identity only on $Y \setminus X$ and subsequently written $Y \setminus X$ in place of $Y$ throughout the proof. – Austin Mohr Dec 11 '12 at 04:07
  • 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. – coffeemath Dec 11 '12 at 04:13
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<n$, $(1, 2, ..., m)$ counts $X$, which is a contradiction.

gnometorule
  • 4,640
  • You are right, thanks. I edited what you rightly remarked out. – gnometorule Dec 11 '12 at 02:41
  • This is fine, but doesn't use the definition of infinite suggested in the OP, namely that A is infinite iff there is an injection from A to A which is not onto (not surjective). These are two equivalent definitions of finite/infinite distinction, namely finite iff bijection with 1...n and infinite iff injective map as above. – coffeemath Dec 11 '12 at 04:02
  • 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. – gnometorule Dec 11 '12 at 06:04