0

Can we determine if a logic system is incomplete? Let's say because I don't really have a good definition of what complete is that a complete logical system can be used as a foundational ground to build a physics model to simulate reality. You can assume the definition to be more general if you can come up with one, but using this definition can you say that certain logic system doesn't pass the completedness test?

Take for example a logic system with only one rule. The rule is A = A or not A. With something like that, I don't think we can do much of anything. We need more rules. So is there a process that can be used to determine if a logic system is complete?

Improve this question
5
  • No. We can compare some logics by expressive power, predicate logic (FOL), for example, is more expressive than propositional one, although it is odd to apply the term to logics rather than languages, see Kocurek, Measuring the Expressive Power of Languages. But we do not know how much (and what kind of) expressive power it would take to "simulate reality" so we cannot tell, in general, whether logic (or language) is "complete" for that or not. Commented Sep 27, 2023 at 23:40
  • 2
    You're confused, A = A is not a rule of any variant of well-known propositional logics, modus ponens is a famous rule, for example. If your system removes MP but not its semantic counterpart aka deduction theorem, say, then it becomes incomplete immediately... Commented Sep 27, 2023 at 23:52
  • It seems that you are using "incomplete" in a broad sense (see also the the "metaphysics"). In modern math logic we formalize math theories using the inferential engine provided by logic, e.g. f-o predicate logic and we apply it to a formalized math systems based on axioms. Thus, we may approach "completeness" in two steps. Commented Sep 28, 2023 at 7:00
  • 1. is the logical engine "complete" in the sense that its rules (that are sound) are enough to ensure logical consequence? For FOL the answer is YES: Godel's Completeness Th. This means that, wrt a formalized math theory, we are able to derive as theorems all formulas that are log cons of the axioms. Commented Sep 28, 2023 at 7:04
  • 2. are the axioms of a formalized math theory enough to "decide" every problem expressible in the language of the theory. For certain specific formalized theory, the answer is NO: Godel's Incompleteness Th. Commented Sep 28, 2023 at 7:06

3 Answers 3

Reset to default
4

In the context of formal logic, completeness has more than one meaning, and from your example I'm not sure which is closest to what you mean. These are the main ones:

Functional completeness. In the context of classical propositional logic, a set of connectives is said to be functionally complete, or expressively adequate, if all truth-functional connectives can be defined in terms of them. A logic that contains only disjunction and identity, like your example, would be incomplete by this definition, since it would not be able to express all the boolean functions. Emil Post proved which sets of connectives are functionally complete for propositional logic. The expressive power of more powerful logics is not so easily described and measured. First order logic seems to be adequate for expressing most theories in physics.

Semantic completeness and strong completeness. Semantic completeness is a relation between a deductive system and some semantics: usually a formal semantics such as model theory. Completeness in this sense is the converse of soundness. A deductive system is sound if every formula it proves is a validity of the semantic system. It is complete if every validity of the semantic system is provable. This is sometimes written as follows:

If ⊢ φ    then   ⊨ φ       (Soundness)
If ⊨ φ    then   ⊢ φ       (Completeness)

Where ⊢ indicates syntactic derivability, and ⊨ indicates semantic consequence. Strong soundness and completeness is an extension of these relations to derivations from a set of premises. Gödel proved that first order classical logic is sound and complete when he did his PhD thesis. The soundness part is easy to prove; the completeness part is hard.

Syntactic completeness or deductive completeness. This is a property of a theory T, such that the addition of any unprovable sentence to it makes it inconsistent. This is roughly equivalent to saying that for any sentence φ in the language of T, T ⊢ φ or T ⊢ ¬φ. Gödel's first incompleteness theorem shows that any system of arithmetic that is consistent, axiomatisable, and at least as strong as Robinson arithmetic, is incomplete in this sense. The proof is ingenious and not too difficult to understand. There is an account of it in a freely downloadable book by Peter Smith.

Improve this answer
1

The simplest definition of system completeness is that any question asked within that system has an answer that lies within that system. So for example, the question of what is x if x^2 = 1 has an answer within the realm of the real numbers but the real number system is incomplete because it doesn't admit an answer to the question of what is x if x^2 = -1.

Improve this answer
1

The meaning of completeness I'm familiar with is that, for a system of logic, if a proposition is true then it is provable in that system.

The star of the show is ol' faithful modus ponens (the method of positing):

  1. IF p THEN q
  2. p
    Ergo,
  3. q

All other natural deduction rules appear to be either spinoffs (hypothetical syllogism) of, or designed to set up a, modus ponens (others). Is all knowledge just one big modus ponens?! It seems reasonable to say natural deduction is complete.

However, there's a cost viz. inconsistency e.g. the liar paradox is modus ponens from start to finish. Gödel was right, completeness OR consistency, but not both!!!

Improve this answer

You must log in to answer this question.