The square root of 2 is irrational, i.e there are no integers a and b such that (a/b)^2 = 2. Proof:

Suppose a and b are integers with no common factor (since if they had common factors then we could cancel it out).

(a/b)^2 = a^2 / b^2 = 2

a^2 = 2b^2

This means a^2 is even.

But if a^2 is even, then a must be even. Since if a is not even then its factors do not contain 2, which means the factors of a^2 do not contain 2 either.

But if a is even then a^2 must be divisible by 4:

a = 2c

a^2 = 4c^2

4c^2 = 2b^2

2c^2 = b^2

This means b must also be even. But we previously concluded that a must be even, so a and b share a common factor (2), which contradicts our assumption. This means a and b do not exist.

Definition 1. Two sets A and B have the same cardinality if and only if there exists a bijection between A and B i.e a function that pairs each element from set A with exactly one element in B and each element in B with exactly one element in A. This definition is ingenious because it works for both finite and infinite sets.

Definition 2. The power set of a set S is the set of all the subsets of S (anything could be a set element, including sets). This includes the empty set and S itself. Reminder: In a set, order does not matter and there are no repeated elements.

Definition 3. A set is countable if it has a finite number of elements or if it has the same cardinality as the set of all natural numbers.

Theorem 1. The set of all integers Z has the same cardinality as the set of all natural numbers N. Proof:

We want to map the following sequence:

1, 2, 3, 4, 5…

To this sequence:

0, 1, -1, 2, -2…

Define the pairing function f that maps the naturals to the integers:

for each number n in N:

if n is odd, return -(n-1)/2

if n is even, return n/2

Notice here that since n is always positive, if n is even, f(n) is positive, and if n is odd, then f(n) is either 0 or negative.

We need to show that f is a bijection, so we need to prove 2 things:

1. f is injective i.e if two elements in N map to the same element in Z, then they must be the same element. i.e each element in N maps to exactly one element in Z.

Let x and y be elements in N. Suppose f(x) = f(y). We want to show that x=y.

If f(x) = f(y) then either they’re both positive or they’re both negative.

If f(x) and f(y) are positive then x and y must be even. Therefore:

f(x) = f(y)

x/2 = y/2

x = y

If f(x) and f(y) are negative then x and y must be odd. Therefore:

f(x) = f(y)

-(x-1)/2 = -(y-1)/2

(x-1)/2 = (y-1)/2

x-1 = y-1

x = y

Therefore f is injective.

2. f is surjective i.e each element in Z is paired with at least one element in N.

For f to be surjective you need to show that every y in Z can be written as y=f(x) for some x in N.

In this case:

If y is positive, then f(2y) = y.

If y is 0, then f(1) = y.

If y is negative, then f(-2y+1) = y. Proof:

y = -(n-1)/2

2y = -(n-1)

-2y = n-1

-2y+1 = n

Since f is both surjective and injective, it is bijective, and therefore is a bijection from N to Z, hence Z is countable.

Theorem 2. The set of all rational numbers Q is countable. This means “countably infinite x countably infinite = countably infinite”.

Recall that a rational number is of the form a/b where a and b are integers.

Therefore, the natural numbers are included in the set of rationals. So we know that the cardinality of the rationals is at least as big as the cardinality of the naturals. For our proof then, it suffices to show that there are at least as many naturals as there are rationals.

We may create a table to represent all positive rational numbers:

Denominators/Numerators:

D\N 1 2 3…

1 1/1 2/1 3/1…

2 1/2 2/2 3/2…

3 1/3 2/3 3/3…

…

In this way, every possible pair of positive integers a and b is accounted for and thus all positive rational numbers are in this table.

The next question is how to assign each value of the table to a unique natural number and vice versa. We need to remember to account for 0 and the negative versions of each rational number in the table as well.

The idea is to proceed one diagonal at a time, so you go 1/1, 1/2, 2/1, 1/3, 2/2, 3/1 and so on.

This is the easiest way intuitively to see how one might map the naturals to the rationals, but since we need to prove that there are at least as many naturals as there are rationals, we need to create a function that maps every rational to a natural, and doing this with the mapping described above is a bit…well there is a much simpler way:

