[News]

News: Welcome to The Oktave Forum.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

This is a proof that I love. It is sophisticated, simple and beautiful. It's a proof that there are infinitely many prime numbers. It is due to Euclid.

Euclid proves this by finding a contradiction. To begin with, assume that there are a finite number of primes. Whatever be the number of primes, the previous statement implies that there must be a last one. Call this P. Next, multiply all the primes together to form a number N.

N = 2 X 3 X 5 X ... X P

We can see that N is divisible by all the primes. Add 1 to N.

N = 2 X 3 X 5 X ... X P + 1

This is the brilliant step. You can see now that N is not divisible by *any* of the primes; they all leave a remainder of 1. So, two cases arise here one of which must hold.

(1) N is prime. If this holds, it is a contradiction in terms. We missed at least one prime in our earlier list of all primes.

(2) N is composite. If this holds, then we ought to be able to express N as a product of a set of primes (assuming that this fact has already been proven). However, since none of the primes we began with can be a factor, there must be some other primes outside this set which are factors of N. Again, we see that we missed out on some primes.

You can also see that this argument can be generalised no matter what the size of the initial list is. Thus, we prove that there are infinitely many primes.

[sids]

sids

sids

Visit sids's website.

Show sids's last posts.

Show general stats for sids.

• 
• God
• Administrator
• Full Member
• Karma: 65535
• Posts: 132

This is awesome! The clarity in the thought process is astounding.

