Prove every subset of countable set is either finite or else countable

  • #1
zenterix
702
84
Homework Statement
Theorem: Every subset of a countable set is either finite or else countable.
Relevant Equations
The proof in the book I am reading is as follows
Let ##A## be a subset of a countable set. Assume ##A## is not finite; then it will be shown that ##A## is countable. An easy argument shows that one can assume without loss of generality that ##A## is a subset of ##\mathbb{N}##.

Now define a function ##f:\mathbb{N}\to A## inductively as follows:

##f(1)=## the least element of ##A## (that exists by the well-ordering principle)

and then if ##f(1),...,f(n)## have been defined, let ##f(n+1)## be the least element of ##A \backslash \{f(1),...,f(n)\}##. (The least element again exists by the well-ordering principle, and the fact that ##A## is not finite.) It is now left to the reader to verify that ##f## is one-to-one and onto. Thus, ##A## is equivalent to ##\mathbb{N}##.

There are a lot of steps left out of this proof. Here is my proof with hopefully all the steps. I would like to know if it is correct

Let ##A## be a countable set. Then ##A## is either finite or countably infinite.

Case 1: ##A## is finite.

There is a bijection ##f## from ##A## onto ##\{1,...,n\}##.

Let ##S\subseteq A##. Then ##g:S\to f(S)## is a bijection, and since every subset of ##\{1,...,n\}## is finite then ##S## is also finite.

Case 2: ##A## is countably infinite.

Since there is a bijection between ##A## and ##\mathbb{N}## (call it ##f##) then

Claim 1: there is a bijection between ##B\subseteq A## and a subset of ##\mathbb{N}##.

Proof 1: Define ##g:B\to f(B)## such that ##g(b)=f(b)## for ##b\in B## where ##f(B)\subseteq\mathbb{N}##. ##g## is a bijection (I won't prove this here so the post isn't too long). ##\blacksquare##

Here is the "easy argument" cited in the book's proof: if we show that every subset of ##\mathbb{N}## is countable then every ##B\subseteq A## is countable too because if there is a bijection ##f_1:f(B)\to\mathbb{N}## and a bijection ##f_2:B\to f(B)## (which we've already obtained above) then there is a bijection ##f_3:B\to\mathbb{N}## defined ##f_3=f_1\circ f_2##, and thus ##B## is countable.

Claim 2: Every subset of ##\mathbb{N}## is countable

Proof 2: Let ##S\subseteq\mathbb{N}##. If ##S## is finite then by definition it is countable.

If ##S## is infinite then consider the function ##f## defined inductively as follows

##S## has a least element (by well-ordering principle) ##s_1##. Define ##f(1)=s_1##.

Assume ##f(1), ..., f(n)## have been defined.

Define ##f(n+1)=## least element of ##S\backslash \{f(1),...,f(n)\}##

Claim 3: ##f## is a bijection from ##\mathbb{N}## onto ##S##

If we accept claim 3 then we have shown that ##S## is countably infinite, and thus countable and proof 2 is finished.

Proof 3: Suppose ##f(n_1)=f(n_2)##.

This means that the least element of ##S\backslash \{f(1),...,f(n_1-1)\}## equals the least element of ##S\backslash\{f(1),...,f(n_2-1)\}##.

Suppose ##n_1>n_2##. Then, the least element of ##S\backslash \{f(1),...,f(n_2), ...,f(n_1-1)\}## equals the least element of ##S\backslash\{f(1),...,f(n_2-1)\}=f(n_2)##.

Thus, ##f(n_2) \in S\backslash\{f(1),...,f(n_2)\}##.

But this contradicts the definition of a set difference.

Thus, by contradiction we have proved that ##n_1\leq n_2##.

With an analogous argument we can show that it cannot be that ##n_2>n_1## and so we can conclude that ##n_1=n_2##.

Thus ##f## is injective.

Now suppose ##n\in S##.

There are ##n-1## natural numbers smaller than ##n##.

Thus, there are at most ##n-1## natural numbers ##k## such that ##f(k)<n##.

Suppose there are ##m## such numbers.

Then ##f(m)=## least element of ##S\backslash \{f(1),...,f(m-1)\}##

and since ##\forall\ x\in S\backslash\{f(1),...,f(m-1)\}\implies x\geq n##

then ##f(m)=n##.

Thus ##f## is surjective.

Thus, ##f## is bijective. ##\blacksquare##
 
Physics news on Phys.org
  • #2
I don't think you need case 1. This is how I would start.

I think we need a name for the set. Let ##S## be a countable set and ##A \subseteq S##. It is enough to show that if ##A## is not finite, then ##A## is countable.

As ##S## is countable, there is a bijection ##f: S \to \mathbb N##. If we restrict ##f## to ##A##, then this is a bijection from ##A## to ##f(A)##, which is a subset of ##\mathbb N##. Note that ##A## is countable iff ##f(A)## is countable. [That, I suggest, is a separate proof, if necessary.] Therefore, it is enough to show that every subset of ##\mathbb N## is countable.
 

FAQ: Prove every subset of countable set is either finite or else countable

What does it mean for a set to be countable?

A set is countable if its elements can be put into one-to-one correspondence with the natural numbers, meaning there exists a bijective function between the set and the natural numbers. This implies that the set is either finite or has the same cardinality as the set of natural numbers.

How do we prove that every subset of a countable set is countable?

To prove that every subset of a countable set is countable, we can use the fact that if a set A is countable, there exists a surjective function from the natural numbers to A. For any subset B of A, we can restrict this surjective function to a subset of the natural numbers that maps onto B, showing that B is also countable.

Can a subset of a countable set be uncountable?

No, a subset of a countable set cannot be uncountable. By definition, any subset of a countable set must be either finite or countable. If a subset were uncountable, it would contradict the property of the original set being countable.

Why is it important to distinguish between finite and countable sets?

It is important to distinguish between finite and countable sets because they have different properties and implications in various areas of mathematics. Finite sets have a limited number of elements, while countable sets can be infinite but still have a structure that allows them to be enumerated or listed in a sequence. Understanding the distinction helps in analyzing problems and proving theorems related to set theory and other branches of mathematics.

What are some examples of countable and uncountable sets?

Examples of countable sets include the set of natural numbers (ℕ), the set of integers (ℤ), and the set of rational numbers (ℚ). Each of these sets can be listed in a sequence where each element corresponds to a natural number. Examples of uncountable sets include the set of real numbers (ℝ) and the set of points on a line segment. These sets cannot be put into one-to-one correspondence with the natural numbers due to their larger cardinality.

Similar threads

Replies
1
Views
1K
Replies
1
Views
951
Replies
5
Views
2K
Replies
3
Views
1K
Back
Top