Define f(a/b) as follows:

if a/b is positive, return (2^a)(3^b)

if a/b is negative, return (2^a)(3^b)(5)

Notice that f(a/b) is a multiple of 5 if and only if a/b is negative, and is not a multiple of 5 if and only if it is positive.

EDIT: THIS IS NOT A BIJECTION! YOU NEED TO SHOW THAT THERE IS A BIJECTION FROM THE NATURALS TO THE RATIONALS IN ORDER TO SHOW THAT THEIR CARDINALITY IS THE SAME! I have not yet proved the Cantor-Bernstein theorem so I can’t show that if there are 2 injections then there is a bijection. I have found what looks to be a correct answer here: http://math.stackexchange.com/questions/7643/produce-an-explicit-bijection-between-rationals-and-naturals but have not checked it for myself. I will check it when I have time.

This guarantees that every rational number has a unique natural number mapped to it and thus that the number of naturals is at least as big as the number of rationals. Proof:

Suppose f(a/b) = f(x/y). We need to show that a/b = x/y.

if a/b is positive, then f(a/b) is not a multiple of 5, and therefore f(x/y) is not a multiple of 5, and therefore x/y is positive. Therefore:

(2^a)(3^b) = (2^x)(3^y)

It suffices to say that since any natural has only one unique prime factorization, a=x and b=y. But how do we know this? We need to show that each natural must have exactly one unique prime factorization. This is the fundamental theorem of arithmetic. Euclid’s proof requires several lemmas but there is a simpler proof that only requires one lemma, so we’ll use that one.

Lemma: Every natural number is either a prime or a product of primes.

Proof by induction:

Base case: 2.

As 2 is a prime, the base case is done.

Inductive step:

Suppose the lemma is true for all numbers up to and including n. We need to prove that it is true for n+1.

If n+1 is prime then we are done.

If n+1 is not prime then something greater than 1 but less than n+1 divides it, call that number x.

(n+1) / x = y

We know that x and y must be both less than n+1, since otherwise their product would be greater than n+1.

Since the lemma is true for all numbers less than n+1, and x and y are less than n+1, then the lemma is true for x and y, therefore x and y are products of primes.

Theorem: Every natural has a unique prime factorization.

First of all, what does it mean for a number n to have a unique prime factorization? It means that there is a list of primes call it P = {p_1, p_2, p_3…} such that their product is n (forgive the underscores, p_1 means p subscript 1 in latex). This of course means that n is divisible by each of those prime factors (since we can write n = p_i * b where b is the product of all the other primes). But it also means that n is not divisible by any prime that is not in P. Why? Because this factorization is UNIQUE. It means the number n CANNOT be expressed by any other factorization! If n was divisible by some prime that is not in P, call it q, then that would produce a different prime factorization of n, since we can write n = qb for some natural b, and we know from the lemma we just proved that since b is a natural it has a prime factorization. Now, q appended to the prime factorization of b produces a prime factorization of n call it Q, and Q is different from P because Q contains q but P does not. Therefore if a number has only one unique prime factorization then it cannot be divisible by any primes that are not in its unique prime factorization.

Base case: 2 has a unique prime factorization. Done.

Inductive step: We assume the theorem is true for naturals up to n. We need to show that n+1 has a unique prime factorization.

If n+1 is prime then we are done.

If n+1 is not prime then there is a smallest factor of n+1 call it p such that n+1 = pb

p is prime, otherwise it would be divisible by a smaller number which would then also be a factor of n+1.

(n+1) / p is smaller than n+1 and therefore has a unique prime factorization. Appending p to this yields a prime factorization of n+1, call it X. We need to show that this is unique.

Suppose there is another prime factorization for n+1 call it Y. There are 2 cases:

If Y contains p then since (n+1)/p has a unique factorization, the result of deleting p from Y is that unique factorization. Since X is the unique factorization of (n+1)/p with p appended, X = Y and we are done.

If Y does not contain p then the least factor in Y call it q is a prime that is greater than p, since we said before that p is the smallest prime factor of (n+1).

