3 ms·

I mean, yeah? It's still true you don't need to prove the composite case separately if you structure it a little different. Plus the original comment was clearl

• Tainnor 5y ago
  There is no induction involved (I mean, yes, for some of the lemmas about divisibility, probably you'll need induction, but not for the main proof).
  • ravi-delia 5y ago
    Oh I see! I was talking about bootstrapping from "there's always another prime" to "there's a countably infinite number of primes", but you can just piggyback off the naturals.
    • Tainnor 5y ago
      Well, I suppose it matters which definition of "infinity" you want to use. The modern definition of an infinite set is that it's a set for which there exists an injection into the natural numbers. But that definition brings you into the territory of set theory, which seems unnecessarily complex when you're just trying to prove something about arithmetic. Euclid's original proof of the theorem is of the form "for any list of primes, I can find an additional prime" [0], and for good reason: in Ancient Greece, thinking of infinity, or infinite sets, as a concrete object that you could manipulate would have seemed weird. But the proof variant where you produce a contradiction doesn't really get into the set-theoretic details either. All it does is say: "Assume there is a finite list of all primes. Derive a contradiction. Therefore there is no such list." That's pretty much equivalent to the direct proof, it's just using different logical inference rules. [0]: http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX...