Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 2:37

2 Answers 2

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.

share|improve this answer
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 2: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 2:40
1  
You are both correct. Let me answer it a little more carefully. –  Austin Mohr Dec 11 '12 at 2: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 3: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 3:23

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.

share|improve this answer
    
You are right, thanks. I edited what you rightly remarked out. –  gnometorule Dec 11 '12 at 2: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 4: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 6:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.