Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $T$ be a formal theory. Suppose that $Con(T)$. Does it Godel completeness theorem confirms that the corresponding model $M_{T}$ of the $T$ really exists?

share|improve this question
6  
What do you mean by "really"? Your phrasing suggests the possibility of existing but not really existing, which sounds like more of a philosophical question about Platonism than a mathematical question. But yes, modulo issues about "really", the completeness theorem says that every consistent theory has a model. –  Henry Cohn Mar 26 '13 at 17:38
1  
The crucial point in your question on which you failed completeley to elaborate is obviously the question what do you mean when you say "really" ? In particular: Which part(s) of the proof of the completeness theorem is (are) questionable in your view? Unless you clarify your question, it does not constitute a real question for MO ;-) (And a minor point: It's not "the" but rather "a" model that exists by the completeness theorem. There is no uniqueness claim made.) –  Johannes Hahn Mar 26 '13 at 17:42
    
I think that Jaykov definitely needs to elaborate on what (s)he means, but I also think that there is a real question lurking here - something along the lines of "what commitments do we need to make in order to be certain that the Completeness Theorem 'means' the right thing?" In general, unraveling precisely what results in logic mean can be tricky, and I think this question, though borderline, can become appropriate. –  Noah S Mar 26 '13 at 17:50
    
@Henry Cohn Thanks! Statement "Consistent theory T" has a clear substantial sense and it means that on any step of the proof we cannot prove the formula 1=0. But construction of proofs is real physical process and for example, if "10 ^ {10 ^ {10000} exists" has not the same substantial sense as well as "2 exists" then and statement Con (T) obviously has not any sense. –  Jaykov Foukzon Mar 30 '13 at 16:31
1  
@St Georg: Editing questions well after they have been asked and answered is unproductive, especially if the edit is minor. –  Noah S Nov 12 '13 at 8:27
add comment

2 Answers

up vote 8 down vote accepted

(For simplicity, I assume all languages and theories are countable.)

I'm not sure what "really exists" means; Godel's theorem says that a model of $T$ exists whenever $T$ is consistent.

If by "really exists" you mean "exists in some constructive sense," then the answer is: sort of. There are consistent, computable theories with no computable model (e.g., PA + a nonstandard integer - see Tennenbaum's Theorem; or $ZF$ (and, I suspect, every natural set theory) - see Is there a computable model of ZFC?), but every consistent theory $T$ does have a model which is low with respect to $T$; in particular, such a model is computable from $T'$, the Turing jump of $T$, which is nicely definable. If you accept operations as complicated as Separation and Replacement, then you should certainly accept the existence of models of consistent theories (unless your underlying logic is not classical, in which case I have nothing useful to say, although Andrej Bauer probably does).

Let me elaborate a bit on why having computationally simple models is relevant. It's not just that such models are "less complicated" than standard set-theoretic constructions, as I state above; it's that we don't even need to talk about set theory, at all, to get them! The models in question are uniformly computable in the jump of $T$; that is, there is a single $e\in\omega$ such that for all theories $T$, either $\Phi_e^{T'}$ codes a model of $T$, or $\Phi_e^{T'}$ codes a proof of $\exists x(x\not=x)$ from $T$. So if we believe that jumps of arbitrary sets of natural numbers "really exist" - that is, if we believe that statements of the form $\exists n\phi(n)$ are meaningful whenever $\phi$ is meaningful - then we have to believe that consistent theories have models. It is definitely possible to be skeptical of the meaningfulness of arbitrary arithmetic statements, but at that level of skepticism it seems like classical logic is the "wrong" tool, so all the questions/theorems look different anyways. I'm pushing this point because I suspect your question is coming from a skepticism towards set theory - which I consider entirely healthy! - and I want to argue that no set theory is needed to believe in models.

Please let me know if this addresses your question. I would suggest, though, that you explain a bit what you mean.

share|improve this answer
2  
This answer convinced me not to vote to close the question. –  Steven Landsburg Mar 26 '13 at 18:54
    
>Let me elaborate a bit on why having computationally simple models >is relevant. It's not just that such models are "less complicated" >than standard set-theoretic constructions, as I state above; it's >that we don't even need to talk about set theory, at all, to get >them! The models in question are uniformly It agree.But nevertheless there are known mathematicians which think that such constructive process will suffer contradictions web.math.princeton.edu/~nelson/papers/warn.pdf –  Jaykov Foukzon Mar 26 '13 at 19:38
    
@Steven: Thanks! @Jaykov: there are, I believe, two parts to Nelson's skepticism: the belief that exponentiation is not consistent (specifically, that an appropriate weak base theory proves that $2^x$ is not total), and the belief that infinite sets are meaningless (ultrafinitism). The latter is so strong, it sees statements like "ZFC is consistent" as being meaningless; so I think you probably don't want to adopt that level of skepticism, if this is the question you're asking. The former is actually relatively benign in this context, and can coexist with the belief that existential statements –  Noah S Mar 27 '13 at 2:35
    
are meaningful, and so doesn't really argue against the completeness theorem. Bottom line, I believe, is this: do you use classical logic, and believe that $\Sigma^0_1$ statements are meaningful? Then you ought to believe that if ZFC is consistent, it has a model. If you don't, then at some level you must be rejecting infinite sets, which is fine, but that throws into question what you mean when you say "Suppose that Con(Th)." (Also, somebody please correct me if I've misrepresented Nelson's positions!) –  Noah S Mar 27 '13 at 2:36
    
> then at some level you must be rejecting infinite sets, which is fine, In it there is no necessity. Nevertheless it is possible to assume that real-life infinite sets, are not obliged to correspond to the classical logic. –  Jaykov Foukzon Mar 28 '13 at 16:44
show 8 more comments

I do not know from what angle you're coming, but "really exist" might mean "exists constructively". In this case you should look at Stefano Berardi, Silvio Valentini: Krivine's intuitionistic proof of classical completeness (for countable languages) Ann. Pure Appl. Logic 129(1-3): 93-106 (2004). Even though existence of the usual Tarski models for consistent theories cannot be proved construtively, one can still prove a slightly weaker version of completeness.

share|improve this answer
    
Andrej Bauer. >but "really exist" might mean "exists constructively". Well. Thus "really exist" completely depend on logic. –  Jaykov Foukzon Mar 28 '13 at 15:31
2  
I really do not understand your comment at all. –  Andrej Bauer Mar 29 '13 at 5:36
    
I can not understand Jaykov's comments completely but I guess he is trying to explain a difference between "theoretic" consistency of a theory and its "practical" consistency in the following sense: Assume that $ZFC$ is "really" inconsistent but the length of shortest proof to reach this inconsistency is too long (for example $10^{100}$ steps from the axioms) in this case what happens? We can work with $ZFC$ without any problem pragmatically because we will never have a contact with its inconsistency. In the other words the "really inconsistent" theory $ZFC$ "seems" consistent for "us". –  Saint Georg Nov 12 '13 at 8:39
    
But I am really suspicious to this philosophical argument because "inconsistency is a malign cancer" and spreads itself everywhere even in very small proofs. So I "believe" that $ZFC$ is "really" consistent just because we didn't find any inconsistency until now and our "short length" proofs in current mathematics are "long enough" to reach any possible inconsistency within $ZFC$. –  Saint Georg Nov 12 '13 at 8:49
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.