0
$\begingroup$

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?

$\endgroup$
5
  • 7
    $\begingroup$ 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. $\endgroup$
    – Henry Cohn
    Mar 26, 2013 at 17:38
  • 1
    $\begingroup$ 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.) $\endgroup$ Mar 26, 2013 at 17:42
  • $\begingroup$ 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. $\endgroup$ Mar 26, 2013 at 17:50
  • $\begingroup$ @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. $\endgroup$ Mar 30, 2013 at 16:31
  • 1
    $\begingroup$ @St Georg: Editing questions well after they have been asked and answered is unproductive, especially if the edit is minor. $\endgroup$ Nov 12, 2013 at 8:27

2 Answers 2

9
$\begingroup$

(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.

$\endgroup$
13
  • 2
    $\begingroup$ This answer convinced me not to vote to close the question. $\endgroup$ Mar 26, 2013 at 18:54
  • $\begingroup$ >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 $\endgroup$ Mar 26, 2013 at 19:38
  • $\begingroup$ @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 $\endgroup$ Mar 27, 2013 at 2:35
  • $\begingroup$ 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!) $\endgroup$ Mar 27, 2013 at 2:36
  • 1
    $\begingroup$ I'm sorry, I still don't know what that means. Does $10^{10^{10000}}$ "really exist," given that it's far larger than the number of atoms in the universe? Does Ackermann's number? How about a model of the theory of the natural numbers with successor (so no + or $\times$ - in particular, I don't believe anyone claims this theory is inconsistent)? I really don't know what "exist as real infinite physical object or infinite physical process" means. (Also, in light of this I am now confused about what "real-life infinite sets" means, in your second-most-recent comment.) $\endgroup$ Mar 29, 2013 at 17:11
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Andrej Bauer. >but "really exist" might mean "exists constructively". Well. Thus "really exist" completely depend on logic. $\endgroup$ Mar 28, 2013 at 15:31
  • 3
    $\begingroup$ I really do not understand your comment at all. $\endgroup$ Mar 29, 2013 at 5:36
  • $\begingroup$ 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". $\endgroup$
    – user42090
    Nov 12, 2013 at 8:39
  • $\begingroup$ 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$. $\endgroup$
    – user42090
    Nov 12, 2013 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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