Now we have p < q and (n+1) = qc where c is some integer with c = (n+1) / q < n+1 since q is a prime. Since c<n+1 it has a unique prime factorization that does not include p (c is the product of Y without q), hence p does not divide c.

Now, consider the number (n+1) – pc.

(n+1) – pc = pb – pc = qc – pc = p(b-c) = c(q-p)

By observation it is obvious that p divides p(b-c) and therefore divides (n+1) – pc as well as c(q-p).

Now, we know from earlier that p does not divide c. Therefore p must divide (q-p). So:

q-p = xp for some x

q = p(x+1)

Since p divides p(x+1), p divides q. However, since we know q is a prime, that means p = q. However we also know that p < q, we get a contradiction.

This means there is no alternative prime factorization of (n+1) and the proof is done.

Euclid’s theorem: There are an infinite number of primes (there is no biggest prime). Proof:

Given any list of primes {p1,p2…}, there is at least one prime not in the list.

Let P be the product of the list of primes. Let q = P + 1.

If q is prime, then we are done.

If q is not prime, then we want to ask if some prime on the list divides it.

Note that since P is the product of every prime in our list, then every prime in our list divides P.

Now suppose a prime p in our list divides both P and q. Then we have:

py = P

px = P+1

p(x-y) = 1

Since no prime number divides 1 (since all primes are bigger than 1), p cannot exist. Intuitively it should be easy to see that no prime can be a factor of both P and P+1. Therefore p is not on the list and we are done.

Cantor’s theorem: The power set of a set is strictly bigger than that set (whether finite or infinite). This means some infinite sets are bigger than others! It also means if we take the power sets of power sets repeatedly we end up with an infinite hierarchy of infinities, meaning there’s no biggest infinity!

Proof:

Denote the power set of a set A as P(A).

We prove this by showing that you can have an injection from A to P(A) (meaning that there are at least as many elements in P(A) as there are in A) but that you cannot have a surjection from A to P(A).

It is trivial to show that the cardinality of P(A) is at least the cardinality of A. Define the function:

f(x) = {x}

P(A) is the set of all subsets of A, and so each element in A has its corresponding set consisting of only itself in P(A). So this is done.

Now if we can show that for every function f from A to P(A) we can find an element in P(A) that is not paired by the function to any element in A, then we are done.

Take any function f from A to P(A).

Now create the set S = {x in A such that x is not in f(x)}. We can create this set because we know f and we can go through each element x in A and check if x is in its corresponding set f(x). We also know that S is an element of P(A) because P(A) is the set of all subsets of A and S is a subset of A.

Now all we need to do is to show that the set S is not f(x) for any x in A and therefore there exists an element in P(A) that is not paired to any element in A by f.

Suppose that S is f(x) for some x in A.

Then consider the 2 possibilities:

x is in f(x) i.e x is in S. But since S is the set of elements x such that x is not in f(x), if x is in S, then x is not in f(x), which is S – a contradiction.

x is not in f(x) i.e x is not in S. But if x is not in f(x), then it should be in S, since S contains all x such that x is not in f(x) – a contradiction.

Therefore no such x exists, meaning S is not paired with any element in A. This means for any pairing function from A to P(A), there is always at least one element in P(A) that is not paired with any element in A, therefore the cardinality of P(A) is strictly greater than the cardinality of A.

Theorem. The cardinality of the naturals is the smallest infinity.

Proof: Take S to be any infinite set. Then we start taking out its members without emptying it (since it is infinite). Continuing to do this creates a denumerable set (i.e a set that has the same cardinality as the naturals aleph zero). This means any infinite set has a proper subset which is denumerable. This means a denumerable set cannot have greater cardinality than any infinite set. Therefore aleph zero is the smallest transfinite (infinite) cardinality.

Theorem: 0.999…=1. Binary version: 0.111…=1. This theorem is important because it shows that you have to be careful when doing diagonalization on real numbers, since two different decimal expansions may represent the same real number (so if you’re doing a proof that uses a bijection from decimal expansions to the reals, you need to take care to not include multiple decimal representations of the same number). Proof:

