Size of the power set

Introduction. Let be any arbitrary set. We say a set is a subset of (written ) if every element of is also an element of . For example, , every set is a subset of itself, and the empty set is the only subset of itself.

Again consider set . We define the power set of , ,  as

.

Thus the power set of is “the set of all subsets of ”. Here are a few examples of power sets:

• Let . Then the power set of is ;
• Let . Then the power set of is ;
• The power set of is . Notice that these two are different: the former is a set with no elements, while the latter is a set with a single element which happens to be the empty set.

We now pose an interesting question: given a set with elements (written ), what is the number of elements of its power set (written )? Peeking at concrete examples like those above, looks like the correct answer — even for the last one, since . But is it really so?

Quadratic formula

Introduction. Let , where . We call the equation a quadratic equation. It is a well-known fact that, given and , there are at most two distinct values of satisfying the equation — called solutions or roots. For example:

• The equation has one solution, namely ;
• The equation has two solutions, namely and ;
• The equation has no solutions. This can be shown pictorially by drawing the graph of , which never intersects the -axis.

Given a quadratic equation, its roots can be found by applying the quadratic formula:

.

We now intend to prove the correctness of this formula.

Irrationality of √2

Introduction. Let be the set of real numbers. Intuitively, these are all the numbers that can turn up when we measure the distance between two points. The set includes the naturals , the integers , and the rationals . The latter are all the numbers that can be written as fractions; more precisely, if and , then . Every fraction can be made irreducible, i.e., we can write any rational number as where and are coprime — they have no common divisors apart from .

Clearly, all the sets mentioned so far are successively contained in each other: . But is ? The answer is negative. The remaining elements of — i.e., those not in  — are aptly called irrational.

Consider a real . We say is a square root of if . It can be shown — but we will not show here — that every non-negative real number has a real-valued square root; in fact, every positive real number has two distinct square roots (one positive and the other negative), and zero is the unique square root of itself. Whenever has a square root, we denote by the non-negative square root of .

Since is a positive real number, it follows that exists in . Here we will show that is irrational. The importance of this theorem lies in the fact that it proves irrational numbers do indeed exist.

Fundamental theorem of arithmetic

Introduction. Let be the set of natural numbers. We say is a prime number if has exactly two distinct divisors: and itself. The first few prime numbers are:

Given , a prime factorization of is a product of naturals such that the are all prime. Notice that a prime factorization may contain multiple occurrences of the same prime number, but the order in which the appear is not important. For example, and are prime factorizations of and , respectively. Clearly, if is a prime number, itself is its unique prime factorization. Also, the number is special in that its unique prime factorization is the empty product.

Considering an arbitrary natural number , two interesting questions arise. First, is guaranteed to have a prime factorization? Second, if it does exist, is it unique (up to rearrangement)? The Fundamental Theorem of Arithmetic answers affirmatively to these two questions.