Sitting at home with a cold, tired of watching TV and playing video games, stumbled upon…
A great theorem from math history
-
Follow
Following
Already have a WordPress.com account? Log in now.
Sitting at home with a cold, tired of watching TV and playing video games, stumbled upon…
Denise Gaskins' Let's Play Math 
Why did you have to use the argument by contradiction?
Could not you just show that for any finite collection of primes there is a prime that is greater than all of them, by the very same argument that you used? That would be enough to demonstrate the infinitude of primes, right?
The other two videos are really cool and funny, thumbs up for those!
I think Meep used reductio ad absurdum because (1) that is the method Euclid used, and (2) it is a method that students find counter-intuitive, so they need to see it in action.
Is it possible to show that “for any finite collection of primes there is a prime that is greater than all of them,” without first assuming that there is a greatest prime number? What Euclid actually proved was that for any finite set of primes, there is at least one prime that is not in the set — but not necessarily that it is larger than the ones in the set.
For instance, if your collection of primes was {2, 7}, then 2×7+1=15 is not divisible by either 2 or 7. It must either be prime itself, or it must be the multiple of some prime number(s) which you haven’t collected yet.
Denise, the excuse (1) looks reasonable to me, it would have looked even more reasonable if Meep had mentioned it to justify her choice. The excuse (2) doesn’t hold water at all, since there are plenty of other opportunities to use arguments by contradiction elsewhere.
Yes, it is possible. Take Q=P!+1, where the P is the biggest prime of our finite collection. Then Q is either a prime or it is divisible by a prime D that must be greater than P because Q is not divisible by P or any smaller number. This is exactly the argument Meep used. Her original assumption that the TOTAL number of primes is finite is superfluous.
So a streamlined argument could be the following. Take any number A. Then A!+1 is either prime or is divisible by a prime B that must be greater than A. Therefore the collection of all primes can not be finite.
Denise, Euclid did not use an argument by contradiction. He proved, as you said, “that for any finite set of primes, there is at least one prime that is not in the set,” and he concluded directly, without invoking any argument by contradiction: “Therefore, prime numbers are more than any assigned multitude of prime numbers.” His “assigned multitude” is what we mean today by “a finite collection.”
@anonymous—
There are other places to use it, too, but why not here? My students have always needed to see lots of examples of proof by contradiction. They find it ever so hard to take that first step and assume the opposite of what they are trying to prove.
As for the proof, you are right. I was mixing up Meep’s proof and Euclid’s in my mind. Euclid did not use anything like the concept of factorial, so using his proof, the new prime is not guaranteed to be larger.
@mathfoolery—
It seems to me that Euclid used contradiction: “I say that G is not the same with any of the numbers A, B, and C. If possible, let it be so. Now A, B, and C measure DE, therefore G also measures DE. But it also measures EF. Therefore G, being a number, measures the remainder, the unit DF, which is absurd.” Am I misreading that?
@Denise–“… why not here?” It looks rather artificial and contrived, because the direct argument is simpler, and in fact is a part of the indirect argument. Ontologically speaking, all the indirect arguments are based on the assumption that there are no contradictions in mathematics, which is still unproven and probably will never be proven, people just believe in it. Relying on this kind of wishful thinking when a direct argument or a construction is available is a bit strange. It’s like saying “let’s assume the theorem is wrong,” then proving the theorem and calling it a contradiction, instead of just proving a theorem, and that’s how Meep’s approach sounds.
Yes, Euclid uses a contradiction when he proves that ABC+1 is not divisible by A, B or C, but we can do without it. He needed this trick because he thought geometrically.
Wishful thinking? I guess that makes sense, and makes a good reason not to use it — at least, not in an upper-level course. I still think it may have value as a demonstration of reductio ad absurdum at the pre-algebra or algebra 1 level.
At any rate, I can see you are both right that the direct proof works. As anonymous showed, one doesn’t even have to start with a prime number. (Hmmm. I wonder what my geometry students would think of constructing a factorial as a measured length…)
Anonymous and I are the same. The situation with indirect reasoning is even worse than relying on absence of contradictions. It also relies on the excluded middle principle which is somewhat shaky, too. Is any statement either true or its negation is true? I don’t know, it’s not clear to me. It is not obvious at all, and the more examples you think about, especially the ones that involve some infinite sets, the less plausible it looks. Sort of depressing… I think children demonstrate a very good common sense when they instinctively perceive indirect arguments as somewhat unnatural and not very convincing.
Constructing a factorial… It grows like crazy. Anyway, I think the original Euclid text is great. You should show it to your students and tell them to ignore the Guide remarks, or still better, edit them out. You can always tell a writing of a great mathematician from a writing of an average one 🙂
“Constructing a factorial… It grows like crazy.” That’s what I thought would be fun about it — start at one end of the room and see how many steps it takes to cover the length of the chalkboard.
We only have two class sessions left in our co-op semester. Our textbook is working on similar figures, but we may just devote the rest of our class time to constructions.