Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Thomas Andrews Feb 20 '13 at 15:06
add comment

1 Answer 1

up vote 5 down vote accepted

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").

share|improve this answer
    
Yes, very interesting. Thank you. –  Valtteri Feb 20 '13 at 21:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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