1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need a hint for intro real analysis problem

  1. Jan 27, 2009 #1
    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.

    1. The problem statement, all variables and given/known dataProve: If |X| is infinite, then |N| <= |X| where N = natural numbers

    3. The attempt at a solutionI 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?
     
  2. jcsd
  3. Jan 28, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Jan 28, 2009 #3
    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?
     
  5. Jan 28, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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,...}.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Need a hint for intro real analysis problem
  1. Intro to Real Analysis (Replies: 4)

  2. Intro to real analysis (Replies: 1)

Loading...