Real Analysis: countably infinite subsets of infinite sets proof

In summary, to prove that every infinite subset contains a countably infinite subset, we can use a proof by cases. If the subset is countably infinite, it already contains a countably infinite subset. If the subset is uncountably infinite, we can use the Axiom of Choice to choose a distinct element from each natural number, creating a one-to-one correspondence with a subset of S. This subset is then countably infinite, proving that S contains a countably infinite subset. However, the use of the Axiom of Choice may be necessary, as it is not possible to prove this without it.
  • #1
TeenieBopper
29
0

Homework Statement


Prove that every infinite subset contains a countably infinite subset.


Homework Equations





The Attempt at a Solution



Right now, I'm working on a proof by cases.

Let S be an infinite subset.

Case 1: If S is countably infinite, because the set S is a subset of itself, it contains a countably infinite subset.

Case 2: If S is uncountably infinite...


And this is where I'm stuck. I know it's true (the Reals contains the Integers, the power set of the Reals still contains the Integers, etc) I've done some other searching online, and I keep seeing references to the Axiom of Choice used to prove this; we haven't talked about it in class, so I'd like to avoid this if at all possible, since if I use it, I'd have to prove that too.
 
Physics news on Phys.org
  • #2
I don't think you can prove it without the axiom of choice, which allows you to build a set by making an infinite number of choices. You don't prove the axiom of choice. That's why it is an axiom. There are consistent models of set theory with and without it.

If you assume the axiom of choice, the proof should be pretty straightforward. For each [itex]n \in \mathbb{N}[/itex], choose a distinct element [itex]x_n \in S[/itex], so that [itex]x_n \neq x_m[/itex] if [itex]n \neq m[/itex]. Suppose this were impossible for some [itex]n[/itex]. What would that imply about [itex]S[/itex]?
 
  • #3
TeenieBopper said:
And this is where I'm stuck. I know it's true (the Reals contains the Integers, the power set of the Reals still contains the Integers, etc) I've done some other searching online, and I keep seeing references to the Axiom of Choice used to prove this; we haven't talked about it in class, so I'd like to avoid this if at all possible, since if I use it, I'd have to prove that too.

It's puzzling that you'd be asked to prove this before you've seen the Axiom of Choice.
 
  • #4
I'm not exactly sure what you're asking; if it's impossible to choose an x_n for some n, doesn't that mean S is finite?


Does this work?

Case 2: S is uncountably infinite.

Let n ε Z+. For each n, choose on distinct element s_n ε S. This establishes a one to one correspondence between Z+ and a subset of S. Because Z+ is countably infinite, this subset is countably infinite. Thus, S has a countably infinite subset.
 

FAQ: Real Analysis: countably infinite subsets of infinite sets proof

What is Real Analysis?

Real Analysis is a branch of mathematics that deals with the study of real numbers and the functions and properties associated with them.

What is a countably infinite subset?

A countably infinite subset is a subset of a set that can be put into a one-to-one correspondence with the set of natural numbers, meaning that the elements can be counted and listed.

What is an infinite set proof?

An infinite set proof is a mathematical proof that shows a set has an infinite number of elements. In Real Analysis, this often involves showing a countably infinite subset within an infinite set.

How do you prove the existence of a countably infinite subset in an infinite set?

To prove the existence of a countably infinite subset in an infinite set, one can use a method known as "Cantor's diagonalization argument." This involves constructing a list of elements in the infinite set and showing that there is always an element missing from the list, thereby proving that the set is larger than the list and must be infinite.

What are some real-world applications of Real Analysis and proofs involving infinite sets?

Real Analysis and proofs involving infinite sets have many real-world applications, especially in fields such as physics, engineering, and computer science. For example, they can be used to model and analyze continuous systems, such as electric circuits, heat flow, and fluid dynamics. They are also crucial in the development of algorithms and data structures used in computer science.

Back
Top