Question

Prove that every subset of \(\mathbb{N}\) is countable.

Short answer

Every subset of \( \mathbb{N} \) is countable because you can map its elements to \( \mathbb{N} \) in a bijection.

Step-by-step solution

Define Countability

A set is countable if there is a bijection between the set and a subset of the natural numbers \( \mathbb{N} \). A set is also considered countable if it is finite or if it has the same cardinality as \( \mathbb{N} \). This can include being either finite or countably infinite.

Understand the Subset Property

Every subset of \( \mathbb{N} \) either has a finite number of elements or is infinite. If the subset is finite, then it is countable by definition since any finite set is countable.

Establish Bijection for Infinite Subsets

If the subset is infinite, we can list its elements in increasing order, forming a sequence that maps to \( \mathbb{N} \). This is a key property of subsets of \( \mathbb{N} \)—they can be lined up as a sequence, which is a bijection to the subset of \( \mathbb{N} \).

Conclude with Countability Definition

Since you can either list the elements of a finite subset or line up the elements of an infinite subset of \( \mathbb{N} \) in increasing sequence to form a bijection with \( \mathbb{N} \), every subset of \( \mathbb{N} \) is countable. This aligns with our initial definition of a countable set.

Key concepts

Bijection

In mathematics, a bijection is a special kind of function that perfectly pairs up elements of two sets. Each element of the first set is paired with exactly one element of the second set, and vice versa. This means there are no leftovers or repeats. Think of it as assigning each person a unique locker at school—no two people have the same locker, and no locker is left unnamed. For a function to be bijective, it must be both injective and surjective. **Injective** means that no two different elements of the first set map to the same element in the second set. **Surjective** means that every element of the second set is the image of at least one element of the first set.
When proving that a set is countable, we often seek a bijection to establish a one-to-one correspondence with the natural numbers, which helps us understand the size of the set in a very natural way. This is why bijections are nearly synonymous with the concept of countability. If a set, finite or infinite, can be placed into a bijective relation with the natural numbers, it confirms the set is countable.

Subsets

Subsets are collections of elements taken from a larger set. In the context of natural numbers, any collection of specific numbers is considered a subset of the natural numbers, designated as \(\mathbb{N}\).
Understanding subsets is crucial when dealing with countability because any subset of \(\mathbb{N}\), no matter its size or composition, will always hold certain properties derived from \(\mathbb{N}\) itself. These properties help establish whether the subset is countable. A subset can be:

• **Finite**: This means the subset contains a limited number of elements. Any finite set is inherently countable because you can simply enumerate its elements in a list.
• **Infinite**: Infinite subsets, like the set of all even numbers, still follow a pattern or sequence that allows them to match every natural number without gaps or duplications.

The ability of infinite subsets of \(\mathbb{N}\) to be listed in an increasing sequence is the basis that allows infinite subsets to form bijections with \(\mathbb{N}\), therefore confirming their countability.

Cardinality

Cardinality refers to the "size" or number of elements within a set. It helps in comparing the sizes of different sets. For example, a set with elements \( \{1, 2, 3\} \) has a cardinality of 3. When discussing countability, cardinality is essential because it provides a simple measure to describe how many elements compose a set.

• A set with **finite cardinality** has a limited number of elements.
• When a set has the **same cardinality as** \(\mathbb{N}\), it is termed countably infinite. That means you can potentially list these sets' elements correspondingly with those of \(\mathbb{N}\).

The concept of cardinality becomes more intriguing when dealing with infinite sets, as it allows us to distinguish between different "sizes" of infinity through its logical structure. This means recognizing that some infinite sets, like \(\mathbb{N}\), can be directly matched with another, showing the same size in terms of one-to-one correspondence, while others cannot. Thus, understanding the cardinality and its relation to bijections is fundamental in proving countability structurally and comprehensively.