Analysis and Other Math Proofs

Fact: The set of real numbers, ℝ, is uncountable.

Proof: We will focus on the subset (0,1)⊆ℝ and show that this set cannot be countable. Since ℝ sits above an uncountable set it follows that ℝ is also uncountable. We have not yet proven the lemma a set containing an uncountable subset must be uncountable (dear reader, we would also start this by contradiction getting a 1-1 function from the "bigger" set to ℕ).

By contradiction, suppose ∃f:(0,1)↦ℕ which is 1-1. We can now "count" the elements of (0,1): a1=f -1(1), a2=f -1(2),….

We will go further and consider the decimal expansion of each an=0.an1an2an3.... That is, ank is the kth digit of the decimal expansion of an. We put these digits in the the following infinite table where the nth row holds the digits of an.

a11 a12 a13 a14 … a21 a22 a23 a24 … a31 a32 a33 a34 … a41 a42 a43 a44 … ⋮ ⋮ ⋮ ⋮ ⋱

We will now construct a "new" element b∈(0,1) by defining the decimal digits of b=0.b1b2b3b4... as follows. If ann=1, let bn=2. Otherwise, let bn=1. Doing this for every n∈ℕ defines every decimal digit of b and therefore defines b itself. Note also that bn≠ann ∀n.

Now we simply notice that b cannot be in the above "listing" of (0,1) because it cannot be in any of the rows. It cannot be in the jth row because the jth entry of that row is ajj≠bj. In this way we see that b∉{a1,a2,a3,...}=(0,1), which contradicts the construction of b∈(0,1).☐

Fact: There is an irrational number.

Proof: In fact, if p is any prime number, then √p is irrational.

To see that this is true, suppose by way of contradiction that √p=a/b where a,b∈ℕ and a and b are reduced so that gcd(a,b)=1.

Squaring both sides of our equation gives p=a2/b2 which can be rewritten as b2p=a2. This gives that p is a divisor of a2, and since p is prime, in fact we can conclude that p divides a. This means ∃c∈ℕ with cp=a.

Squaring both sides of this last equation gives c2p2=a2. Combining this with the previously known b2p=a2 gives b2p=c2p2. Dividing both sides of this by p gives b2=c2p, which now tells us that p must also divide b. This contradicts the fact that gcd(a,b)=1.☐

Fact: Instant runoff does not satisfy the Condercet criterion.

Proof: We prove this with an example using 5 voters and 3 candidates.

1st Choice A B A B C 2nd Choice C C C C A 3rd Choice B A B A B

There is no majority winner as no candidate has more than 40% of 1st choices. C has only one first choice and would be eliminated in the first round of instant runoff. At this point A would have 3/5 1st place votes and win the instant runoff election.

We see that C is the Condercet winner. C is preferred to B in columns 1, 3, and 5. C is preferred to A in columns 2, 4, and 5.☐

Proof: We will prove the first statement by extablishing set inclusion "both ways". The second statement follows from a slightly modified argument.

[⊆:] Let x∈(∩Aα)C. This means x∉∩Aα. By definition of ∩, there is an Aβ with x∉Aβ. This means x∈(Aβ)C⊆∪(Aα)C. So x∈∪(Aα)C.

[⊇:] Let y∈∪(Aα)C. This means there is an Aγ with y∈(Aγ)C. This means y∉Aγ. So y cannot be in ∩Aα which is contained in Aγ. That is to say y∈(∩Aα)C.☐

Proof: Let x < y be given real numbers. By the Archimedean property, there is an integer n such that n(y-x)>1. This means that the gap between ny and nx is wider than 1, meaning that we can find an integer in this gap.

Formally, if we consider the set A={m∈&Zopf;:m>nx}, then we have a nonempty set of integers which is bounded below. This set must have a least element, and we will call this element q. Note that q∈A implies that q>nx.

Also, q<ny. If this were not the case, we would have q-1≥ny-1>nx and then q-1∈A. But this would contradict that q is the least element of A.

We have q∈&Zopf; with ny>q>nx. This implies that y>q/n>x and q/n is an element of ℚ as desired.☐

Proof: Consider an election with m candidates and n voters. Suppose that candidate C is the Condercet winner of this election.

The number of Borda points depends on the number of candidates. There are 0 points for last place and (m-1) points for first place. So the total number of points available on each ballot is 0+1+...+(m-2)+(m-1)=∑k=0m-1k = (m-1)*m⁄ 2.

The total number of Borda points available is (number of ballots)*(points available on each ballot)=n*m*(m-1)⁄ 2. So the average candidate Borda score is (total points)/(# candidates)=n*m*(m-1)⁄ (2*m) =n*(m-1)⁄ 2.

It remains to show that candidate C has more than this many Borda points.

Recall that candidate C is the Condercet winner. This means C wins pairwise matchups against each of (m-1) other candidates. In order to win a pairwise matchup against any one of these candidates, C would need to be ahead of them on at least (n+1)/2 ballots. (If C were ahead of A on only n/2 ballots, then A would be ahead of C on n/2 ballots and C would not win that pairwise matchup. Also, (n+1)/2 need not be an integer. If n is even, then C will in fact need to be ahead of A on (n+2)/2 ballots, which would only add padding to the argument.)

C earns a point every time it is ahead of another candidate on a ballot. We have seen that C picks up at least (n+1)/2 points per other candidate. Therefore, the total Borda score of C is greater than or equal to (m-1)*(n+1)/2>(m-1)*(n)/2 which is the average Borda score.☐