Every countably infinite set has a countably infinite set

• k3k3
In summary, the proof shows that every infinite set contains a countably infinite set. This is done by defining a mapping f from the natural numbers to the infinite set A, and showing that this mapping is both one-to-one and onto. Therefore, A must contain a countable subset.
k3k3

Homework Statement

Show that every infinite set contains a countably infinite set.

The Attempt at a Solution

Let A be an infinite set

Since A is infinite and not empty, there exists an a∈A
Let f be a mapping such that for all n in ℕ such that f(n)=$a_{n}$ for some $a_{n}$.

Then f(1)=$a_{1}$. A is an infinite set, so there exists another element $a_{2}$ that is not $a_{1}$ such that f(2)=$a_{2}$ and so on.

This makes f a 1-1 function.

Since every element of ℕhas an image, the subset generated by f is onto ℕ.

Therefore, since f creates a subset of A, infinite subsets have a countable subset.

--
Is this a valid proof on why infinite sets have a countably infinite subset?

Yes, it is. I would rephrases some of the sentences, but in spirit it's correct.

1. What does it mean for a set to be "countably infinite"?

A set is countably infinite if it has the same number of elements as the set of natural numbers (1, 2, 3, ...). This means that the elements in the set can be put into a one-to-one correspondence with the natural numbers.

2. How is it possible for every countably infinite set to have a countably infinite set?

This is a result of Cantor's diagonal argument, which states that given any countably infinite set, it is always possible to construct another countably infinite set that is not in a one-to-one correspondence with the original set.

3. Can you give an example of a countably infinite set?

The set of even numbers (2, 4, 6, ...) is a countably infinite set, as it can be put into a one-to-one correspondence with the set of natural numbers by multiplying each natural number by 2.

4. What are some applications of this theorem?

This theorem has applications in various areas of mathematics, such as set theory, number theory, and topology. It also has practical applications in computer science and data analysis, as it allows for efficient organization and manipulation of large data sets.

5. Is it possible for an uncountably infinite set to have a countably infinite subset?

No, this is not possible. If a set is uncountably infinite, it means that it has more elements than the set of natural numbers, and therefore it cannot have a subset that is countably infinite.

• Calculus and Beyond Homework Help
Replies
1
Views
739
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
532
• Calculus and Beyond Homework Help
Replies
6
Views
2K
• Calculus and Beyond Homework Help
Replies
18
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
• General Math
Replies
15
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
654
• Calculus and Beyond Homework Help
Replies
4
Views
2K