Problem 3 - A Gentle Introduction to the Art of Mathematics

Question

In the proof of Cantor's theorem we construct a set \(S\) that cannot be in the image of a presumed bijection from \(A\) to \(\mathcal{P}(A)\). Suppose \(A=\\{1,2,3\\}\) and \(\mathrm{f}\) determines the following correspondences: \(1 \longleftrightarrow \emptyset\) \(2 \longleftrightarrow\\{1,3\\}\) and \(3 \longleftrightarrow\\{1,2,3\\}\). What is \(S ?\)

Step-by-Step Solution

Answer

The set \(S\) is \(\{1, 2\}\).

Step 1 - Define the elements of set A

The set here is given as: \(A = \{1, 2, 3\} \).

Step 2 - List the correspondences given in the problem

The function \(f\) maps the elements of \(A\) to the subsets of \(A\). The correspondences are: \(f(1) = \emptyset\) \(f(2) = \{1, 3\}\) \(f(3) = \{1, 2, 3\}\)

Step 3 - Construct the set S

Set \(S\) must include all elements \(a \in A\) such that \(a \otin f(a)\). Check each element: - For \(1\), \(1 \otin \emptyset\), so include 1 in \(S\).- For \(2\), \(2 \otin \{1, 3\}\), so include 2 in \(S\).- For \(3\), \(3 \in \{1, 2, 3\}\), so do not include 3 in \(S\).Therefore, \(S = \{1, 2\}\).

Key Concepts

set theory

Set theory is a fundamental branch of mathematics that deals with the study of sets, which are collections of objects. A set can contain numbers, symbols, or even other sets. For example, the set \(A = \{1, 2, 3\}\) includes the numbers 1, 2, and 3. In set theory, we often use special notations and concepts:

• \( \in \) indicates membership, meaning an element is in a set. For example, 1 \( \in A\) means 1 is an element of set A.
• \( \otin \) indicates non-membership, meaning an element is not in the set. For example, 4 \( \otin A\) means 4 is not in set A.
• \( \mathcal{P}(A) \) is the power set of A, the set of all subsets of A. If \( A = \{1, 2, 3\} \), then \( \mathcal{P}(A) = \{\{\}, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}\).

Understanding these concepts helps you grasp how set theory forms the basis for more advanced mathematical topics, like Cantor's theorem and related proofs.

bijection

A bijection is a special type of function that creates a one-to-one correspondence between the elements of two sets. In other words, a bijection means:

• Each element of the first set is paired with exactly one element of the second set.
• No two elements from the first set are paired with the same element from the second set.

In our exercise, set A and its power set \( \mathcal{P}(A) \) are involved. The function \ f \ gives a supposed bijection between these sets. Here are the specifics:

• \( f(1) = \emptyset \)
• \( f(2) = \{1, 3\} \)
• \( f(3) = \{1, 2, 3\} \)

Bijections are important in proofs, particularly in Cantor's theorem, because they help us establish relationships or the lack thereof between different sizes (cardinalities) of sets.

proof techniques

In mathematics, proof techniques are methods used to establish the validity of statements. Cantor’s theorem is proven by contradiction, a common proof technique. Here's how it works:

• Assume that there is a bijection \ f \ from set A to its power set \( \mathcal{P}(A) \).
• Construct a set \ S \ in \( \mathcal{P}(A) \) that \ f \ supposedly maps to.
• Show that \ S \ cannot be in the image of \ f \ under the given mappings.

In our exercise, we built set \( S = \{1, 2\} \) such that \ S \ includes elements for which corresponding elements are not in their subsets mapped by \ f \:

• For 1, 1 \( \otin \emptyset\), so include 1 in \ S \.
• For 2, 2 \( \otin \{1, 3\}\), so include 2 in \ S \.
• For 3, 3 \( \in \{1, 2, 3\}\), so do not include 3 in \ S \.

Therefore, \ S = \{1, 2\} \ cannot be mapped back into \ f \’s image, showing that no bijection exists and proving Cantor's theorem by contradiction.