First of all, let me issue a warning: model-theoretic truth is a mathematical notion, which (a priori) doesn’t have anything to do with the real-world sense of truth!
A short introduction to model theory follows. It is not LW quality, but hopefully it’s good enough to answer some questions about MrMind’s post. Prerequisites: merely some familiarity with formal reasoning, but I guess knowing the Mental Concepts of Model Theory doesn’t hurt.
The 1st part is the general introduction to model theory, the examples about non-standard models are in the 2nd and 3rd parts.
1 Models explained
Axioms are the starting points of formal reasoning. A collection (system) of axioms is inconsistent if it is possible to prove a contradiction using them. E.g. consider the following system of three axioms.
All men are mortal.
Socrates is a man.
Socrates is not mortal.
This system is inconsistent, because the contradiction “Socrates is mortal and Socrates is not mortal” is a consequence of the axioms. On the other hand, the following system (from now on referred to as the example system) is not inconsistent:
All men are mortal.
Socrates is a man.
Inconsistent systems are liars: the conclusions derived from them cannot be trusted. ^1 Axiomatic systems can be defined for many specific purposes (mathematics, ethics, et c.). Hopefully I don’t have to explain why an inconsistent system of ethics would be disastrous. We would like some assurance that our frameworks are not inconsistent: proofs of consistency!
Proofs of consistency are possible because mathematicians have agreed upon a powerful axiomatic system, the Set Theory ZFC that they believe to be consistent. ^3
Take any axiomatic theory S. Sometimes, you can re-label the axioms of S to be about mathematical objects. This is possible if
All quantifiers that occur in the axioms can be restricted to range over some given set M (in the example system, you would replace “All men” with “All men belonging to the set M*”).
Each symbol occuring in the axioms can be identified with an element of the set M (in the example system you would interpret the word “Socrates” to refer to some specific element of the set M).
Each predicate occuring in the axioms can be identified with a subset of the set M (in the example system you would interpret “is a man” by a subset of M, and “is mortal” by another subset of M).
The sentences of S, when interpreted this way, are consequences of the axioms of ZFC.
Such sets M, whenever they exist, are called the models of S. The set of numbers less than 5 {0,1,2,3,4} is a model of the example system, because you can
Interpret the symbol “Socrates” as referring to the number 1.
Interpret the predicate “is a man” as the subset of odd numbers; this means that you consider 1 and 3 men, but not 0, 2 and 4.
Interpret the predicate “is mortal” as the subset of numbers less than 4; this means that you consider 0, 1, 2 and 3 to be mortals, but not 4.
Now, the sentence “All men are mortal” means “All odd numbers in M are less than 3″, which is a true mathematical statement that you can prove using the axioms of ZFC.
The sentence “Socrates is a man” means “The number 1 is odd”, which is again a true mathematical statement that can be proved from the axioms of ZFC.
The relabeling interprets the axioms and consequences of S as true mathematical statements (the form of the statements is preserved, even if meaning is not). If a contradiction follows from the axioms of S, then it can be relabeled into a contradiction in mathematics (ZFC). Therefore, every axiomatic system that has a model is at least as consistent as mathematics itself: giving a model amounts to giving a consistency proof. We say that this consistency proof is relative to ZFC.
It can be demonstrated that Model Theory is the most general method of giving consistency proofs (relative to ZFC): if ZFC proves that a system is consistent then the system has a model, and vice versa.
^1 There are also consistent liars. Observing an inconsistency is sufficient to conclude that an axiom system is a liar, but it is not necessary.
^2 Observe that we still have no assurance about the consistency of this general-purpose system.
^3 This is not entirely true, but it is a reasonable non-technical explanation.
^4 Unfortunately, the satisfaction relation “satisfied in a model” is commonly referred to as true in a model. Worst of all, “X is satisfied in the standard model” is sometimes abbreivated to X is true, giving these results a false aura of deep philosophical relevance.
As a general rule, consistent theories have multiple models. Models have more consequences than the theories they model: for example, our model of the example system proves that there are only 2 men, even though this does not follow from the axioms. A sentence follows from the axioms only if it is satisfied in every possible model of S. ^4
Even the axiomatic theory of natural number arithmetic, which we would think is absolute, has multiple models. Mathematicians have agreed on a standard model (the so-called set of natural numbers), but it is easy to prove that other models exist:
Extend the theory of arithmetic (PA) with a new constant K, and the following (infinitely many) axioms.
0 < K
1 < K
2 < K
...
65534 < K
65535 < K
...
Surprisingly, the resulting theory PAK is consistent. Proofs are finite: any proof of a contradiction in PAK would use only finitely many axioms, so there is a largest number n such that n < K is used in the proof. Therefore, K can be replaced in the proof by n + 1, yielding a proof of a contradiction in PA itself! Since arithmetic is consistent, there is no proof of contradiction in PAK.
We have shown that PAK is consistent relative to ZFC. Therefore, it has a model. A model of PAK is a model of arithmetic, but it is clearly not the standard model. Therefore, arithmetic has a non-standard model, which contains the standard integers, as well as non-standard integers (such as the one corresponding to our constant K). In a sense, the non-standard models contain “infinite” numbers that the model cannot distinguish from the real, finite numbers.
The existence of non-standard models is a serious issue: There are situations where the standard model has no counterexamples to a statement, but some non-standard model has. This means that the statement ought to follow from the axioms of arithmetic, but we cannot prove it because it fails in a weird, non-standard model.
For example, some non-standard models disagree with the following statement (the Ramsey theorem), which is satisified by the standard model.
For any non-zero natural numbers n, k, m we can find a natural number N such that if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.
Another, more accessible example is whether you can kill the Hydra or not. You can kill the hydra in the standard model, but many non-standard models disagree. If you would number all the hydras in a non-standard model, the counterexamples would be numbered by non-standard numbers such as K in the proof above.
We need to add new axioms to the axiomatic system of arithmetic, so that it corresponds more faithfully to the standard model. However, our work is never over: as a consequence of Gödel’s incompleteness theorem, new axioms can rule out some non-standard models, but never all of them.
3. Generalised models and Hamkins’ paper
So far:
Consistency relative to ZFC is a useful notion: giving a model allows us to prove that our theories are as consistent as mathematics itself.
Arithmetic has multiple models. There is a so-called standard model of arithmetic, which is not some real-world or transcendent notion. It is merely a set that mathematicians have agreed to call the standard model. The axioms of arithmetic are unable to exactly describe the standard model: they always describe the standard model plus some other “junk” models.
Do we know that ZFC is consistent? The short answer: we don’t and we can’t. By Gödel’s incompleteness, if ZFC is consistent then it has no models. However, by adding new axioms to ZFC (e. g. large cardinal axioms). we can create set theories that have generalised notions of models. While ZFC has no models, it does have generalised models.
Unlike arithmetic, ZFC itself has no agreed-upon standard generalised model. There is not even a standard system in which we construct generalised models. In all of the above, we have refused to choose a specific model of ZFC (i. e. we did not use the phrase “satisfied in a generalised model of ZFC” or any semantically equivalent sentences). We used the notion of provability in ZFC (which is absolute).
If we replace provability in ZFC with “satisfiability in some specific model”, we are suddenly able to prove more properties about the standard model of arithmetic (similarly to how we can prove more theorems about numbers by passing to the standard model of arithmetic from the axioms of arithmetic). Unfortunately, it is well-known (and intuitively obvious) that if you and I choose different generalised models, our conclusions (about these previously undecidable properties) can disagree.
The paper of Hamkins collects some stronger results: our conclusions can disagree even if our chosen generalised models are very similar. For example
There are two generalised models which agree upon the elements that constitute the standard model, yet disagree on the properties of these elements.
There are two generalised models which agree upon the elements that constitute the standard model, agree upon the properties of the addition operation, yet disagree about the properties of the multiplication operations.
and so on… Unfortunately, the proofs of these rely on powerful lemmas, so I can’t instantiate them to produce explicit examples.
Got really much me thinking. Why are we regarding non-standard natural numbers as “junk”? I guess the identification of standard natural number as the simplest construciton that is a natural number system.
The thing is a know a perfectly legimate construction for a number that is non-standard and not deliberately a “wrench in the machinery”. The surreal number {1,2,3,4...|}=ω I have sometimes seen characterised as a integer and it’s construction is of the same shape as other integers with lower birthdays (althought they use finite sets, ω is the first to use infinite sets).
The hydra problem seems natural as you can’t have ω-(n1) with finite n that reaches 0, and in fact ω-(n1) is still bigger than any finite number. I can also see how the successor of ω is ω+1 which I guess is the property that successor and addition play nice together.
When geometry was axiomatised it was discovered that there are euclid and non-euclid geometries. They were not called non-standard geometries despite them getting way less attention. In general euclid and non-euclid geometries share some properties (those that stem from aximo not regarding parallel lines) but have different properties in general (ie different parallizaiton rules lead to genuinely different systems). Coudn’t it just be that we are using a way too general system where the formal meaning of a integer captures more entities that we have in mind when we are really interested only in certain kinds of natural numbers? That is ω might be a integer as the axioms read out but when people say integers they don’t mean entities like ω (like when people say space they usually don’t mean minowskian spaces althought those are spaces too).
I do like the rigour that when a mathematician lays out a set of axioms he can know whether all cases are covered without being able to come up with any “viable” exception to them. That is any kind of arithmetic thing that hinges on the differences of finite and infinite numbers is already ambigious based on axioms of arithmetic because finiteness and infiniteness is ortohogonal to the issue (a kind of separation of concerns where you don’t even know how many concerns there are).
Wouldn’t the holistic nature of the truth be viewed as if you have an ambigious delineation on the universe of discourse then you can’t have all properties nailed down. As in if you have a theory of “tallness” that doesn’t allow you to determine an objects color.
First of all, let me issue a warning: model-theoretic truth is a mathematical notion, which (a priori) doesn’t have anything to do with the real-world sense of truth!
A short introduction to model theory follows. It is not LW quality, but hopefully it’s good enough to answer some questions about MrMind’s post. Prerequisites: merely some familiarity with formal reasoning, but I guess knowing the Mental Concepts of Model Theory doesn’t hurt.
The 1st part is the general introduction to model theory, the examples about non-standard models are in the 2nd and 3rd parts.
1 Models explained
Axioms are the starting points of formal reasoning. A collection (system) of axioms is inconsistent if it is possible to prove a contradiction using them. E.g. consider the following system of three axioms.
All men are mortal.
Socrates is a man.
Socrates is not mortal.
This system is inconsistent, because the contradiction “Socrates is mortal and Socrates is not mortal” is a consequence of the axioms. On the other hand, the following system (from now on referred to as the example system) is not inconsistent:
All men are mortal.
Socrates is a man.
Inconsistent systems are liars: the conclusions derived from them cannot be trusted. ^1 Axiomatic systems can be defined for many specific purposes (mathematics, ethics, et c.). Hopefully I don’t have to explain why an inconsistent system of ethics would be disastrous. We would like some assurance that our frameworks are not inconsistent: proofs of consistency!
Proofs of consistency are possible because mathematicians have agreed upon a powerful axiomatic system, the Set Theory ZFC that they believe to be consistent. ^3
Take any axiomatic theory S. Sometimes, you can re-label the axioms of S to be about mathematical objects. This is possible if
All quantifiers that occur in the axioms can be restricted to range over some given set M (in the example system, you would replace “All men” with “All men belonging to the set M*”).
Each symbol occuring in the axioms can be identified with an element of the set M (in the example system you would interpret the word “Socrates” to refer to some specific element of the set M).
Each predicate occuring in the axioms can be identified with a subset of the set M (in the example system you would interpret “is a man” by a subset of M, and “is mortal” by another subset of M).
The sentences of S, when interpreted this way, are consequences of the axioms of ZFC.
Such sets M, whenever they exist, are called the models of S. The set of numbers less than 5 {0,1,2,3,4} is a model of the example system, because you can
Interpret the symbol “Socrates” as referring to the number 1.
Interpret the predicate “is a man” as the subset of odd numbers; this means that you consider 1 and 3 men, but not 0, 2 and 4.
Interpret the predicate “is mortal” as the subset of numbers less than 4; this means that you consider 0, 1, 2 and 3 to be mortals, but not 4.
Now, the sentence “All men are mortal” means “All odd numbers in M are less than 3″, which is a true mathematical statement that you can prove using the axioms of ZFC.
The sentence “Socrates is a man” means “The number 1 is odd”, which is again a true mathematical statement that can be proved from the axioms of ZFC.
The relabeling interprets the axioms and consequences of S as true mathematical statements (the form of the statements is preserved, even if meaning is not). If a contradiction follows from the axioms of S, then it can be relabeled into a contradiction in mathematics (ZFC). Therefore, every axiomatic system that has a model is at least as consistent as mathematics itself: giving a model amounts to giving a consistency proof. We say that this consistency proof is relative to ZFC.
It can be demonstrated that Model Theory is the most general method of giving consistency proofs (relative to ZFC): if ZFC proves that a system is consistent then the system has a model, and vice versa.
^1 There are also consistent liars. Observing an inconsistency is sufficient to conclude that an axiom system is a liar, but it is not necessary.
^2 Observe that we still have no assurance about the consistency of this general-purpose system.
^3 This is not entirely true, but it is a reasonable non-technical explanation.
^4 Unfortunately, the satisfaction relation “satisfied in a model” is commonly referred to as true in a model. Worst of all, “X is satisfied in the standard model” is sometimes abbreivated to X is true, giving these results a false aura of deep philosophical relevance.
2. A multitude of models
As a general rule, consistent theories have multiple models. Models have more consequences than the theories they model: for example, our model of the example system proves that there are only 2 men, even though this does not follow from the axioms. A sentence follows from the axioms only if it is satisfied in every possible model of S. ^4
Even the axiomatic theory of natural number arithmetic, which we would think is absolute, has multiple models. Mathematicians have agreed on a standard model (the so-called set of natural numbers), but it is easy to prove that other models exist:
Extend the theory of arithmetic (PA) with a new constant K, and the following (infinitely many) axioms.
Surprisingly, the resulting theory PAK is consistent. Proofs are finite: any proof of a contradiction in PAK would use only finitely many axioms, so there is a largest number n such that n < K is used in the proof. Therefore, K can be replaced in the proof by n + 1, yielding a proof of a contradiction in PA itself! Since arithmetic is consistent, there is no proof of contradiction in PAK.
We have shown that PAK is consistent relative to ZFC. Therefore, it has a model. A model of PAK is a model of arithmetic, but it is clearly not the standard model. Therefore, arithmetic has a non-standard model, which contains the standard integers, as well as non-standard integers (such as the one corresponding to our constant K). In a sense, the non-standard models contain “infinite” numbers that the model cannot distinguish from the real, finite numbers.
The existence of non-standard models is a serious issue: There are situations where the standard model has no counterexamples to a statement, but some non-standard model has. This means that the statement ought to follow from the axioms of arithmetic, but we cannot prove it because it fails in a weird, non-standard model.
For example, some non-standard models disagree with the following statement (the Ramsey theorem), which is satisified by the standard model.
Another, more accessible example is whether you can kill the Hydra or not. You can kill the hydra in the standard model, but many non-standard models disagree. If you would number all the hydras in a non-standard model, the counterexamples would be numbered by non-standard numbers such as K in the proof above.
We need to add new axioms to the axiomatic system of arithmetic, so that it corresponds more faithfully to the standard model. However, our work is never over: as a consequence of Gödel’s incompleteness theorem, new axioms can rule out some non-standard models, but never all of them.
3. Generalised models and Hamkins’ paper
So far:
Consistency relative to ZFC is a useful notion: giving a model allows us to prove that our theories are as consistent as mathematics itself.
Arithmetic has multiple models. There is a so-called standard model of arithmetic, which is not some real-world or transcendent notion. It is merely a set that mathematicians have agreed to call the standard model. The axioms of arithmetic are unable to exactly describe the standard model: they always describe the standard model plus some other “junk” models.
Do we know that ZFC is consistent? The short answer: we don’t and we can’t. By Gödel’s incompleteness, if ZFC is consistent then it has no models. However, by adding new axioms to ZFC (e. g. large cardinal axioms). we can create set theories that have generalised notions of models. While ZFC has no models, it does have generalised models.
Unlike arithmetic, ZFC itself has no agreed-upon standard generalised model. There is not even a standard system in which we construct generalised models. In all of the above, we have refused to choose a specific model of ZFC (i. e. we did not use the phrase “satisfied in a generalised model of ZFC” or any semantically equivalent sentences). We used the notion of provability in ZFC (which is absolute).
If we replace provability in ZFC with “satisfiability in some specific model”, we are suddenly able to prove more properties about the standard model of arithmetic (similarly to how we can prove more theorems about numbers by passing to the standard model of arithmetic from the axioms of arithmetic). Unfortunately, it is well-known (and intuitively obvious) that if you and I choose different generalised models, our conclusions (about these previously undecidable properties) can disagree.
The paper of Hamkins collects some stronger results: our conclusions can disagree even if our chosen generalised models are very similar. For example
There are two generalised models which agree upon the elements that constitute the standard model, yet disagree on the properties of these elements.
There are two generalised models which agree upon the elements that constitute the standard model, agree upon the properties of the addition operation, yet disagree about the properties of the multiplication operations.
and so on… Unfortunately, the proofs of these rely on powerful lemmas, so I can’t instantiate them to produce explicit examples.
Anyway, this should be enough to get you started.
Thanks for these posts (upvoted both). LW needs more of this.
You should definitely post it as a top-level post in Main.
Got really much me thinking. Why are we regarding non-standard natural numbers as “junk”? I guess the identification of standard natural number as the simplest construciton that is a natural number system.
The thing is a know a perfectly legimate construction for a number that is non-standard and not deliberately a “wrench in the machinery”. The surreal number {1,2,3,4...|}=ω I have sometimes seen characterised as a integer and it’s construction is of the same shape as other integers with lower birthdays (althought they use finite sets, ω is the first to use infinite sets).
The hydra problem seems natural as you can’t have ω-(n1) with finite n that reaches 0, and in fact ω-(n1) is still bigger than any finite number. I can also see how the successor of ω is ω+1 which I guess is the property that successor and addition play nice together.
When geometry was axiomatised it was discovered that there are euclid and non-euclid geometries. They were not called non-standard geometries despite them getting way less attention. In general euclid and non-euclid geometries share some properties (those that stem from aximo not regarding parallel lines) but have different properties in general (ie different parallizaiton rules lead to genuinely different systems). Coudn’t it just be that we are using a way too general system where the formal meaning of a integer captures more entities that we have in mind when we are really interested only in certain kinds of natural numbers? That is ω might be a integer as the axioms read out but when people say integers they don’t mean entities like ω (like when people say space they usually don’t mean minowskian spaces althought those are spaces too).
I do like the rigour that when a mathematician lays out a set of axioms he can know whether all cases are covered without being able to come up with any “viable” exception to them. That is any kind of arithmetic thing that hinges on the differences of finite and infinite numbers is already ambigious based on axioms of arithmetic because finiteness and infiniteness is ortohogonal to the issue (a kind of separation of concerns where you don’t even know how many concerns there are).
Wouldn’t the holistic nature of the truth be viewed as if you have an ambigious delineation on the universe of discourse then you can’t have all properties nailed down. As in if you have a theory of “tallness” that doesn’t allow you to determine an objects color.