f 2a

Countable and Uncountable Sets

This section will deal with the concept of finite and infinite sets which were introduced in Section 3.1. This section will help attach some meaning to the size, or cardinality, of a set A when A is an infinite set.

Definition of a Bijection, Same Cardinality
For any nonempty sets A,B, the function f: A -> B is called a bijection, or one-to-one correspondence, if f is both one-to-one and onto.

Let A = ℤ⁺ and B = 2ℤ⁺ = {2k | k ∈ ℤ⁺} = {2,4,6,…}. The function f: A -> B, defined by f(x) = 2x is a bijection.
For a₁,a₂ ∈ A, then f(a₁) = f(a₂) => 2a₁ = 2a₂ => a₁ = a₂, and so f is one-to-one.
If b ∈ B, then b = 2a for some unique a ∈ A, and f(a) = 2a = b, and so f is onto.

When f: A -> B is a bijection, then A and B are denoted as A ~ B, where A and B have the same cardinality such that |A| = |B|.

From the previous example, it was shown that ℤ⁺ and 2ℤ⁺ both have the same size, even though it seemed like 2ℤ⁺ had fewer elements than ℤ⁺. This assumption is based on the fact that 2ℤ⁺ ⊂ ℤ⁺.

Instead, let g: B -> A denote another function, where A = ℤ⁺ and B = 2ℤ⁺ (only the order changed) and g is defined by g(2k) = k.
Then, g(2k₁) = g(2k₂) => k₁ = k₂ => 2k₁ = 2k₂, and so g is one-to-one.
Then, for each k ∈ A, then 2k ∈ B with g(2k) = k, and so g is also onto.
Therefore, g is a bijection and B ~ A.
Since the previous example showed the function f was a bijection, then A ~ B. Additionally, in this example, it was shown that, although B ⊂ A, it is also found that B ~ A.

The above two examples showed that, for the case of A = ℤ⁺ and B = 2ℤ⁺, then A ~ B and B ~ A. However, this is generally true for any case. This is because the function g in the previous example was actually the inverse function of f. Since a function is invertible if it is a bijection, then, if there are two nonempty sets A,B with A ~ B, then B ~ A. And it is not necessary for A = B for |A| = |B|.

For B = 2ℤ⁺ = {2k | k ∈ ℤ⁺} and C = 3ℤ⁺ = {3k | k ∈ ℤ⁺}, the function h: B -> C defined by h(2k) = 3k establishes a bijection between the sets B and C. Therefore, B ~ C, C ~ B, |B| = |C|.

Properties of Bijection
The following are some properties of bijection for any nonempty sets A,B,C:

1. A ~ A
2. If A ~ B, then B ~ A.
3. If A ~ B and B ~ C, then A ~ C.

Finite and Infinite Sets
Any set A is called a finite set if A = ∅ or if A ~ {1,2,3,…,n} for some n ∈ ℤ⁺. When A = ∅, then A has no elements, and so |A| = 0. When A ~ {1,2,3,…,n}, then |A| = n.

When a set A is not a finite set, then A is called an infinite set.

From this definition, it is seen that, if A is a nonempty finite set, then there is a bijection g: {1,2,3,…,n} -> A for some n ∈ ℤ⁺. This function g provides a listing of elements of A as g(1), g(2), g(3), …, g(n), which is a listing that can be counted.

When A is an infinite set, it can be seen there is no n ∈ ℤ⁺ such that the function g: A -> {1,2,3,…,n} is a bijection. But, if A and B are infinite sets, and A ⋂ B, then |A| = |B|, then there is a bijection between A and B, and so A ~ B, B ~ A.

Countable Sets
A set A is a countable, or denumerable, set if A is finite or A ~ ℤ⁺.

