Set Theory: Equivalence of Sets. The Power of a Set

Definitions of finite, infinite, countable, uncountable. Demonstration of how the rationals are countable.

Theorem 1

Every subset of a countable subset is countable.

Theorem 2

The union of a finite or countable number of countable sets is itself countable.

Proof

Line the elements of the sets parallel to each other, and count all of the elements ‘diagonally’.

Theorem 3

Every infinite set has a countable subset.

Definition of equivalence.

Demonstration of how the points on a sphere can be mapped one-to-one with the points in the complex plane with stereographic projection.

Theorem 4

Every infinite set \(M\) is equivalent to one of its proper subsets.

Proof

By Theorem 3, every infinite set contains a countable subset \(A\). Partition this subset into two countable subsets \(A_1\) and \(A_2\). A one-to-one correspondence can be set between \(A\) and \(A_1\). Hence \(M = A \cup (M - A) \sim A_1 \cup (M - A) = M - A_2\) and \(M - A_2\) is a proper subset of \(M\).

Theorem 5

The set of real numbers in the closed unit interval \([0, 1]\) is uncountable.

Proof

Cantor’s diagonal. Make sure to disallow setting a digit as \(0\) or \(9\).

Definition of power, aleph null, continuum.

Theorem 6

Given any set \(M\), let \(\mathscr{M}\) be the set whose elements are all possible subsets of \(M\). Then the power of \(\mathscr{M}\) is greater than the power of the original set \(M\).

Proof

Attempt to setup \(X\) to be the set of elements of \(M\) which do not belong to their ‘associated subsets’. Then we reach an argument similar to Russel’s paradox.

Theorem 7 (Cantor-Bernstein)

Given any two sets \(A\) and \(B\), suppose \(A\) contains a subset \(A_1\) equivalent to \(B\), while \(B\) contains a subset \(B_1\) equivalent to \(A\). Then \(A\) and \(B\) are equivalent.

Proof

The proof is beautifully shown in the book. A sketch would be a disservice.

Problems

  1. Prove that a set with an uncountable subset is itself uncountable.

    Suppose the set is countable, and very quickly reach a contradiction.

  2. Let \(M\) be any infinite set and \(A\) any countable set. Prove that \(M \sim M \cup A\).

    Use Theorem 3.

  3. Prove that the following sets are countable:

    1. The set of all numbers with two distinct decimal expansions.

      Since all of the numbers can either be shown as \(n.x00000\) or \(n.y99999\), only consider the \(n.x00000\) representation. Evident that this is a subset of the rationals, hence countable.

    2. The set of all rational points in the plane.

      Simply extend the technique used for demonstrating that the rationals are countable.

    3. The set of all rational intervals.

      This can be transposed to be a subset of the the set of all rational points in the plane, i.e. the previous question.

    4. The set of all polynomials with rational coefficients.

      This can be transposed to a subset of the set of all rational points in \(n\) dimensions. Extend the argument for problem 3.2. from 2 dimensions to \(n\) dimensions.

  4. A number \(\alpha\) is called algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.

    The set of all polynomials with rational coefficients is countable, and each polynomial has a maximum of \(n\) solutions. Hence countable by Theorem 2.

  5. Prove that the existence of uncountably many transcendental numbers, i.e., numbers which are not algebraic.

    From Theorem 5, we know that there are uncountably many numbers between \([0, 1]\). And from Theorem 2, we know that no union of countable sets will ever become uncountable. Hence there must exist numbers within \([0, 1]\) which are not algebraic. We call these transcendental.

  6. Prove that the set of all real functions (more generally, functions taking values in a set containing at least two elements) defined on a set \(M\) is of power greater than the power of \(M\). In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval \([0, 1]\) is greater than \(c\).

    Just look at the identity functions. The set of all identities has a one-to-one correspondence with the power set.

  7. Give an indirect proof of the equivalence of the closed interval \([a, b]\), the open interval \((a, b)\) and the half-open interval \([a, b)\) or \((a, b]\).

    Need to find suitable functions to use with Theorem 7.

  8. Prove that the union of a finite or countable number of sets each of power \(c\) is itself of power \(c\).

    Since \([0, 1]\) is uncountable, and by problem 7, so is \([0, 1)\), map each set to \([0, 1)\), \([1, 2)\), … respectively. Evidently the union is a subset within the real line, and is itself of power \(c\).

  9. Prove that each of the following sets has the power of the continuum:

    1. The set of all infinite sequences of positive integers.

      Place \( 0. \) in front of the integers to get the set \((0, 1)\).

    2. The set of all ordered \(n\)​-tuples of real numbers.

      Use a similar argument to problem 8.

    3. The set of all infinite sequences of real numbers.

      Need to check how to deal with the uncountable sequences of real numbers.

  10. Develop a contradiction inherent in the notion of the “set of all sets which are not members of themselves”.

    Russell's paradox.

Christian Christiansen