43

Cantor's Theorem

• Introduces the concept of comparing the size of a set A with the size of its power set P(A).

• For any set A, the power set P(A) always has strictly greater cardinality than set A itself.

Theorem 1: Relation Between Set and Power Set

• If set A has 3 elements, then the power set P(A) has 8 elements since the number of elements in P(A) is given by 2 raised to the number of elements in A (i.e., 2^3 = 8).

• For any set A, the cardinality of A is less than that of its power set, denoted as |A| < |P(A)|.

• Proof:

  • Define a function f from A to P(A) by f(x) = {x} for each element x in A.

  • This function is one-to-one (injective) but not onto (surjective).

  • Example: If f(x1) = f(x2), then {x1} = {x2}, implying x1 = x2, confirming injectiveness.

Theorem 1: Proof of Non-Onto

• Suppose function f: A -> P(A) is onto.

• Define the set B = {x ∈ A : x ∉ f(x)}.

• Example: If A = {1, 2, 3}, then:

  • f(1) = {1}, f(2) = {2}, f(3) = {3}; hence, B would be a subset PA.

• Since f is onto, there exists an element a in A such that f(a) = B and B must be a subset of A.

• There are two possibilities for element a:

  1. a ∈ B

  2. a ∉ B

• Either scenario leads to a contradiction.

Theorem 1: Conclusion on Onto Definition

• Case 1: If a ∈ B, then by the definition of set B, a cannot be part of B, leading to a contradiction.

• Case 2: If a ∉ B, then it would imply a ∈ f(a) which is again a contradiction.

• Hence, the assumption that f is onto is false: |A| < |P(A)|.

Theorem 2

• States that for any cardinal number n, 2^n = c, where c represents the cardinality of the continuum.

Continuum Hypothesis

• Postulates that there exists no cardinal number B such that 2^A < B < c, where A represents a set.

• For any cardinal number N, it is established that N < 2^N = c.