The previous examples show that 2ℤ⁺ ~ ℤ⁺ and 3ℤ⁺  ~ ℤ⁺. Since ℤ⁺ ~ ℤ⁺, then the sets ℤ⁺, 2ℤ⁺, and 3ℤ⁺ are all countable sets. In fact, for all k ∈ ℤ, k ≠ 0, the function f: ℤ⁺ -> kℤ⁺ defined as f(x) = kx is a bijection, and so kℤ⁺ is a countable set, where |kℤ⁺| = |ℤ⁺|.

Generally, if A is an infinite set and A ~ ℤ⁺, then ℤ⁺ ~ A, and so there is a bijection f: ℤ⁺ -> A that provides a listing of elements of A as f(1), f(2), …, and in this way, the elements of A can be counted but never finished in counting.

Therefore, an infinite set A is a countably infinite if either the bijection f: A -> ℤ⁺ exists or the bijection g: ℤ⁺ -> A exists.

Let A = {1,½,1/3,¼,…} = {1/n | n ∈ ℤ⁺}. The function f: ℤ⁺ -> A defined by f(n) = 1/n establishes a bijection between ℤ⁺ and A, and so |ℤ⁺| = |A| and A is countable.

Although all of the previous examples of countably infinite sets have been subsets of ℤ, other countably infinite sets are possible.

Finite and Infinite Sequences
For n ∈ ℤ⁺, a finite sequence of n terms is a function f with domain (1,2,3,…,n}. This sequence is usually written as an ordered set {x₁,x₂,x₃,…,xn}, where xᵢ = f(i) for all 1 ≤ i ≤ n.

An infinite sequence is a function g with ℤ⁺ as its domain. This type of sequence is denoted by the ordered set {x₁,x₂,x₃,…}, or {xᵢ}ᵢ∈ℤ⁺, where xᵢ = g(i) for all i ∈ ℤ⁺.

The set {1,½,¼,1/8,1/16} can be thought of as a finite sequence given by the function f: A -> ℚ⁺, where A = {1,2,3,4,5} and f(n) = 2-n+1.

The above example, where A = {1,½,1/3,¼,…} = {1/n | n ∈ ℤ⁺} can also be expressed as an infinite sequence {1/n}n∈ℤ⁺ given by the function g: ℤ⁺ -> ℚ⁺, where g(n) = 1/n for each n ∈ ℤ⁺.

For sequences, the terms do not have to be distinct. For instance, let f: ℤ⁺ -> ℤ, where xn = f(n) = (-1)n + 1, for each positive integer n. Then the infinite sequence is {xn}n∈ℤ⁺ = {x₁,x₂,x₃,x₄,…} = {1,-1,1,-1,1,…}, but the range of f is only the two element set {1,-1}.

If A is a nonempty countable set, then A can be written as a sequence of distinct elements.

If A is finite, then A ~ {1,2,3,…,n} and {1,2,3,…,n} ~ A for some n ∈ ℤ⁺. Therefore, f: {1,2,3,…,n} -> A is a bijection. Then let aᵢ = f(i) for each 1 ≤ i ≤ n. Since f is a bijection, then {a₁,a₂,a₃,…,an} is a sequence of n distinct elements of A.

If A is a countably infinite set, then either f: ℤ⁺ -> A or  g: A -> ℤ⁺ is a bijection. Let aᵢ = g(i) for all i ∈ ℤ⁺. Since g is a bijection, the elements {a₁,a₂,a₃,…} are distinct elements and A = {a₁,a₂,a₃,…}.

The infinite sequence {a₁,a₂,a₃,…} = {aᵢ}ᵢ∈ℤ⁺ is a subsequence of ℤ⁺ if for all i ∈ ℤ⁺, aᵢ ∈ ℤ⁺ and aᵢ < ai+1.

Let {xn}n∈ℤ⁺ and {yn}n∈ℤ⁺ be two infinite sequences. Then {yn}n∈ℤ⁺ is a subsequence of {xn}n∈ℤ⁺ if there exists a subsequence {ak}k∈ℤ⁺ of ℤ⁺, when for each k ∈ ℤ⁺, yk = xak.

