Problem 11 - Analysis Now

Question

Let \(X\) be a set and \(\mathscr{S}(X)\) the family of all subsets of \(X\). Show that the cardinality of the set \(\mathscr{S}(X)\) is strictly larger than that of \(X\), cf. E 1.1.6. Hint: If \(f: X \rightarrow \mathscr{S}(X)\) is a bijective function, set $$ A=\\{x \in X \mid x \notin f(x)\\} $$ and take \(y=f^{-1}(A)\). Either possibility \(y \in A\) or \(y \notin A\) will lead to a contradiction.

Step-by-Step Solution

Answer

The cardinality of \(\mathscr{S}(X)\) is strictly larger than that of \(X\).

Step 1: Understanding Injective Functions

To show that the cardinality of \(\mathscr{S}(X)\) is strictly larger than that of \(X\), we first assume, for contradiction, the existence of a bijective function \(f: X \rightarrow \mathscr{S}(X)\). This means for each element in \(X\), there is a unique subset of \(X\), and vice versa.

Step 2: Defining Set A

Consider the set \(A = \{ x \in X \mid x otin f(x) \}\). This set consists of all elements in \(X\) that are not included in their corresponding subset as defined by the function \(f\).

Step 3: Using Inverse Function

Let \(y = f^{-1}(A)\). Since the function \(f\) is bijective, \(f^{-1}\) must exist and map \(A\) back to some element \(y\) in \(X\).

Step 4: Checking the Contradiction

The element \(y\) must either belong or not belong to the set \(A\). If \(y \in A\), by the definition of \(A\), it must be that \(y otin f(y) = A\), which is a contradiction. Conversely, if \(y otin A\), then by the definition of \(A\), we must have \(y \in f(y)\), implying that \(y otin A\), again leading to a contradiction.

Step 5: Conclusion

Given that both scenarios lead to a contradiction, our initial assumption that a bijective function \(f: X \rightarrow \mathscr{S}(X)\) exists must be false. Therefore, there can be no bijection, and the cardinality of \(\mathscr{S}(X)\) must be strictly larger than the cardinality of \(X\).

Key Concepts

Cardinality

Cardinality is a concept in set theory that relates to the size of a set. It tells us how many elements are in a set. For finite sets, this is simple counting, but for infinite sets, cardinality helps us understand how one infinite set compares in size to another. This is often done using bijective functions.
The cardinality of set \( \mathscr{S}(X) \), which is the power set of a given set \(X\), is larger than the cardinality of \(X\). The power set \( \mathscr{S}(X) \) includes all subsets of \(X\), which implies there's a larger quantity of subsets than there are elements in the original set.
This illustrates an important principle: for any set, its power set is exponentially larger than the set itself, even if the original set is infinite.

Bijective Function

A bijective function is a crucial concept in understanding the relationship between two sets. It's a function that pairs every element in one set uniquely with an element in another set. This means:

• Injective (One-to-One): Different elements in the domain map to different elements in the codomain.
• Surjective (Onto): Every element in the codomain is mapped by at least one element in the domain.

If a bijective function exists between two sets, those sets have the same cardinality. However, in the exercise, we assumed such a bijection between \(X\) and \(\mathscr{S}(X)\) to reach a contradiction, showing that no such bijection can actually exist, affirming that \(\mathscr{S}(X)\) has greater cardinality than \(X\).

Subset

In set theory, a subset includes all elements from another set, but not necessarily all of them. If set \( A \) is a subset of set \( B \), every member of \( A \) is also a member of \( B \). Denoted as \( A \subseteq B \), it is an elemental relationship in defining set sizes and cardinalities.
The power set \( \mathscr{S}(X) \) is the set of all subsets of \(X\). By including every possible combination of elements from \(X\), including the empty set and \(X\) itself, the power set illustrates the vast number of subsets possible, reinforcing the fact that its size is significantly larger than \(X\).

Contradiction

A contradiction in logic occurs when one reasoned outcome directly conflicts with another. It's a powerful tool in proofs, especially in set theory. By assuming the opposite of what you want to prove, if a contradiction arises, it confirms the original statement.
In this exercise, a contradiction appears when assuming the existence of a bijection between \(X\) and \(\mathscr{S}(X)\). By defining a specific set \(A\) consisting of elements of \(X\) not in their respective subsets, we encounter logical conflicts. Whether or not \(y\) is in \(A\), a contradiction is inevitable, highlighting the impossibility of such bijection and further establishing \(\mathscr{S}(X)\)'s greater cardinality.

Inverse Function

An inverse function reverses the operation of a function. If \(f\) is a function with domain \(X\) and codomain \(Y\), then the inverse function \(f^{-1}\) maps back from \(Y\) to \(X\). For the inverse to exist, \(f\) must be bijective.
In the exercise, using the inverse function \(f^{-1}\) led to the logical test of including \(y\) in set \(A\), resulting in the contradiction. By demonstrating that any inclusion or exclusion of \(y\) leads to a logical impossibility, we prove that \(f\) cannot actually be bijective from \(X\) to \(\mathscr{S}(X)\). Thus, \(\mathscr{S}(X)\) indeed has a strictly larger cardinality compared to \(X\).