User:IssaRice/Computability and logic/Intended interpretation versus all interpretations - Revision history

IssaRice: /* Completeness */

2019-02-02T06:15:17Z

Completeness

← Older revision		Revision as of 06:15, 2 February 2019
Line 22:		Line 22:
	* 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 ''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"		* 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"
			* <math>\Sigma_1</math>-complete theory -- about the standard interpretation.

	==Expresses, arithmetically defines==		==Expresses, arithmetically defines==

IssaRice at 03:41, 1 February 2019

2019-02-01T03:41:23Z

← Older revision		Revision as of 03:41, 1 February 2019
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 (xy = yx)</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 (xy = yx)</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>.

IssaRice at 03:40, 1 February 2019

2019-02-01T03:40:44Z

← Older revision		Revision as of 03:40, 1 February 2019
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.)		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 (xy = yx)</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>.		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>.

IssaRice: /* Completeness */

2019-02-01T00:17:38Z

Completeness

← Older revision		Revision as of 00:17, 1 February 2019
Line 21:		Line 21:

	* 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 ''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.		* 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==		==Expresses, arithmetically defines==

IssaRice at 00:16, 1 February 2019

2019-02-01T00:16:20Z

← Older revision		Revision as of 00:16, 1 February 2019
Line 11:		Line 11:
	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".		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.		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?

	==Soundness==		==Soundness==

IssaRice: /* Completeness */

2019-02-01T00:08:44Z

Completeness

← Older revision		Revision as of 00:08, 1 February 2019
Line 20:		Line 20:
	==Completeness==		==Completeness==

	* The completeness of a ''deductive system'' (a.k.a. semantic completeness) takes the "all possible interpretations" point of view.		* 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).		* 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.

	==Expresses, arithmetically defines==		==Expresses, arithmetically defines==

IssaRice at 00:06, 1 February 2019

2019-02-01T00:06:54Z

← Older revision		Revision as of 00:06, 1 February 2019
Line 12:		Line 12:

	Syntax doesn't seem to have this analogue.		Syntax doesn't seem to have this analogue.

	~~Expresses/captures: these are also relative to an interpretation.~~

	==Soundness==		==Soundness==
Line 24:		Line 22:
	* The completeness of a ''deductive system'' (a.k.a. semantic completeness) takes the "all possible interpretations" point of view.		* The completeness of a ''deductive system'' (a.k.a. semantic completeness) takes the "all possible interpretations" point of view.
	* 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).		* 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).

			==Expresses, arithmetically defines==

			these are also relative to an interpretation.

			==Captures, defines==

			these are also relative to an interpretation.

	==External links==		==External links==

	* https://math.stackexchange.com/a/13677/35525		* https://math.stackexchange.com/a/13677/35525

IssaRice at 00:05, 1 February 2019

2019-02-01T00:05:27Z

← Older revision		Revision as of 00:05, 1 February 2019
Line 1:		Line 1:
	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.		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".		:'''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.)		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.)

IssaRice at 00:05, 1 February 2019

2019-02-01T00:05:18Z

← Older revision		Revision as of 00:05, 1 February 2019
Line 1:		Line 1:
	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.		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 <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.)		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.)

IssaRice: /* Completeness */

2019-02-01T00:03:34Z

Completeness

← Older revision		Revision as of 00:03, 1 February 2019
Line 21:		Line 21:

	* The completeness of a ''deductive system'' (a.k.a. semantic completeness) takes the "all possible interpretations" point of view.		* The completeness of a ''deductive system'' (a.k.a. semantic completeness) takes the "all possible interpretations" point of view.
	* The completeness of a ''theory'' (a.k.a. negation-completeness) is ''entirely syntactic'', so it does not take either of the views.		* 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).

	==External links==		==External links==

	* https://math.stackexchange.com/a/13677/35525		* https://math.stackexchange.com/a/13677/35525