{1,3,5,7,…} is a subsequence of ℤ⁺, where it can be given by the function f: ℤ⁺ -> ℤ⁺ where an = f(n) = 2n – 1.

For n ∈ ℤ⁺, let xn = 1/n and let yn = 1/(3n). Then {xn}n∈ℤ⁺ = {1,½,1/3,¼,…} and {yn}n∈ℤ⁺ = {1/3,1/6,1/9,…}. Consider the subsequence {ak}k∈ℤ⁺ of ℤ⁺ where ak = 3k for each k ∈ ℤ⁺. Then for all n ∈ ℤ⁺, yn = 1/(3n) = x₃n = xan, and so  {yn}n∈ℤ⁺ is a subsequence of {xn}n∈ℤ⁺.

Infinite Countable Sets and Subsets
If S is an infinite countable set, and A ⊆ S, then A is a countable set no matter the set A.

Uncountable Sets
Up to this point, it seemed as though every infinite set has turned out to be countable.

However, dealing with the infinite set of real numbers ℝ, not only is ℝ uncountable, but even (0,1] in ℝ is also uncountable.

To prove that the set (0,1] = {x | x ∈ ℝ ᴧ 0 < x ≤ 1} is not a countable set, assume the set (0,1] is countable, such that f: ℤ⁺ -> (0,1] is a bijection. Then the set can be written in an infinite sequence of distinct terms, where for every i ∈ ℤ⁺, rᵢ is a real number: (0,1] = {r₁,r₂,r₃,…} = {rn}n∈ℤ⁺. To avoid repeats, it is agreed that every real number rᵢ is written in decimal form such that 0.5 becomes 0.499…, so that no decimal expansion ends. Writing such decimal expansions for real numbers r₁, r₂, r₃, …, yields the following:
r₁ = 0.a₁₁a₁₂a₁₃a₁₄…
r₂ = 0.a₂₁a₂₂a₂₃a₂₄…
r₃ = 0.a₃₁a₃₂a₃₃a₃₄…

rn = 0.an1an2an3an4

where aᵢj ∈ {0,1,2,3,…,8,9} for all i,j ∈ ℤ⁺.
Consider the real number r = 0.b₁b₂b₃…, where, for each k ∈ ℤ⁺, r is constructed as follows:

Note that 2 and 3 are randomly chosen integers.
Then r ∈ (0,1). However, for every k ∈ ℤ⁺, r ≠ rk, because their nth digits differ, and so r ∉ {r₁,r₂,r₃,…}, which results in a contradiction, because it was assumed that the interval (0,1] was inside the countable infinite sequence {r₁,r₂,r₃,…}. Therefore, the interval (0,1] is uncountable.

Therefore, when a set is not uncountable, it is called uncountable. When a set A is uncountable, then ℤ⁺ and A do not have the same cardinality, and so A ≁ ℤ⁺. The cardinality of A is then greater than the cardinality of ℤ⁺, where |ℤ⁺| < |A|, despite both A and ℤ⁺ being infinite sets.

Additionally, it can happen where the subset of a uncountable set is countable, such as ℤ ⊆ ℝ. However, if the subset A is uncountable, and A ⊆ B, then B is uncountable as well, such as (0,1] ⊆ ℝ. Therefore, ℝ is uncountable.

Recall that an infinite set is countable if there either exists the bijection f: A -> ℤ⁺ or g: ℤ⁺ -> A. However, for uncountable sets, the roles of A and ℤ⁺  of f cannot be reversed. If there is a one-to-one function f: ℤ⁺ -> A, the set A is uncountable, such as f: ℤ⁺ -> ℝ. Therefore, |ℤ| < |ℝ|.

