3 ms·

Think of it kind of like the Sieve of Eratosthenes, but for provability instead of primeness. You start with one axiom and prove everything you can based on tha

Think of it kind of like the Sieve of Eratosthenes, but for provability instead of primeness. You start with one axiom and prove everything you can based on that. Then you pick one of the statements you couldn't prove and add it as a second axiom (thereby expanding your axiomatic system), then prove everything that you can with those two axioms. The pick another unproven statement as your third axiom and repeat. Godel's incompleteness theorem is equivalent to saying that you will never run out of axioms, and that you will be able to continue this process indefinitely (just like there are an infinite number of primes). It's not an exact comparison, but it gives you the idea.

bjornsing 15y ago
An interesting comparison. Just one important difference though if I understand correctly: In Gödel's world you will sooner or later ruin your axiomatic system by adding an axiom that is inconsistent with one or several of your earlier axioms. There's no way to know (from within the system) when that happens, except perhaps that it gets a whole lot easier to prove weird stuff. :)
- rcthompson 15y ago
  I guess I should have said that you pick as your new axiom a statement that you couldn't prove and also couldn't disprove. Though I'm not sure if even that is the same as logical independence, which is what you really want.
xyzzyz 15y ago
I think your comparison misses an important point. If you pick in every step a sentence that is non-provable from your current axioms, but not contradictory with them either, after infinitely many steps[1] you will have picked all of them, and get a system called True Arithmetic, in which every true sentence is provable, essentially by definition. The reason why Goedel's incompleteness theorem does not work here is that your set of axioms is not recursively enumerable, and this is a necessary assumption of GIT. [1] - If "after infinitely many steps" sounds fishy to anyone, please keep in mind that you start with an infinite list of axioms anyway -- first order Peano arithmetic theory has an induction axiom schema Ind that basically says that for every sentence f, Ind(f) (the sentence you get by substituting every occurrence of a single free variable in Ind with f) is an axiom of PA.
- rcthompson 15y ago
  The "infinitely many steps" does sound fishy to me, because I wonder whether the number of axioms in True Arithmetic is countably infinite or uncountably so, and whether it makes a difference (I think it does). But yes, the comparison is an analogy, certainly not correct at every level.
  - xyzzyz 15y ago
    The set of all statements is easily seen to be countable, so the subset of statements being true, being infinite, is countable as well. It does not make any difference, though, since what matters here is, as I said, recursive enumerability of axioms. Anyway, transfinite induction lets one use "pick next element" arguments even on uncountable sets.

bjornsing 15y ago

An interesting comparison. Just one important difference though if I understand correctly: In Gödel's world you will sooner or later ruin your axiomatic system by adding an axiom that is inconsistent with one or several of your earlier axioms. There's no way to know (from within the system) when that happens, except perhaps that it gets a whole lot easier to prove weird stuff. :)

rcthompson 15y ago
I guess I should have said that you pick as your new axiom a statement that you couldn't prove and also couldn't disprove. Though I'm not sure if even that is the same as logical independence, which is what you really want.

xyzzyz 15y ago

I think your comparison misses an important point. If you pick in every step a sentence that is non-provable from your current axioms, but not contradictory with them either, after infinitely many steps[1] you will have picked all of them, and get a system called True Arithmetic, in which every true sentence is provable, essentially by definition. The reason why Goedel's incompleteness theorem does not work here is that your set of axioms is not recursively enumerable, and this is a necessary assumption of GIT. [1] - If "after infinitely many steps" sounds fishy to anyone, please keep in mind that you start with an infinite list of axioms anyway -- first order Peano arithmetic theory has an induction axiom schema Ind that basically says that for every sentence f, Ind(f) (the sentence you get by substituting every occurrence of a single free variable in Ind with f) is an axiom of PA.

rcthompson 15y ago
The "infinitely many steps" does sound fishy to me, because I wonder whether the number of axioms in True Arithmetic is countably infinite or uncountably so, and whether it makes a difference (I think it does). But yes, the comparison is an analogy, certainly not correct at every level.
- xyzzyz 15y ago
  The set of all statements is easily seen to be countable, so the subset of statements being true, being infinite, is countable as well. It does not make any difference, though, since what matters here is, as I said, recursive enumerability of axioms. Anyway, transfinite induction lets one use "pick next element" arguments even on uncountable sets.