Second order logic and completeness

[jordi]

Goldrei's Propositional and Predicate Calculus states (in my words; any mistake is mine) that first-order logic is complete, i.e. any logic deduction from a set of axioms (written in first-order logic) is equivalent to proving the theorem for all models satisfying the axioms.

Completeness is good to have, and for this reason, both the Peano and the Real numbers axioms, which by themselves are second-order logic, are usually stated within set theory, where they become first-order logic.

But then my question is: when axioms are in second-order logic, it is not true that "any logic deduction from a set of axioms is equivalent to proving the theorem for all models satisfying the axioms"?

Is there an example of a logical deduction from a set of axioms (written in second-order logic), such that the resulting theorem is not valid for at least one model satisfying the axioms?

 

[sysprog]

I think that reading the Stanford Encyclopedia article on Gödel’s Incompleteness Theorems would probably shed some clear light on this for you.

 

[Heikki Tuuri]

https://math.stackexchange.com/ques...heorem-for-second-order-logic-in-the-language
There is no complete proof system or a calculus which would prove all such sentences of second order logic which are true in every model of the vocabulary.

By definition, if you have a proof system and you prove a sentence in it, then the sentence is true in every model of that vocabulary.

Predicate calculus is a complete proof system for first order logic.

 

[sysprog]

Predicate calculus is a complete proof system for first order logic.

Whether predicate calculus or first order logic is or is not in your view therefore/consequently inconsistent, and whether you do or do not intend to deny the validity of [Professor] Gödel’s Incompleteness Theorems, I request that you please elaborate on the meaning you endeavor to convey to readers of that sentence.

 

[stevendaryl]

Whether predicate calculus or first order logic is or is not in your view therefore/consequently inconsistent, and whether you do or do not intend to deny the validity of [Professor] Gödel’s Incompleteness Theorems, I request that you please elaborate on the meaning you endeavor to convey to readers of that sentence.

There are two different meanings of "complete". We say that a theory is complete if every statement expressible in the language of that theory is either provable or refutable. Godel proved that if a theory is at least as powerful as arithmetic, it can't be consistent, complete and axiomatizable.

We say that a logic or set of deduction rules for a language is complete if every valid statement is provable. A statement is valid if it is true under all possible interpretations of the nonlogical symbols. For example, "A implies A" is true, regardless of what "A" stands for.

First-order logic is complete in the second sense. Peano arithmetic is incomplete in the first sense.

 

[sysprog]

We say that a logic or set of deduction rules for a language is complete if every valid statement is provable.

I'm not sure that I'd be willing to co-sign such a statement. I would call a language, and the logic for that language, complete if and only if I determined that all things observable or imaginable are in that language sayable, and by the logic thereof provable or disprovable, even if it is by those conditions logically necessary that some possible statements in the language are self-inconsistent. Is it the case that you think that regarding first-order logic "we say that" any statement that is for all truth values false is invalid?

 

[stevendaryl]

I'm not sure that I'd be willing to co-sign such a statement. I would call a language, and the logic for that language, complete if and only if I determined that all things observable or imaginable are in that language sayable, and by the logic thereof provable or disprovable, even if it is by those conditions logically necessary that some possible statements in the language are self-inconsistent. Is it the case that you think that regarding first-order logic "we say that" any statement that is for all truth values false is invalid?

It's a technical definition. It's not a matter of opinion. In first order logic, there is a notion of an "interpretation" of a language. An interpretation consists of:

1. A "universe" of discourse, $U$.
2. For every variable symbol, $v$, there is a corresponding element of $U$, $\mathcal{I}(v)$.
3. For every n-ary relation symbol $R(x_1, x_2, x_3, ..., x_n)$, there is a corresponding set $\mathcal{I}(R)$ of n-tuples of elements of $U$
4. For simplicity, I'll leave out function symbols and constant symbols.

In terms of an interpretation, we can say that a formula is true under an interpretation.

