“Complete” in logic means many different things. For instance, the “complete” in Goedel’s completeness theorem and Goedel’s incompleteness theorem are referring to different concepts.
The idea of “truth” hinges on two specific concepts:
Coherence - Are the assertions I make or the things I believe internally consistent?
Correspondence - Is there an adequate relationship between my assertions/beliefs and the physical world?
Logic deals exclusively with the coherence of assertions, while empiricism is the method used to verify correspondence. While some knowledge relies more on one concept than the other (e.g. the truth of mathematics is heavily verified by its coherence, while something like the results of a scientific experiment derives its truth more from correspondence), any “interesting” assertion usually must pass both tests–or at least plausibly explain why it fails one or the other.
Care to elaborate in this point?
The completeness theorem shows that, in FOPL, all semantic truths are provable and that all provable theorems must be semantically true.
The incompleteness theorem shows that for a logic capable of doing arithmetic, some statements must be semantically true but unprovable.
Yes, in a sense they’re the same concept, even though people, for whatever reason, tend to think of them differently. How you describe the situation just depends on the semantics you pick. If you only allow models of arithmetic theories which use the “actual” natural numbers, there will be semantically validated statements which aren’t not provable [if your theory is arithmetically definable (for example, if it is computably axiomatized), and your logic includes negation]. But if you allow more general models in your semantics, those non-provable statements will not be semantically valid.
Incidentally, for what it’s worth, I hate the tying of Goedel’s incompleteness theorem to arithmetic, when it really has nothing fundamentally to do with arithmetic; that just happens to be one context in which it can be encoded. But I’ll save that rant for another day.
Sorry for the overnegation
Hmm, the way I heard the story is that Gödel’s incompleteness theorem is about syntactic completeness, i.e. the question of whether or not either every formula or its negation is provable in some theory, while his completeness theorem is about semantic completeness, i.e. whether or not all and only the tautologies are derivable. So there are theories that are semantically, but not syntactically complete, no?
Both are about whether a syntactic notion of completeness matches up with a semantic notion of completeness.
But the completeness theorem is about the syntactic system of first-order logic and the semantic system of first-order models.
While the incompleteness theorem is about the syntactic system of first-order arithmetic* and the semantic system of “true arithmetic*”.
[*: As usually presented, though, as I said, construing it as about arithmetic (and, even more specifically, natural numbers without a stipulated ability to define functions by recursion but with the stipulated special cases of addition and multiplication) annoys me; still, I’ll say it this way for now]
Or, rather, to make the analogy more forceful, let me word it this way:
The completeness theorem is about the syntactic system of first-order logic, and the semantic system of first-order structures. [Of which there happen to be very many]
The incompleteness theorem is about the syntactic system of first-order logic + arithmetic on the natural numbers, and the semantic system of first-order structures of arithmetic on the natural numbers. [Of which there happens to be only one]
Though, since it hasn’t been said, let me also say explicitly what Capt. Ridley’s Shooting Party was saying:
People often read “completeness” in GIT as meaning the purely syntactic property “For every statement, either it or its negation is provable”.
This is a completely different concept from the “completeness” in GCT.
What I’ve been noting is that, in the context of theories of natural number arithmetic, “For every statement, either it or its negation is provable” is equivalent to the appropriate semantics-syntax bridge property “Every statement validated by natural number semantics is provable”.
So you could come at GIT that way, or this way, and consider it perfectly analogous, or not analogous, to the investigation in GCT, depending on how you’re looking at it.
Oh, sorry, Half Man Half Wit did say that explicitly… I somehow skipped right over that.
Agreed. I was merely pointing out that logic is an a posteriori truth, not an a priori truth.