To prove that the set of positive rational numbers ℚ⁺ is a countable infinite set, where ℚ⁺ ~ ℤ⁺ and |ℚ⁺| = |ℤ⁺|, and f: ℤ⁺ -> ℚ⁺ or g: ℚ⁺ -> ℤ⁺ is a bijection, then a bijection of ℚ⁺ and ℤ⁺ needs to be created, where all of the elements in ℚ must be considered.
Begin by considering all of the positive rational numbers of the form x/y for some x,y ∈ ℤ⁺. Then the following table displays how every single positive rational number is included in a sequence using the arrows as direction of ordering:

The fractions that are circled and crossed out are skipped and not included in the sequence set, because they have already been included in the list.
Therefore, the set of positive rational numbers can have each of its distinct numbers listed as an infinite sequence {1,2,½,1/3,3,4,3/2,2/3,…}, which creates a countable set. Therefore, ℚ⁺ is countable.

Additionally, to show that the set ℚ is countable, the infinite sequence created from the set of positive rational number ℚ⁺ is taken and every negative number is placed beside its corresponding positive number to account for every negative of every positive rational number. Therefore, ℚ is countable, and so f: ℤ⁺ -> ℚ is a bijection.

The following proof is to show that, if A is any set, then |A| < |℘(A)|.

To prove that if A is any set, |A| < |℘(A)|, consider two cases of the set A, where A is an empty set or A is a nonempty set.
For A = ∅, then the cardinality of A is |∅| = 0. The power set of A is then ℘(A) = {∅}. And so the cardinality of ℘(A) is |{∅}| = 1. Hence, |A| < |℘(A)| holds true so far.
For A ≠ ∅, let f: A -> ℘(A) be defined by f(a) = {a} for each a ∈ A. Since the function f is one-to-one, |A| = |f(A)| ≤ |℘(A)|.
To show that |A| ≠ |℘(A)|, it remains to be proven that there is no function g: A -> ℘(A) that is onto.
Let g: A -> ℘(A) and B = {a | a ∈ A ᴧ a ∉ g(a)}, and so B = g(a). There is an element a inside A such that it is not in the range of g(a), and so g(a) = B ⊆ A.
Since B ∈ ℘(A), then if g is an onto function, there must exist an element a’ ∈ A such that g(a’) = B. However, when a’ ∈ g(a’) = B, then from the definition of B, a’ ∉ g(a’), which forms a contradiction that a’ ∈ g(a’) and a’ ∉ g(a’). When a’ ∈ g(a’), then a’ ∈ B, but B = g(a’). This is a contradiction.
Therefore, there is no such a’ ∈ A where g(a’) = B, and so the function g cannot be onto. Hence, |A| ≠ |℘(A)|, yet |A| < |℘(A)|.

Sizes of Infinity
As a consequence to the above proof, it is found that there is no infinite cardinal number that is the largest, where if A is any finite set, then |A| < |℘(A)| < |℘(℘(A))| < …

However, the smallest cardinal number for countably infinite sets is the size of ℤ, ℤ⁺, ℚ, or any set A, such that the function f: ℤ⁺ -> A is a bijection. This smallest infinity is denoted as א‎₀, read as, “aleph zero,” where א‎₀ = |ℤ|, |ℤ⁺|, |ℚ|, |A|, where f: ℤ⁺ -> A is a bijection or |ℤ⁺| = |A|.

Additionally, the next larger cardinality for uncountable sets, such as ℝ, is denoted as א‎₁, or c for continuum.

Therefore, for any countably infinite set A,  |A| = |ℤ| = |ℤ⁺| = |ℚ| = א‎₀ is the smallest infinity for a cardinality to be.

PDF reference: 887

Page A-32. Question 1.

a) true
b) false, the subset (1,2] in ℝ⁺ is uncountable, and therefore ℝ⁺ is uncountable.
d) true
e) false, let A = ℤ ⋃ (0,1] and B = ℤ ⋃ (1,2]. A and B are uncountable sets, yet A ⋂ B = ℤ, which is a countable set.
f) true
g) false, let A = ℤ⁺ ⋃ (0,1] and B = (0,1]. A and B are uncountable sets, yet A ⧹ B = {2,3,4,…} is  a countable set.