• The formula $R(x_1, x_2, ..., x_n)$ is true if $\mathcal{I}(x_1) = e_1$ and $\mathcal{I}(x_2) = e_2$, etc, and $(e_1, e_2, ..., e_n)$ is an element of $\mathcal{I}(R)$.
• A conjunction $A \wedge B$ is true if both $A$ is true and $B$ is true.
• A disjunction $A \vee B$ is true if either one is true.
• A negation $\neg A$ is true if $A$ is not true.
• $\forall x \phi$ is true under interpretation $\mathcal{I}$ in the following circumstances: Let $\mathcal{I}(x \rightarrow e)$ be an interpretation $\mathcal{I}'$ that only differs from $\mathcal{I}$ by the fact that $\mathcal{I}'(x) = e$. Then $\forall x \phi$ is true under interpretation $\mathcal{I}$ if under all possible $e$ in $U$, $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$. So a for all statement is true if it is true no matter how you interpret the variable.
• $\exists x \phi$ is true if there is an $e$ such that $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$

Basically, an interpretation is just a way to understand what the formulas are saying by giving the domain the variables range over and giving the meanings of the relation symbols.

A formula is valid if it is true under all possible interpretations. A formula is invalid if it is not valid. So an invalid formula isn't one that is always false, it's one that is not always true.

 

[WWGD]

It's a technical definition. It's not a matter of opinion. In first order logic, there is a notion of an "interpretation" of a language. An interpretation consists of:

1. A "universe" of discourse, $U$.
2. For every variable symbol, $v$, there is a corresponding element of $U$, $\mathcal{I}(v)$.
3. For every n-ary relation symbol $R(x_1, x_2, x_3, ..., x_n)$, there is a corresponding set $\mathcal{I}(R)$ of n-tuples of elements of $U$
4. For simplicity, I'll leave out function symbols and constant symbols.

In terms of an interpretation, we can say that a formula is true under an interpretation.

• The formula $R(x_1, x_2, ..., x_n)$ is true if $\mathcal{I}(x_1) = e_1$ and $\mathcal{I}(x_2) = e_2$, etc, and $(e_1, e_2, ..., e_n)$ is an element of $\mathcal{I}(R)$.
• A conjunction $A \wedge B$ is true if both $A$ is true and $B$ is true.
• A disjunction $A \vee B$ is true if either one is true.
• A negation $\neg A$ is true if $A$ is not true.
• $\forall x \phi$ is true under interpretation $\mathcal{I}$ in the following circumstances: Let $\mathcal{I}(x \rightarrow e)$ be an interpretation $\mathcal{I}'$ that only differs from $\mathcal{I}$ by the fact that $\mathcal{I}'(x) = e$. Then $\forall x \phi$ is true under interpretation $\mathcal{I}$ if under all possible $e$ in $U$, $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$. So a for all statement is true if it is true no matter how you interpret the variable.
• $\exists x \phi$ is true if there is an $e$ such that $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$

Basically, an interpretation is just a way to understand what the formulas are saying by giving the domain the variables range over and giving the meanings of the relation symbols.

A formula is valid if it is true under all possible interpretations. A formula is invalid if it is not valid. So an invalid formula isn't one that is always false, it's one that is not always true.

And an interpretation that "witnesses" the theory, i.e., where all formulas are mapped to the truth value 'true' are a model for the theory, right? And same for a set of sentences?

 

[sysprog]

We say that a logic or set of deduction rules for a language is complete if every valid statement is provable.

I'm not sure that I'd be willing to co-sign such a statement.

It's a technical definition. It's not a matter of opinion.

I did not and do not contend that the matter of completeness of the predicate calculus in/for first order logic is a matter of opinion, and I do not agree that the statement "a logic or set of deduction rules for a language is complete if every valid statement is provable" is "a technical definition", nor do I agree with that statement as worded.

An interpretation consists of:

