Problem 6 - A Gentle Introduction to the Art of Mathematics

Question

Verify that the final deduction in the proof of Cantor's theorem, " \((y \in\) \(S \Longrightarrow y \notin S) \wedge(y \notin S \Longrightarrow y \in S), "\) is truly a contradiction.

Step-by-Step Solution

Answer

The statement is a contradiction because it asserts that y is both in and not in S at the same time.

Step 1: Understand Cantor's Theorem

Cantor's theorem states that for any set, the power set (the set of all subsets) has a strictly greater cardinality than the set itself.

Step 2: Analyze the Contradiction Statement

The statement given is \( (y \in S \Longrightarrow y \otin S) \wedge (y \otin S \Longrightarrow y \in S) \). It means if y is in set S, then y is not in S, and if y is not in S, then y is in S.

Step 3: Break Down the Implications

Consider the first part: \( y \in S \Longrightarrow y \otin S \). This means if y is in S, it cannot be in S (which is a contradiction by itself). Now the second part: \( y \otin S \Longrightarrow y \in S \). This means if y is not in S, then it must be in S (another contradiction).

Step 4: Combine Both Contradictions

Since both parts are contradictions on their own, combining them with an AND (\( \wedge \)) operator makes the entire statement a contradiction, as it states that y both is and is not in S simultaneously.

Step 5: Conclusion

The final deduction of Cantor's theorem \( (y \in S \Longrightarrow y \otin S) \wedge (y \otin S \Longrightarrow y \in S) \) is indeed a contradiction because it asserts two mutually exclusive conditions to be true at once, which is impossible.

Key Concepts

set theory

Set theory is a branch of mathematical logic that deals with sets, which are collections of objects. Sets can include anything, from numbers to letters to other sets. In set theory, we often use notation to describe whether something is part of a set. For example, if we have a set S, and an element y, we denote y being in S as \(y \in S\), and y not being in S as \(y otin S\).

Some basic operations in set theory include:

• Union: Combining two sets together, denoted as \(A \cup B\).
• Intersection: Finding the common elements between two sets, denoted as \(A \cap B\).
• Difference: Elements in one set but not in another, denoted as \(A - B\).

Set theory is fundamental because it provides the basis for more complex mathematical concepts, such as functions, sequences, and power sets.

power set

A power set is the set of all subsets of a given set. If you have a set S, the power set of S, denoted as \(\mathcal{P}(S)\), includes every possible combination of elements from S, including the empty set and S itself.

For example, if \(S = \{ a, b \}\), then the power set \(\mathcal{P}(S)\) is:

• \(\emptyset\) (empty set)
• \(\{a\}\)
• \{b\}
• \{a, b\}

The power set is important in set theory and logic because it allows us to explore the relationships among subsets and the original set. Cantor's theorem states that the power set of any set always has a strictly greater cardinality (size) than the set itself, meaning you can never match up every element of a set to a unique element of its power set without running out of elements in the original set.

logical contradiction

A logical contradiction occurs when a statement both asserts and denies the same thing, which is impossible. In the context of Cantor's theorem, we encounter a specific contradiction.

The statement \((y \in S \Longrightarrow y otin S) \wedge (y otin S \Longrightarrow y \in S)\) means:

• If y is in S, then y is not in S.
• If y is not in S, then y is in S.

Both these statements cannot be true at the same time because they argue that a condition is both true and false simultaneously. The key to identifying a contradiction is looking for mutually exclusive conditions that are claimed to be true together. Understanding contradictions is essential for recognizing errors and inconsistencies in logical arguments and proofs.

cardinality

Cardinality refers to the number of elements in a set, often described as the 'size' of the set. In set theory, we typically compare the cardinality of different sets to understand their relative sizes. For example, the cardinality of a finite set \(\{a, b, c\}\) is 3.

When comparing infinite sets, things get more interesting. The set of natural numbers \(\mathbb{N} = \{1, 2, 3, \ldots\}\) has an infinite cardinality, often denoted by \(\aleph_0\) (aleph-null).

Cantor's theorem shows that the power set of any set has a strictly greater cardinality than the set itself, even if the original set is infinite. This means there's no one-to-one correspondence between a set and its power set, emphasizing different 'sizes' of infinity. Understanding cardinality helps us grasp these deep and sometimes counterintuitive properties in mathematics.