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.

  • 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.2012-12-11
  • 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?2012-12-11
  • 1
    You are both correct. Let me answer it a little more carefully.2012-12-11
  • 0
    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?2012-12-11
  • 0
    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...2012-12-11
  • 0
    @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.2012-12-11
  • 0
    @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?2012-12-11
  • 0
    @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.2012-12-11
  • 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

  • 0
    You are right, thanks. I edited what you rightly remarked out.2012-12-11
  • 0
    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.2012-12-11
  • 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