Need a hint for intro real analysis problem

In summary, the conversation discusses the proof of the statement "If |X| is infinite, then |N| <= |X| where N = natural numbers" and suggests using induction to define an injective function from N to X. The conversation also touches on the concept of bijections and infinite sets.
  • #1
andrassy
45
0
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?
 
Physics news on Phys.org
  • #2
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.
 
  • #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?
 
  • #4
andrassy said:
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,...}.
 

Related to Need a hint for intro real analysis problem

1. What is real analysis?

Real analysis is a branch of mathematics that deals with the study of real numbers, functions, and their properties. It involves the use of rigorous mathematical techniques to understand the behavior of these objects and their relationships.

2. What is an "intro" problem in real analysis?

An "intro" problem in real analysis is a problem that is meant to introduce students to the fundamental concepts and techniques of the subject. These problems are often simpler and more straightforward than advanced problems, and they serve as a stepping stone for students to build their understanding and problem-solving skills.

3. Why do students need hints for intro real analysis problems?

Intro real analysis problems can be challenging for students because they require a solid understanding of basic concepts and the ability to apply them in new and unfamiliar contexts. Hints can help students approach these problems in a structured and systematic way, guiding them towards the solution.

4. Are hints considered cheating in real analysis?

No, hints are not considered cheating in real analysis. In fact, many instructors and textbooks provide hints and solutions to problems as a way to support students' learning and understanding of the material. It is important for students to use hints as a learning tool rather than relying on them to simply get the answer.

5. How can I find hints for intro real analysis problems?

There are several ways to find hints for intro real analysis problems. You can ask your instructor or classmates for help, consult a textbook or online resources, or break down the problem into smaller parts and attempt to solve them individually. It is also helpful to review your notes and previous examples to see if there are any similar problems that can provide insight.

Similar threads

  • Calculus and Beyond Homework Help
Replies
14
Views
597
  • Calculus and Beyond Homework Help
Replies
1
Views
587
  • Calculus and Beyond Homework Help
Replies
3
Views
622
  • Calculus and Beyond Homework Help
Replies
11
Views
307
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
864
  • Calculus and Beyond Homework Help
Replies
3
Views
596
  • Calculus and Beyond Homework Help
Replies
1
Views
629
  • Calculus and Beyond Homework Help
Replies
13
Views
841
  • Calculus and Beyond Homework Help
Replies
1
Views
626
Back
Top