Not quite. It’s a map of the sentences generated by a language to Z_2. When we talk about “a model of a theory”, we’re discussing those maps for which all sentences in the theory under consideration are mapped to 1.
To put it another way, a model cannot map just a theory on to Z_2; every model must map every sentence to Z_2 one way or the other. Some theories are such that their models must make arbitrary choices for sentences “outside the theory”, this is precisely “incompleteness”.
But yeah, there’s use in mapping sentences to something larger than Z_2. Down this road lies multi-valued logics. And if you want to map sentences onto the interval [0, 1] you’re getting pretty close to probabilistic logic.
Note that in the referenced paper, the probability function is constructed from a measure of how many available models map a sentence to 1 rather than 0, which is an interesting way to map sentences onto a continuous interval.
Not quite. It’s a map of the sentences generated by a language to Z_2. When we talk about “a model of a theory”, we’re discussing those maps for which all sentences in the theory under consideration are mapped to 1.
So, any sentence that does not map to 1 is not in the model? I thought a model includes both true and false sentences. I guess I should instead think of a model as a preimage of a single element (conventionally called “truth”) in some surjective theory->image map. Or is it language->image map? Is model a subset of some theory or just of a language?
To put it another way, a model cannot map just a theory on to Z_2; every model must map every sentence to Z_2 one way or the other.
Every sentence of the language? And the theory is the preimage of 1? I’m confused. This can’t be right, since there can be multiple models for the same theory. Or do all models for a given theory have the same preimage of 1 but differ in other ways?
Some theories are such that their models must make arbitrary choices for sentences “outside the theory”, this is precisely “incompleteness”.
Does this mean “in an undecidable (unsatisfiable? incomplete?) language there is no map language->Z_2”?
Hmm, I think I’ve misunderstood you somewhere. By Z_2 you mean “integers modulo 2” (the set {0, 1}), correct? If you want to think of a model as a function from sentences onto {0, 1}, then sentences which map to “0″ in some model are indeed “not in the model”. (This phrasing is uncommon; sentences are not usually referred to as “in” a model. Rather, the model either holds / models / models as true or rejects / does not model / models as false each sentence.)
I thought a model includes both true and false sentences
A sentence is neither true nor false except under consideration of a model. (Sentences true in every model are called “valid”, sentences false in every model are called “refutable”, but even then “truth” is a property assigned to sentences by models.) The sentences that a model models are true according to that model, so it’s tautologically true that a model does not hold any sentences that are “false in” (rejected by) that model.
If, by “true” and “false” you meant “valid” and “refutable”, then note that there are no models which model refutable sentences.
A sentence is neither true nor false except under consideration of a model.
OK, so, if I understand you correctly, the following sequence is sensible, though not standard and probably backward:
We construct a surjective map from a given language+logic to some set.
We designate one element of the image as “1” or “true”.
We construct the preimage of 1, called “provably true sentences”.
We select a subset of the language+logic called a “theory”, based on some external semantic considerations.
The intersection of the theory and the set of provably true sentences is called the model of the theory in the language+logic with the map as given in step 1. (“The” model because to get a different model we have to change the map in step 1.)
This way if a theory is not a subset of the preimage of “1” (i.e. a set of provably true sentences), it is called incomplete, even though the model singled out in the theory by the map in step 1 is complete.
In this analogy, the map is playing the role of “model” (as it assigns sentences to the analog of truth values).
Note that in order for the map to be a model, the map must have certain behavior (whenever both φ and ψ map to 1, φ∧ψ also maps to 1, etc.). In model theory we restrict consideration to maps obeying these laws; if your map strays outside these boundaries then model theory has nothing to say about it.
In model theory, we say that a model is “of” a theory when the model holds true all sentences in the given theory. Thus, in your construction, the preimage of 1 would be the theory of the map (the largest theory that the map is a model of).
If you construct a different theory T that contains sentences not in the preimage of 1, then we would say the map is not a model of T (because there are sentences of T which are not “true” under the map).
The object you’re discussing in pt.5 (the intersection between the theory of a model and some other theory) does not have an obvious analog in model theory.
In this analogy, the map is playing the role of “model” (as it assigns sentences to the analog of truth values).
Hmm, I thought only the preimage of 1 is the model.
in your construction, the preimage of 1 would be the theory of the map (the largest theory that the map is a model of).
But… a theory can include sentences not in the preimage of 1 (undecidable?)… I am confused.
I would instead say that the preimage of 1 is the largest model of the map, and is the model of any “large enough” theory.
Note that in order for the map to be a model, the map must have certain behavior (whenever both φ and ψ map to 1, φ∧ψ also maps to 1, etc.). In model theory we restrict consideration to maps obeying these laws; if your map strays outside these boundaries then model theory has nothing to say about it.
Where are these laws defined? In the logic? In the logic+language? Then the only “valid” maps are those which are homomorphisms (in some sense) from logic(?) to the Z_2 subset (true/false) of the codomain.
I’ve missed something in my explanation of models. Allow me to define them more precisely.
Intuitively, we want an “interpretation” of the sentences generated by a logic+language which assigns each to a truth value. Model theory formalizes this as an object+relation, but we can also look at it as a map from sentences onto Z_2.
Any such means of assigning a sentence to {true, false} (or equivalent) is an “interpretation” of sorts, but not necessarily a model. We reserve the term “model” specifically for not-stupid interpretations (ones where the interpretation maps “x” and “not x” to different values, etc.)
In your construction, when you consider a surjection from sentences to some set and pick one element of the range to be “truth”, you’ve essentially defined an interpretation in a roundabout way. (Every sentence mapped to 1 is true in that interpretation, every sentence mapped elsewhere is false in that interpretation.)
If your interpretation obeys the rules of logic (“x*y” maps to 1 whenever “x” maps to 1 and “y” maps to 1) then it’s a model. Otherwise, model theory doesn’t have much to say about it.
I’m not sure I understand the construct you’re describing: does the above help at all? I’m not sure if I’m answering the right questions.
Don’t worry about decidability in this context, I think it might be confusing things somewhat. The point I was making earlier about completeness is this:
If you consider the set of all sentences as the domain of your map, then a “theory” T is just a subset of the domain of your map. If there are multiple models (functions which obey the rules of the logic) from the set of all sentences onto Z_2 which map the subset of all sentences (theory) T to 1, then T is “incomplete”.
Thanks for this clarification. When I first read the sentence shminux quoted, I imagined that any assignment from sentences to truth values constituted a model, but then realized I was confused when I got to the sentence in the next paragraph saying that, “because there is no model of the theory of order which is also a model of [(∃x)¬(x≤x)].”
I thought, “What about the ‘model’ where you directly assign (∃x)¬(x≤x) to true as well as the sentences in the theory?” But if I understand correctly now, what I just described does not constitute a model. All models are maps from all sentences in a language to a truth value, but not all such maps are models.
Is there a straightforward way to describe which maps are allowed as models (of a given theory)? Is it something like—a model is any truth assignment that does not mark as false any sentences in the theory or any sentences that can be derived from the theory by constructing new sentences according to the rules of the logic?
Yes! I cover this in the first part of Very Basic Model Theory, the next post. “Model” is the name for the subset of mappings from sentences to truth values that interpret the logical symbols in a very specific way. See the linked post for details.
Not quite. It’s a map of the sentences generated by a language to Z_2. When we talk about “a model of a theory”, we’re discussing those maps for which all sentences in the theory under consideration are mapped to 1.
To put it another way, a model cannot map just a theory on to Z_2; every model must map every sentence to Z_2 one way or the other. Some theories are such that their models must make arbitrary choices for sentences “outside the theory”, this is precisely “incompleteness”.
But yeah, there’s use in mapping sentences to something larger than Z_2. Down this road lies multi-valued logics. And if you want to map sentences onto the interval [0, 1] you’re getting pretty close to probabilistic logic.
Note that in the referenced paper, the probability function is constructed from a measure of how many available models map a sentence to 1 rather than 0, which is an interesting way to map sentences onto a continuous interval.
So, any sentence that does not map to 1 is not in the model? I thought a model includes both true and false sentences. I guess I should instead think of a model as a preimage of a single element (conventionally called “truth”) in some surjective theory->image map. Or is it language->image map? Is model a subset of some theory or just of a language?
Every sentence of the language? And the theory is the preimage of 1? I’m confused. This can’t be right, since there can be multiple models for the same theory. Or do all models for a given theory have the same preimage of 1 but differ in other ways?
Does this mean “in an undecidable (unsatisfiable? incomplete?) language there is no map language->Z_2”?
Hmm, I think I’ve misunderstood you somewhere. By Z_2 you mean “integers modulo 2” (the set {0, 1}), correct? If you want to think of a model as a function from sentences onto {0, 1}, then sentences which map to “0″ in some model are indeed “not in the model”. (This phrasing is uncommon; sentences are not usually referred to as “in” a model. Rather, the model either holds / models / models as true or rejects / does not model / models as false each sentence.)
A sentence is neither true nor false except under consideration of a model. (Sentences true in every model are called “valid”, sentences false in every model are called “refutable”, but even then “truth” is a property assigned to sentences by models.) The sentences that a model models are true according to that model, so it’s tautologically true that a model does not hold any sentences that are “false in” (rejected by) that model.
If, by “true” and “false” you meant “valid” and “refutable”, then note that there are no models which model refutable sentences.
OK, so, if I understand you correctly, the following sequence is sensible, though not standard and probably backward:
We construct a surjective map from a given language+logic to some set.
We designate one element of the image as “1” or “true”.
We construct the preimage of 1, called “provably true sentences”.
We select a subset of the language+logic called a “theory”, based on some external semantic considerations.
The intersection of the theory and the set of provably true sentences is called the model of the theory in the language+logic with the map as given in step 1. (“The” model because to get a different model we have to change the map in step 1.)
This way if a theory is not a subset of the preimage of “1” (i.e. a set of provably true sentences), it is called incomplete, even though the model singled out in the theory by the map in step 1 is complete.
Am I off-base completely?
Still a little off base.
In this analogy, the map is playing the role of “model” (as it assigns sentences to the analog of truth values).
Note that in order for the map to be a model, the map must have certain behavior (whenever both φ and ψ map to 1, φ∧ψ also maps to 1, etc.). In model theory we restrict consideration to maps obeying these laws; if your map strays outside these boundaries then model theory has nothing to say about it.
In model theory, we say that a model is “of” a theory when the model holds true all sentences in the given theory. Thus, in your construction, the preimage of 1 would be the theory of the map (the largest theory that the map is a model of).
If you construct a different theory T that contains sentences not in the preimage of 1, then we would say the map is not a model of T (because there are sentences of T which are not “true” under the map).
The object you’re discussing in pt.5 (the intersection between the theory of a model and some other theory) does not have an obvious analog in model theory.
Thank you for your patience!
Hmm, I thought only the preimage of 1 is the model.
But… a theory can include sentences not in the preimage of 1 (undecidable?)… I am confused.
I would instead say that the preimage of 1 is the largest model of the map, and is the model of any “large enough” theory.
Where are these laws defined? In the logic? In the logic+language? Then the only “valid” maps are those which are homomorphisms (in some sense) from logic(?) to the Z_2 subset (true/false) of the codomain.
Thanks again!
I’ve missed something in my explanation of models. Allow me to define them more precisely.
Intuitively, we want an “interpretation” of the sentences generated by a logic+language which assigns each to a truth value. Model theory formalizes this as an object+relation, but we can also look at it as a map from sentences onto Z_2.
Any such means of assigning a sentence to {true, false} (or equivalent) is an “interpretation” of sorts, but not necessarily a model. We reserve the term “model” specifically for not-stupid interpretations (ones where the interpretation maps “x” and “not x” to different values, etc.)
In your construction, when you consider a surjection from sentences to some set and pick one element of the range to be “truth”, you’ve essentially defined an interpretation in a roundabout way. (Every sentence mapped to 1 is true in that interpretation, every sentence mapped elsewhere is false in that interpretation.)
If your interpretation obeys the rules of logic (“x*y” maps to 1 whenever “x” maps to 1 and “y” maps to 1) then it’s a model. Otherwise, model theory doesn’t have much to say about it.
I’m not sure I understand the construct you’re describing: does the above help at all? I’m not sure if I’m answering the right questions.
Don’t worry about decidability in this context, I think it might be confusing things somewhat. The point I was making earlier about completeness is this:
If you consider the set of all sentences as the domain of your map, then a “theory” T is just a subset of the domain of your map. If there are multiple models (functions which obey the rules of the logic) from the set of all sentences onto Z_2 which map the subset of all sentences (theory) T to 1, then T is “incomplete”.
OK, I think I have a clearer picture now, between yours and DavidS’s explanations. I only wish I had a chance to learn it in school. Thanks!
Thanks for this clarification. When I first read the sentence shminux quoted, I imagined that any assignment from sentences to truth values constituted a model, but then realized I was confused when I got to the sentence in the next paragraph saying that, “because there is no model of the theory of order which is also a model of [(∃x)¬(x≤x)].”
I thought, “What about the ‘model’ where you directly assign (∃x)¬(x≤x) to true as well as the sentences in the theory?” But if I understand correctly now, what I just described does not constitute a model. All models are maps from all sentences in a language to a truth value, but not all such maps are models.
Is there a straightforward way to describe which maps are allowed as models (of a given theory)? Is it something like—a model is any truth assignment that does not mark as false any sentences in the theory or any sentences that can be derived from the theory by constructing new sentences according to the rules of the logic?
Yes! I cover this in the first part of Very Basic Model Theory, the next post. “Model” is the name for the subset of mappings from sentences to truth values that interpret the logical symbols in a very specific way. See the linked post for details.
Thanks!