First order logic: Soundness, Completeness, Decidability

**master_coda** · Dec13-05, 09:09 PM

Originally Posted by VazScep

The second-order predicate calculus is incomplete (under standard semantics), so there is no such thing as a consistent second-order recursively axiomatisable theory.

That's a very good point, of course. I'm not too familar with the middle ground between first-order logic and second-order logic, or else I would've tried to pick something between the two.

**master_coda** · Dec13-05, 09:22 PM

Originally Posted by VazScep

I only said "indicates". If you want to find out the way that truth is defined for interpretations, I can recommend some logic textbooks -- the definitions are quite long-winded.

The monadic predicate calculus (the predicate calculus in a language with only one-place predicates) is decidable but incomplete.

Well, I'll take your word for it then. I am not a logician, it's entirely possible that I may be talking out of my *** without even knowing it. Fortunately, this is not my day job.

**Hurkyl** · Dec13-05, 09:44 PM

Hurkyl's definition of a truth valuation looked an awful lot like "assign P a value of true if P is derivable from the axioms of the theory". In that case, I don't see how "P is true in this theory" and "P is provable from the axioms in this theory" are any different.

You do have this theorem:

If a statement P is true in every model of a (first-order) theory, then P can be proven from the axioms.

**AKG** · Dec13-05, 09:54 PM

Originally Posted by VazScep

For the Incompleteness Theorem to apply, N also has to prove a sufficient amount of arithmetic (it must prove enough statements true in the standard model).

Why? If a system that is strong enough to prove certain arithmetic facts still can't prove all true statements, then certainly a weaker system that can't even prove those arithmetic facts can't prove all true statements. The proof of the theorem requires that N proves certain arithmetic facts, but once we have the theorem, then it follows that weaker axioms (that can't even prove basic arithmetic facts) will also be incomplete.

**Hurkyl** · Dec13-05, 10:07 PM

If a system that is strong enough to prove certain arithmetic facts still can't prove all true statements, then certainly a weaker system that can't even prove those arithmetic facts can't prove all true statements.

Sure, there will be statements the weaker system cannot prove.

However, the weaker system will not even be able to say those statements.

The great example (IMHO) is the theory of real closed fields. It is logically complete, despite the fact any real closed field is a ring containing the integers!

The resolution of this pseudoparadox is that while any real closed field contains the integers, the theory of real closed fields has no way of actually talking about integers.

This fact has an algebraic interpretation: any polynomial that is zero at every integer must, in fact, be zero everywhere. Thus, there is no algebraic expression capable of identifying the integers.

So while you can ask if an equation has a solution, you cannot ask if an equation is an integer solution.

**VazScep** · Dec14-05, 06:45 AM

Originally Posted by master_coda

Well, I'll take your word for it then. I am not a logician, it's entirely possible that I may be talking out of my *** without even knowing it. Fortunately, this is not my day job.

Just to correct something Hurkyl wrote earlier, truth is not defined with respect to any set of axioms or any theory. It is defined with respect to an interpretation of a formal language. For instance, suppose the given formal language consists of the predicate symbol

and the constant symbol

. An interpretation of this language is a set of objects, called the domain, an assignment of a one-place relation

to the symbol

, and an assignment of an object in the domain

to the symbol

. An atomic formula like

will then be defined to be true for this interpretation if and only if $LaTeX Code: C\\in R$ .

Obviously, a lot more work is needed to define truth for a general formula in the language, but the point is that all this is done without reference to axioms or particular theories. And you should be able to see from this that provability and truth are distinct concepts. For instance, in the theory with only logical axioms (the predicate calculus)

is unprovable, but in any interpretation of the language, it will have a definite truth value.

**asdf60** · Dec14-05, 10:23 PM

I don't understand much of what all of you said, but it seems that my book says that the key to the difference between undecidability, is that while we can prove any formula that we KNOW to be valid (that is to say, the formula is logically true- in every interpretation), we can not know where a given formula is valid in a FINITE number of steps. If we try constructing a proof via top-down derivation or deductive systems, we aren't guarenteed a counter example, so we never know if the proof is just about to come around the corner.

For example, propositional logic is decidable, because it will be at most 2^n tests for each formula containing n variables.

Is this right in anyway?

**asdf60** · Dec14-05, 10:28 PM

I think i'm convincing myself more and more that undecidability deals with a formula in a specific interpretation, it doesn't deal with logically true statements. This seems to me very reasonable. If I had an infinite universe of discourse, and formula making some existential claim, then it seems reasonable that it would be impossible to either produce a counterexample or a proof. And completeness, in this case, does not guarantee that a proof should exist, since the formula is not a logical truth.

**AKG** · Dec15-05, 12:00 AM

Unless you're using "decidability" to mean something else, it has nothing to do with truth or interpretations. A set of axioms is decidable iff there is an ideal computer with an algorithm that can decide whether a given formula is in the set or not in the set. This has nothing to do with whether the formulas are true, or true in a given interpretation, or whether or not they are provable, etc.

**asdf60** · Dec15-05, 12:09 AM

You're right. My book is very misleading. Thanks for the help.

**VazScep** · Dec15-05, 05:28 AM

Originally Posted by asdf60

You're right. My book is very misleading. Thanks for the help.

Generally, a set is decidable if there is an algorithm to determine whether an object belongs to that set or not. A theory is a set of formulas, so we can say that a theory is decidable if there is an algorithm to determine whether a formula belongs to that theory or not. We can also say that a set of axioms is decidable if there is an algorithm to determine whether a given formula belongs to that set.

Another meaning of decidable applies to formulas: A formula $LaTeX Code: \\phi$ is decidable for a theory if the theory contains $LaTeX Code: \\phi$ or $LaTeX Code: \\neg\\phi$ . So we can say that a theory is complete (syntactically, in the sense meant by Godel's Incompleteness Theorems) if it contains no undecidable formulas.

**asdf60** · Dec15-05, 03:19 PM

Hmmmm. What about this question.

Suppose a universe with exactly five elements. A set is definied by a formula A, and it turns out that the set has exactly 3 elements. Consider the set defined by -A (negation of A). Does this set have exactly 2 elements?

**VazScep** · Dec15-05, 03:44 PM

Originally Posted by asdf60

Hmmmm. What about this question.
Suppose a universe with exactly five elements. A set is definied by a formula A, and it turns out that the set has exactly 3 elements. Consider the set defined by -A (negation of A). Does this set have exactly 2 elements?

Are you asking this to clarify my last post? What do you mean by a set defined by a formula, or a set defined by the negation of that formula?

**asdf60** · Dec15-05, 03:49 PM

I'm trying to get a concrete example.

By set defined by a wff, i mean, the wff has one free variable, so any substitution of the free variable by an element of the universe that makes the wff true belongs to the set being defined.

**VazScep** · Dec15-05, 04:01 PM

Originally Posted by asdf60

I'm trying to get a concrete example.
By set defined by a wff, i mean, the wff has one free variable, so any substitution of the free variable by an element of the universe that makes the wff true belongs to the set being defined.

Okay. In that case, the negation will define the complement of the first set, which will have two elements. I'm not sure what this is a concrete example of though.

**asdf60** · Dec15-05, 04:06 PM

Okay.
I guess the question is, is it possible that one of the sentences is (that is, the wff substituted with an element) is undecidable, meaning it is neither true or false.
If I understand correctly, it's not possible, because that's not what undecidability says.
So to clarify, given a full model/intepretation, it is always possible to verify whether a given sentence is true in the model. And if it isn't true, then it's negation is.
Is this correct?