Real Analysis: countably infinite subsets of infinite sets proof

  • #1

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.
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
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
795
7
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.
 

Related Threads on Real Analysis: countably infinite subsets of infinite sets proof

Replies
3
Views
10K
Replies
1
Views
3K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
5
Views
1K
  • Last Post
2
Replies
29
Views
8K
  • Last Post
Replies
9
Views
7K
  • Last Post
Replies
3
Views
980
Replies
11
Views
3K
Replies
5
Views
1K
Top