# Difference between revisions of "User:IssaRice/Computability and logic/Intended interpretation versus all interpretations"

Line 3: | Line 3: | ||

:'''Moral.''' Whenever you see the word "true" or "truth" in mathematical logic, always be sure whether it is about "truth in the intended interpretation" or "truth in all possible interpretations". | :'''Moral.''' Whenever you see the word "true" or "truth" in mathematical logic, always be sure whether it is about "truth in the intended interpretation" or "truth in all possible interpretations". | ||

− | Normally when we say a mathematical statement is true, we mean that it is true in the standard (or intended) interpretation. For instance, we say that <math>2+2=4</math> is true. But <math>2+2=4</math> could also be false if we adopt a non-standard interpretation. For example, we could say "<math>2</math>" is the number zero, "<math>4</math>" is the number one, and "<math>+</math>" is the usual multiplication. In other words, we still keep the same ''signature'' (<math>2</math> and <math>4</math> are still constants, <math>+</math> is still a binary function) so that the sentence is still grammatical, but we assign different meanings to these non-logical symbols. (Note: the equality symbol is usually taken to be special and cannot be assigned an arbitrary meaning.) A better example is a sentence like <math>\forall x \forall y (x*y = y*x)</math>. | + | Normally when we say a mathematical statement is true, we mean that it is true in the standard (or intended) interpretation. For instance, we say that <math>2+2=4</math> is true. But <math>2+2=4</math> could also be false if we adopt a non-standard interpretation. For example, we could say "<math>2</math>" is the number zero, "<math>4</math>" is the number one, and "<math>+</math>" is the usual multiplication. In other words, we still keep the same ''signature'' (<math>2</math> and <math>4</math> are still constants, <math>+</math> is still a binary function) so that the sentence is still grammatical, but we assign different meanings to these non-logical symbols. (Note: the equality symbol is usually taken to be special and cannot be assigned an arbitrary meaning.) A better example is a sentence like <math>\forall x \forall y (x*y = y*x)</math>, which can be true or false depending on whether a structure with a given operation is commutative. |

When we talk about semantic consequence (a.k.a. logical consequence, logical implication) and write things like <math>\Gamma \models \phi</math> (where <math>\Gamma</math> is a set of sentences and <math>\phi</math> is a sentence) then this doesn't just mean that "if all sentences in <math>\Gamma</math> are true, then the sentence <math>\phi</math> also is true". Rather, it means that this "if-then" is true ''in every possible interpretation''. In other words, when we write <math>\Gamma \models \phi</math> we mean that there is no interpretation in which every sentence in <math>\Gamma</math> is true but <math>\phi</math> is false. This is also sometimes expressed by saying that <math>\phi</math> is true in all models of <math>\Gamma</math>. | When we talk about semantic consequence (a.k.a. logical consequence, logical implication) and write things like <math>\Gamma \models \phi</math> (where <math>\Gamma</math> is a set of sentences and <math>\phi</math> is a sentence) then this doesn't just mean that "if all sentences in <math>\Gamma</math> are true, then the sentence <math>\phi</math> also is true". Rather, it means that this "if-then" is true ''in every possible interpretation''. In other words, when we write <math>\Gamma \models \phi</math> we mean that there is no interpretation in which every sentence in <math>\Gamma</math> is true but <math>\phi</math> is false. This is also sometimes expressed by saying that <math>\phi</math> is true in all models of <math>\Gamma</math>. |

## Revision as of 03:41, 1 February 2019

Something I have found tricky in mathematical logic is that some theorems/propositions apply to just the intended/standard interpretation (structure), while others are about all possible interpretations. Texts also don't necessarily emphasize this point each time, so you have to figure it out.

**Moral.**Whenever you see the word "true" or "truth" in mathematical logic, always be sure whether it is about "truth in the intended interpretation" or "truth in all possible interpretations".

Normally when we say a mathematical statement is true, we mean that it is true in the standard (or intended) interpretation. For instance, we say that is true. But could also be false if we adopt a non-standard interpretation. For example, we could say "" is the number zero, "" is the number one, and "" is the usual multiplication. In other words, we still keep the same *signature* ( and are still constants, is still a binary function) so that the sentence is still grammatical, but we assign different meanings to these non-logical symbols. (Note: the equality symbol is usually taken to be special and cannot be assigned an arbitrary meaning.) A better example is a sentence like , which can be true or false depending on whether a structure with a given operation is commutative.

When we talk about semantic consequence (a.k.a. logical consequence, logical implication) and write things like (where is a set of sentences and is a sentence) then this doesn't just mean that "if all sentences in are true, then the sentence also is true". Rather, it means that this "if-then" is true *in every possible interpretation*. In other words, when we write we mean that there is no interpretation in which every sentence in is true but is false. This is also sometimes expressed by saying that is true in all models of .

Similarly when we say that a sentence is *valid*, this is much stronger than saying it is true in our intended interpretation. To say a sentence is valid means that no matter what interpretation we assign, the sentence ends up true. Thus, is not a valid sentence. But is a valid sentence; no matter what meanings we assigned to the non-logical symbols, the sentence would come out true. In other words, validity is the absence of a counterexample.

The soundness and completeness theorems are all about this "all possible interpretations" point of view. If a deductive system is sound and complete, then "true in all possible interpretations" exactly coincides with "is provable in the system".

Syntax doesn't seem to have this analogue. If something is provable, it automatically gets "true in all possible interpretations" (assuming soundness). There doesn't seem to be a way to partially prove something?

## Contents

## Soundness

- The soundness of a
*deductive system*takes the "all possible interpretations" point of view. - The soundness of a
*theory*takes the "true in the intended interpretation" point of view.

## Completeness

- The completeness of a
*deductive system*(a.k.a. semantic completeness) takes the "all possible interpretations" point of view. Gödel's completeness theorem is about this form of completeness, so Gödel's completeness theorem is talking about all possible interpretations. - The completeness of a
*theory*(a.k.a. negation-completeness) is*entirely syntactic*, so it does not take either of the views (whenever we talk about truth, that is bringing in semantics). Gödel's first incompleteness theorem is about this form of completeness, so Gödel's first incompleteness theorem is talking about truth in the intended interpretation. -- actually this might be wrong. there is a way to phrase godel's incompleteness theorem in terms of models like "there is a sentence that is true in some models but not others"

## Expresses, arithmetically defines

these are also relative to an interpretation.

## Captures, defines

these are also relative to an interpretation.