Thanks for sharing this.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Incidentally, this is one of the first evidence of proof by contradiction. Proof by contradiction is an extremely powerful notion, and much of the most beautiful proofs in mathematics are proofs by contradiction (Cantor's diagonal argument about uncomputable sets is another example.)

There is a precursor theorem to the theorem of infinite primes. And that is about how every number can be decomposed into prime factors. (A related post on proofs from my blog is here).

The proof goes as follows. Assume the contrary: i.e. a number N, which is the smallest number that does not have prime factors. That means, N should be composite and among its factors (N₁, ... N_k), there should be at least one non-prime N_i.

But then, we assumed that N is the smallest number, which does not have prime factors, so it means N_i should have prime factors. Therefore N also has prime factors!

The implication of this theorem is that prime numbers are the building blocks of all natural numbers. And the infinite primes theorem states that there are infinitely many building blocks!!

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

A lot of times, proofs by contradiction lead to a contradiction which is not directly related to the statement that we want to prove. There is a contradiction alright, and the proof is indeed valid, but a slight nagging feeling remains

But these proofs that we are talking about here, lead to contradictions that stare at our face. So, the effect is direct.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Good proofs always have the direct effect. That's what make them beautiful..

[sids]

sids

sids

Visit sids's website.

Show sids's last posts.

Show general stats for sids.

• 
• God
• Administrator
• Full Member
• Karma: 65535
• Posts: 132

A lot of times, proofs by contradiction lead to a contradiction which is not directly related to the statement that we want to prove. There is a contradiction alright, and the proof is indeed valid, but a slight nagging feeling remains

But these proofs that we are talking about here, lead to contradictions that stare at our face. So, the effect is direct.

Zeno's paradoxes are somewhat like the ones Sanket describes; in this case you know there is something wrong but you just cannot pin point it. I had posted about these a few days ago here.

Incidentally, this is one of the first evidence of proof by contradiction. Proof by contradiction is an extremely powerful notion, and much of the most beautiful proofs in mathematics are proofs by contradiction (Cantor's diagonal argument about uncomputable sets is another example.)

Incidentally, Zeno's paradoxes are also credited as the first examples of usage of proof by contradiction although they deal with Philosophy rather than Mathematics.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Zeno's paradoxes are not really mathematical proofs. In fact, mathematically, they are not paradoxes either. They make use of infinite progressions to prove an impossibility that does not exist actually.

In logic, a paradox has a very specific meaning. It is a self referential assertion with a contradiction. For example: "This statement is false."

Contradiction and paradoxes are sometimes confused to mean one and the same thing. But no. Contradiction is falsehood, while paradox is an impossibility. A contradiction simply evaluates to false, while a paradox keeps cycling between true and false. For example, an assertion "This statement is false", if true, should mean the statement is false, which should mean the statement is true, which should mean...

A contradiction on the other hand is something like a statement that says: "x is an odd number that is divisible by 2." It is simply false.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Zeno's statements seemed paradoxical at a time when the mathematics was not sophisticated enough to handle them. Once the ideas of the infinitesimal and limits were developed, the paradoxes ceased to be. The problem is that Zeno was trying to discretize quantities which are continuous. Quantities like distance and time are continuous and need to be measured. So, once calculus was developed, things became easy.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

I pressed post before completing my reply. Let me continue here...

When I said some proofs don't have a "direct impact", I was talking about much simpler things. For example, consider the proof for 'square root of 2 is irrational'. We start by assuming that square of 2 is rational, and hence expressible as a fraction. And then through a series of steps we arrive at a point where both the numerator and denominator of a fraction (expressed in its lowest form) are even. This is incorrect and hence the contradiction. As you can see, the connection between this fact and the fact that square root if 2 is irrational is not immediately apparent. The proof is, of course, valid. Since we arrived at an incorrect statement through a series of logically correct statements, there must be an error somewhere. And it so happens that the error is in the premise itself.

OTOH, Euclid's proof gets to the point straight.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

While we are on the topic of proofs, here is something on mathematical induction -

Mathematical induction proves that we can climb as high on a ladder as we want by proving that we can climb on the bottommost rung of the ladder, and then that from each rung we can climb up to the next one.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

The reason for this is in the generalization step in induction.

The example that I typically use to explain this is to "prove" by induction that I can walk any number of miles by showing that I can walk one mile, two miles, etc. and generalizing.

The generalization works only if there is a crucial axiom that holds -- the CWA or the closed world assumption. Be it the climbing ladder example or walking example, the implicit assumption is that we have captured everything that is required for this activity in our initial examples. Which is not true. We have not captured elements like gravity in the ladder example, or exhaustion in the walking example.

In fact, the whole of theoretical computer science for which Turing Machines are the basis, rely upon the closed world assumption. The moment we relax the CWA, we're opening a Pandora's box. We not only should allow external variables to affect our problem solving process during computation, we also have to successfully complete the process in order to prove our theorem. If I have to prove that I can drive home from work on a rainy evening in Bangalore traffic; I should show that I can not only respond to the hurdles I get (rain, traffic, etc.) but also that I would eventually reach home and not somewhere else.

PS: I must say this is turning out to be one of the better threads on this forum! Thanks to Sanket for provoking the right questions that makes talking about proofs interesting. An applause for you!

[Nirav]

Nirav

Nirav

Show Nirav's last posts.

Show general stats for Nirav.

• 
• Newbie
• Karma: 2
• Posts: 6

Are there any proofs without having Closed World Assumption? How do we prove any thing without CWA?

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Proving things without CWA is not possible in the conventional sense of mathematical proof. For instance, when someone builds a bridge, he can never "prove" that the bridge will withstand any kind of challenge whatsoever.

The way we go about providing guarantees (let me not use the term "proof") for open-world systems is basically two fold: one is to use a probability distribution to indicate what will be the expected behaviour of the system in general; the second is to use a notion of "bisimilarity" -- that is, we show that our system has provable properties w.r.t. some abstract infinite state space, until a finite depth. So, as long as the system is operated within this depth, we have provable behavioural guarantees. The latter is more or less what is done by aircraft manufacturers. Software written for crucial avionics are provably correct as long as the external parameters are within acceptable limits.

[mandar]

mandar

mandar

Show mandar's last posts.

Show general stats for mandar.

• 
• Global Moderator
• Newbie
• Karma: 2
• Posts: 36

A very elegant proof indeed! Brings a smile to your face automatically. As Sids said, the clarity of thought is amazing.

Another elegant proof that I have come across recently is of the divergence of the infinite harmonic series. (Some of you may have read about it on my blog earlier.)

Consider the infinite harmonic series 1 + 1/2 + 1/3 + 1/4 + 1/5 + ...

To prove: The above series diverges.

As n tends to infinity, the n^th term in this series tends to 0. Therefore, as more and more terms are considered, smaller and smaller values are added to the running total of the series. This might lead us into believing that the series actually converges to a finite value. But it is not so!

The following proof is due to Nicole d’Oresme, a French scholar (c. 1323 - 1382).

Beginning with the third term, let us start grouping the terms of this series into "chunks" as follows: (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + (1/9 + 1/10 + 1/11 + 1/12 + 1/13 + 1/14 + 1/15 + 1/16) + ... and so on.

The first chunk has 2 terms, the second chunk has 4 terms, and so on. Generally speaking, the n^th chunk has 2ⁿ terms.

Since the series is infinite, it is possible to group its terms into infinitely many chunks.

d’Oresme observed that the sum of each of these chunks is greater than 1/2. How?

The number of terms in the n^th chunk is 2ⁿ. Replace all terms of this chunk with its smallest term. The smallest term of the n^th chunk is 1/2ⁿ⁺¹. Therefore, the sum of this chunk is now (1/2ⁿ⁺¹ + 1/2ⁿ⁺¹ + ... 2ⁿ times) = 2ⁿ/2ⁿ⁺¹ = 1/2. Hence, with the original terms, the sum of the chunk must be greater than 1/2.

[Example: (1/9 + 1/10 + 1/11 + 1/12 + 1/13 + 1/14 + 1/15 + 1/16) is the third chunk. Replacing all terms with the smallest term, i.e. 1/16, we get (1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16 + 1/16) = 1/2.]

Hence the series must diverge!