5
$\begingroup$

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic status and add it to $A_0$ and construct a new set of axioms $A_1$. Continue this process indefinitely. Assume we end up with a set of axioms $A_{\infty}$, that contains infinite number of axioms. Is this set effectively generated? Is this system complete? Is it consistent?

I don't know anything about these things, apart from what can be read in Wikipedia about Gödel's incompleteness theorems. Just a thought I had.

$\endgroup$
  • 1
    $\begingroup$ If you are generating the $A_i$ by a process, then you can't get completeness - there are statements that are unprovable that can't be resolved by that process. If the $A_i$ are not enumerated by a process, then they are not an effective axiom system. $\endgroup$ – Thomas Andrews Feb 20 '13 at 15:06
7
$\begingroup$

First, there is nothing unusual about having a theory with infinitely many axioms. This is the case for both of the two most commonly studied "foundational" theories, Peano Arithmetic and Zermelo-Fraenkel set theory. In both of these cases, what is often described as one named axiom (induction for PA, selection and replacement in ZF) are actually axiom schemas -- that is, each is just a recipe for generating an infinity of different axioms by plugging different logical formulas into the schema.

First-and-a-half, remember that the Gödel procedure for producing an unprovable (and un-dis-provable) statement requires not only that the axioms is effectively generated, but also that the theory is rich enough to be "interesting". (For example, the theory of integers and addition where multiplication is not mentioned is not rich enough for Gödel's construction to work on it).

Second, if your original theory $A_0$ is effectively generated, then your $A_\infty$ will be too -- there's a mechanical, deterministic process that will eventually print every axiom in $A_\infty$.

$A_\infty$ will be consistent too, if $A_0$ is -- by the "compactness" property of formal logic which says that every inconsistent system of axioms has a finite subsystem that's also inconsistent. (If there's a proof of a contradiction in the system, then because proofs are finite by definition, the proof depends on only finitely many of the axioms). Every finite subset of $A_\infty$ will be a subset of one of the $A_n$'s, and all of these are consistent by construction.

Since $A_\infty$ is effectively generated and (because it extends $A_0$) sufficiently rich, we can repeat the Gödel process on it, and get at Gödel sentence for $A_\infty$. Add that to $A_\infty$ to get $A_{\infty+1}$, and proceed ad nauseam. (In this context it is traditional to write $\omega$ instead of $\infty$, and there's a theory of the necessary numbers "beyond infinity" under the name "ordinal numbers").

$\endgroup$
  • $\begingroup$ Yes, very interesting. Thank you. $\endgroup$ – Valtteri Feb 20 '13 at 21:31
  • $\begingroup$ Since $A_{\infty+1}$ depends on infinitely many axioms, wouldn't the sentence be infinitely long and so be invalid (unlike all of $A_{\infty}$)? $\endgroup$ – Albert Hendriks Aug 18 '18 at 1:41
  • 1
    $\begingroup$ @AlbertHendriks: No, because you can write a finite program that recognizes the infinitely many axioms of the theory. The Gödel sentence is derived from an algorithm for recognizing axioms, not directly from the list of axioms themselves. $\endgroup$ – Henning Makholm Aug 18 '18 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.