1. A "universe" of discourse, $U$.
2. For every variable symbol, $v$, there is a corresponding element of $U$, $\mathcal{I}(v)$.
3. For every n-ary relation symbol $R(x_1, x_2, x_3, ..., x_n)$, there is a corresponding set $\mathcal{I}(R)$ of n-tuples of elements of $U$
4. For simplicity, I'll leave out function symbols and constant symbols.

In terms of an interpretation, we can say that a formula is true under an interpretation.

• The formula $R(x_1, x_2, ..., x_n)$ is true if $\mathcal{I}(x_1) = e_1$ and $\mathcal{I}(x_2) = e_2$, etc, and $(e_1, e_2, ..., e_n)$ is an element of $\mathcal{I}(R)$.
• A conjunction $A \wedge B$ is true if both $A$ is true and $B$ is true.
• A disjunction $A \vee B$ is true if either one is true.
• A negation $\neg A$ is true if $A$ is not true.
• $\forall x \phi$ is true under interpretation $\mathcal{I}$ in the following circumstances: Let $\mathcal{I}(x \rightarrow e)$ be an interpretation $\mathcal{I}'$ that only differs from $\mathcal{I}$ by the fact that $\mathcal{I}'(x) = e$. Then $\forall x \phi$ is true under interpretation $\mathcal{I}$ if under all possible $e$ in $U$, $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$. So a for all statement is true if it is true no matter how you interpret the variable.
• $\exists x \phi$ is true if there is an $e$ such that $\phi$ is true under the interpretation $\mathcal{I}(x \rightarrow e)$

Basically, an interpretation is just a way to understand what the formulas are saying by giving the domain the variables range over and giving the meanings of the relation symbols.

I think that is an outstandingly good brief exposition.

A formula is valid if it is true under all possible interpretations. A formula is invalid if it is not valid. So an invalid formula isn't one that is always false, it's one that is not always true.

I view that to be an insufficient formulation for the purpose to which you appear to be trying to apply it. It looks to me as if you're saying that only tautologies are valid formulations. Even if it's true that all valid arguments, in the sense of sets of premises along with the conclusions drawn therefrom, are tautologies, the statements therein need not themselves be tautologies to be valid statements. I think that your formulation needs some elaboration.

 

[stevendaryl]

I view that to be an insufficient formulation for the purpose to which you appear to be trying to apply it. It looks to me as if you're saying that only tautologies are valid formulations.

Yes.

Even if it's true that all valid arguments, in the sense of sets of premises along with the conclusions drawn therefrom, are tautologies, the statements therein need not themselves be tautologies to be valid statements.

Well, "valid" is usually applied to inferences. You have axioms $A_1, A_2, ...$ and you prove $B$. $B$ is a valid inference from $A_1, ...$ if every interpretation that makes all the $A$s true also makes $B$ true. If the list of $A$s is finite, then this is equivalent to saying that $A_1 \wedge A_2 \wedge ... \rightarrow B$ is valid, in the sense of being true under all interpretations.

 

[stevendaryl]

From Wikipedia:

https://en.wikipedia.org/wiki/Tautology_(logic)#Semantic_completeness_and_soundness

An axiomatic system is complete if every tautology is a theorem (derivable from axioms). An axiomatic system is sound if every theorem is a tautology.

I guess I got the terminology mixed up. "Valid" applies to inferences, while "tautology" applies to formulas.

 

[sysprog]

From Wikipedia:

https://en.wikipedia.org/wiki/Tautology_(logic)#Semantic_completeness_and_soundnessI guess I got the terminology mixed up. "Valid" applies to inferences, while "tautology" applies to formulas.

In general, we call a formula 'well-formed' or not, and an argument 'valid' or not; however, there are 16 binary relations that are 'validly' expressible, from contradiction at one extreme, to tautology on the other. Exactly two of those are complete, in the sense that all of the others can be expressed by the use of multiple instances of them; In electronic engineering, the binary relations or functions are implemented by logic gates, and one of those two complete binary relation gates is called NAND and the other is called NOR. An inverter (an inverter is a monary inversion functor) emplaced after an AND yields/produces NAND, and succeeding an OR with an inverter results in a NOR.