Question

Challenge: Show that \(|\mathbb{R}|=|\mathcal{P}(\mathbb{N})| .\) (Hint: Use the Cantor-Schröder-Bernstein Theorem. To show that \(|\mathbb{R}| \leq|\mathcal{P}(\mathbb{N})|\), you might use function \(D: \mathbb{R} \rightarrow \mathcal{P}(\mathbb{Q})\) where for \(r \in \mathbb{R}, D(r)=\\{q \in Q: q

Short answer

\(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|\) using Cantor-Schröder-Bernstein with injections.

Step-by-step solution

Understand the Cantor-Schröder-Bernstein Theorem

The Cantor-Schröder-Bernstein Theorem states that if there exist injections (one-to-one functions) between two sets \(A\) and \(B\), then the two sets have the same cardinality, i.e., \(|A| = |B|\). To show \(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|\), we need to find an injection from \(\mathbb{R}\) to \(\mathcal{P}(\mathbb{N})\) and another from \(\mathcal{P}(\mathbb{N})\) to \(\mathbb{R}\).

Inject \(\mathbb{R}\) into \(\mathcal{P}(\mathbb{N})\)

Define a function \(D: \mathbb{R} \rightarrow \mathcal{P}(\mathbb{Q})\) where \(D(r) = \{q \in \mathbb{Q} : q < r\}\) for each \(r \in \mathbb{R}\). The set \(D(r)\) is a subset of the rationals. Since the rational numbers \(\mathbb{Q}\) are countable, \(\mathbb{Q} \subset \mathbb{N}\). Thus, \(D(r)\) is a subset of a countable set, implying \(D(r) \in \mathcal{P}(\mathbb{N})\). Since different real numbers define different sets, \(D\) is an injection.

Inject \(\mathcal{P}(\mathbb{N})\) into \(\mathbb{R}\)

To show the reverse injection, consider the bijection between \(\mathcal{P}(\mathbb{N})\) and binary sequences: each subset \(A \subseteq \mathbb{N}\) can be associated with a binary sequence where the \(n\)-th digit is \(1\) if \(n \in A\) and \(0\) otherwise. This binary sequence can represent a real number between 0 and 1. Thus, there is an injection from \(\mathcal{P}(\mathbb{N})\) into \([0, 1] \subseteq \mathbb{R}\), showing an injection from \(\mathcal{P}(\mathbb{N})\) to \(\mathbb{R}\).

Conclude with the Cantor-Schröder-Bernstein Theorem

Since there are injections from \(\mathbb{R}\) to \(\mathcal{P}(\mathbb{N})\) and from \(\mathcal{P}(\mathbb{N})\) to \(\mathbb{R}\), by the Cantor-Schröder-Bernstein Theorem, \(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|\).

Key concepts

Cardinality

Cardinality is a mathematical concept used to compare the size of sets. When we say two sets have the same cardinality, we mean there is a one-to-one correspondence between their elements. Essentially, one can create a perfect pair for each element in one set with exactly one element in the other set, ensuring no elements are left unmatched. In the context of infinite sets, different infinities can have different cardinalities.

• For finite sets, cardinality is simply the number of elements in the set.
• For infinite sets, cardinality requires a deeper understanding and often involves comparing sets using functions like injections.
• For example, the set of natural numbers \(\mathbb{N}\) and the set of integers \(\mathbb{Z}\) both have infinite elements but have the same cardinality because they can be matched perfectly with each other.

Understanding cardinality helps us explore the types of infinities in mathematics, as well as make comparisons between sets traditionally considered immeasurable, like \(\mathbb{R}\) and \(\mathcal{P}(\mathbb{N})\).

Injective Function

An injective function, also known as an injection, is a function that preserves distinctness. This means that each element in the function's domain (input set) is mapped to a unique element in its codomain (output set). An injective function ensures a one-to-one correspondence between elements of the domain and codomain

• If \(f: A \to B\) is injective, then whenever \(f(a_1) = f(a_2)\), it must follow that \(a_1 = a_2\).
• This property is crucial for demonstrating that two sets have the same cardinality according to the Cantor-Schröder-Bernstein Theorem.
• Injections do not require the entire codomain to be mapped, as long as no two distinct elements of the domain map to the same codomain element.

Injective functions are essential building blocks in set theory and help in structuring solutions for problems concerning correspondences between different sets.

Injection

In the realm of set theory, establishing an injection between two sets is a fundamental pathway to comparing their cardinalities. An injection creates a bridge where distinct elements from one set map uniquely to elements of another, preserving order and uniqueness.

• An injection between \(A\) and \(B\) implies that each element of \(A\) links to a distinct element of \(B\), but not necessarily every element of \(B\) needs to have a pre-image in \(A\).
• This concept is critical in proving equal cardinality between different sets, like in the Cantor-Schröder-Bernstein Theorem.
• For such proofs, injections help stabilize the idea of matching, ensuring no elements wastefully coalesce or drop.

Finding injections between sets can often involve creative approaches, like transforming subsets into binary sequences or using other mathematical tools. These strategies are what illuminate the path in major theorems and proofs within mathematics.