Need a hint for intro real analysis problem

[andrassy]

Im just starting real analysis and trying to get my mind to start thinking the right way to do these kind of proofs. Any hints would be appreciated.

Homework Statement

Prove: If |X| is infinite, then |N| <= |X| where N = natural numbers

The Attempt at a Solution

I figure you can start by saying Let |X| be infinite. Then there does not exist any bijective function f: X -> {1,..,n} for any n. And I understand that |N| <= |X| means that there exists an injective function that maps N to X and that N is infinite. But I am having trouble bridging these. Any advice?

 

[Dick]

Use induction to define the injection f. X is nonempty so pick an x1 and define f(1)=x1. If X didn't have any more elements, then f would be a bijection. So you can find an x2!=x1 and define f(2)=x2. Etc, etc.

 

[andrassy]

I'm not quite sure I underhand how to execute the proof using this method. I also have not really learned how to do induction well yet, Here is what I have:

Suppose |X| is infinite. We construct a function f: N -> X. Because |X| is infinite, X is not empty.
Using induction: For n=1, f(1)=x1 is a unique element in X.
Inductive assumption: There is a unique element in X for every element in N: Suppose, for n=k, f(k)=xk. Suppose this were the last element in X, then the function f would be a bijection. But we know that since N is infinite, there does not exist any bijection f: N -> {1,...,n} for any n. Thus, there is a contradiction, so xk cannot be the last element. Then, when n = k+1, f(k+1)=xk+1 is a unique element in X. The inductive assumption is therefore true. Since there exists a unique element in X for every element in N, f: N->X is injective. Therefore, by definition, |N| <= |X|.

Does this look okay?

 

[Dick]

I'm not quite sure I underhand how to execute the proof using this method. I also have not really learned how to do induction well yet, Here is what I have:

Suppose |X| is infinite. We construct a function f: N -> X. Because |X| is infinite, X is not empty.
Using induction: For n=1, f(1)=x1 is a unique element in X.
Inductive assumption: There is a unique element in X for every element in N: Suppose, for n=k, f(k)=xk. Suppose this were the last element in X, then the function f would be a bijection. But we know that since N is infinite, there does not exist any bijection f: N -> {1,...,n} for any n. Thus, there is a contradiction, so xk cannot be the last element. Then, when n = k+1, f(k+1)=xk+1 is a unique element in X. The inductive assumption is therefore true. Since there exists a unique element in X for every element in N, f: N->X is injective. Therefore, by definition, |N| <= |X|.

Does this look okay?

Sort of. How about phrasing the inductive step more like this? If {x1,...,xk} is sequence of k distinct elements in X, then there exists an x_k+1 in X which is not equal to any of the x1,...,xk. (The argument is as you gave it). So there exists a sequence of k+1 distinct elements in X. Induction then shows there is an infinite sequence of distinct elements in X, {x1,x2,...}.