Suppose 0.999… != 1. Then the two numbers are distinct. But between two distinct real numbers, there is always another real number – this is a property of the reals: you can divide it infinitely.

In this case, denote the difference between 0.999… and 1 as x. Then we can construct another real number y = 0.999…+x/2 which is closer to 1 than 0.999…

Why is this problematic? We have 0.999… < y 0

f(x) = 1 + 1/x if x < 0

Now, for values of x between 0 and 1, we have -1+1/x, so when x is 1 we have 0 and as x goes to 0 f(x) goes to +infinity.

For values of x between -1 and 0, we have 1+1/x, so when x is -1 we have 0 and as x goes to 0 f(x) goes to -infinity.

f(x) = f(y)

if f(x) positive we have:

-1 + 1/x = -1 + 1/y

1/x=1/y

y=x

if f(x) negative we have:

1+1/x = 1+1/y

y=x

Surjection:

f(x) = y for some arbitrary y from -infinity to +infinity.

If y is positive then:

f(x) = -1+1/x = y

1/x = y+1

1/(y+1) = x clearly a positive real number less than 1.

And likewise when y is negative:

1/(y-1) = x clearly a negative real number greater than -1.

Hence f is a bijection. So there you have it. The cardinality of the reals from 0 to 1 is the same as the cardinality of the reals from -1 to 1, which is the same as the cardinality of the reals. To prove this you simply compose the functions so a number in (0,1) goes to (-1,1) then to R.

Theorem. The reals are uncountable

Cantor’s diagonal argument:

If |R| = |N| then there is a surjection from N to R, meaning every real is paired with a natural.

We want to show that for any function from N to R there is at least one real that is not paired with any natural. Proof:

Take any function f from N to (0,1)

f(1) = 0.a_{1,1} a_{1,2} a_{1,3} …

f(2) = 0.a_{2,1} a_{2,2} a_{2,3} …

…

Now consider the following number:

The ith digit of our number is 4 if the ith digit of the ith number in the sequence is not 4, and 8 if it is 4:

n_i = 4 if a_{i,i} != 4

n_i = 8 if a_{i,i} = 4

I have chosen the numbers 4 and 8 to avoid problems associated with the fact that 0.999…=1. Any scheme which avoids that problem will do.

Now, it is clear that this number we have constructed is different in the ith digit from the ith number on the list, for every number on the list, and therefore it is not on the list. So it is not mapped to by our function, meaning our function is not a surjection. This means there can be no surjection from N to R and therefore the reals are uncountable.

Does the set of all sets that do not include themselves include itself?

If this set includes itself, then since it is in the set of all sets that do not include themselves, it does not include itself – a contradiction. But if it does not include itself, then it belongs to the set of all sets that do not include themselves, so therefore it must include itself! A paradox. Thus modern formulations of set theory do not allow for these kinds of sets.

Lawrence Krauss once said: “The sum of all natural numbers is -1/12. It may seem illogical that an infinite series of positive terms, each of which is bigger than 1/12, can have a finite sum of -1/12, but the fact that you find it illogical just means you’re ignorant”. But a divergent series has no limit, so it makes no sense to talk about “the sum of all natural numbers”. However, this number is supposedly used in the calculation of the Casimir force so there may be something more to this.

The less rigorous (actually incorrect) proof goes like this:

First you need to accept that the limit of the series 1-1+1-1+1… is 1/2. Then:

S=1+(-2)+3+(-4)+…

2S = 1+(-2)+1+3+(-2)+(-4)+3+…= 1-1+1-1… = 1/2

S = 1/4

And then:

S = 1+2+3+…

4S = 4+8+12+…

S-4S = 1+2-4+3+4-8+5+6-12+…

-3S = 1-2+3-4+5-6+… = 1/4

S = -1/12

Similarly it can be shown that the limit of the series 1+2+4+… is -1:

S = 1+2+4+…

2S = 2+4+8…

S-2S = -S = 1+2-2+4-4+… = 1

S = -1

Likewise you can prove 1=0:

S=1+1+1+…

S-S = 0 = 1+1-1+1-1… = 1.

# Fun proofs part 1

Advertisements