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.

Can an axiomatic system (which is capable of expressing arithmetic) be complete and consistent?

Let me explain my motivation a little bit (though it can be a kind of a mess...) I'm aware of Goedel's Theorems, and I started thinking about this question when I happened to read about the so-called "true arithmetic". Well, assuming Peano arithmetic is consistent (if we accept that the natural numbers structure is its model), we can take all statements which hold in this model as axioms (which will contain PA), can't we? And this system will be consistent and complete (and not decidable)? How about proving its own consistency? Can it even express it? I read Goedel's original work and there the statement of consistency is formalized as $\exists x [Form(x) \land \lnot Bew(x)]$ (1) which means that there exists some formula $x$ (this is expressed by $Form(x)$) which is not provable ($\lnot Bew(x)$) (though, roughly speaking, the same can be of course said about any set of sentences - it is consistent if and only it doesn't prove everything). So what I am trying to make sense of, is it that this "true arithmetic" can't even express its consistensy in the form (1)? Is it simply a statement we know about this system on the basis of, say, $ZF$?

share|improve this question
add comment

3 Answers

Given a formula, you are unable to verify if it is an axiom.

share|improve this answer
add comment

This isn't really an answer, but more like a really long comment.

Firstly, note that yes, "true arithmetic" can be defined inside set theory, but from outside, we notice that each model of (first-order) set theory has its own version of true arithmetic, and these needn't be 'isomorphic.' So, we can talk about "true arithmetic" without being forced into believing that there exists a true true arithmetic, in the philosophical sense.

Secondly, yes you're right that set theory proves that true arithmetic is consistent and complete (and trivially, that it is sound!). Set theory also proves Goedel's first (and second!) incompleteness theorem, which implies that true arithmetic is not recursively ennumerable. So if you believe in a true true arithmetic, and if you believe that set theory is "trustworthy" with respect to this true true arithmetic, then you should believe that your true true arithmetic is not recursively ennumerable.

Thirdly, I have heard Goedel's theorems used to argue that there is no true true arithmetic. This is a complete reinterpretation of their significance! I do not know if this a philosophically coherent position, though.

Fourthly, note that although set theory proves that true arithmetic cannot be recursively ennumerated, it also proves that the diagram of arithmetic can be. The diagram consists of sentences like $3+2=5$ and $3+2 \neq 6$, so this is certainly reassuring.

Finally, most of what I know about this topic has been gleaned from Wikipedia and by asking bazillions of questions here at math.stackexchange, so some of what I just wrote is probably wrong. If you're looking for more information on these ideas, Peter Smith's book on the issue is reading quite nicely so far (but I'm only about 1/4 of the way through), and I'd definitely recommend it.

share|improve this answer
    
@AlexWhite and if you're lucky Peter will answer your question himself. –  Trismegistos Aug 2 '13 at 7:06
    
@Trismegistos Does he visit this site? :) –  W_D Aug 2 '13 at 7:48
add comment

A theory $\mathbb{T}$ is inconsistent if all well-formed formulae are derivable in $\mathbb{T}$; otherwise it is consistent. A theory $\mathbb{T}$ is complete if $\mathbb{T}$ is consistent and, for all well-formed formulae $\varphi$, either $\varphi$ is derivable in $\mathbb{T}$, or $\mathbb{T} \cup \{ \varphi \}$ is inconsistent. These are notions that makes sense for any theory, whether or not it has the expressive power of arithmetic.

Now let $\mathbb{T}$ be the first-order theory of "true arithmetic", i.e. all sentences which are true in the standard model of arithmetic.

  1. $\mathbb{T}$ is consistent, because $0 = 1$ is not derivable in $\mathbb{T}$. (Assuming the rules of inference are sound, of course.)
  2. $\mathbb{T}$ is obviously complete.
  3. $\mathbb{T}$ is not recursively (i.e. computably) axiomatisable, because if it were, it would contradict Gödel's incompleteness theorem.
  4. Actually we can say more: there does not exist a "reasonable" coding scheme and a well-formed formula $A (x)$ with one free variable $x$ such that $A (n)$ holds if and only if $n$ is a code for an axiom of $\mathbb{T}$ (i.e. a sentence that is true in the standard model of arithmetic). This is Tarski's undefinability theorem.

Thus, it is indeed impossible to formulate in the language of arithmetic the notion that $\mathbb{T}$ is consistent. But that's just a defect of $\mathbb{T}$: for example, one can still talk about the consistency of $\mathrm{PA}$ in the language of arithmetic and the formal statement $\mathrm{Con}(\mathrm{PA})$ is derivable (indeed, is an axiom) in $\mathbb{T}$.

share|improve this answer
    
Your first paragraph about inconsistency and completeness is not true for all logics. It is true for classical logic but not for constructive logic. –  Trismegistos Aug 2 '13 at 7:14
    
Those are definitions, not statements. –  Zhen Lin Aug 2 '13 at 7:15
    
@Trismegistos Is this constructive logic somehow related to the so-called inconsistent logic? –  W_D Aug 2 '13 at 7:54
    
@ZhenLin Those were statements which are consequences of proper definitions. In fact you can treat those statements as definitions in FOL. –  Trismegistos Aug 2 '13 at 10:06
    
I've replaced the definition of completeness with another one. Perhaps this one is more to your liking, but it is equivalent to the one I gave before even for intuitionistic logic. –  Zhen Lin Aug 2 '13 at 10:54
show 2 more comments

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.