6 ms·

In the context of the Löwenheim–Skolem theorem and "Skolem's Paradox", what does it mean for 'the domain of a model to be countable'? My only guess is that the

In the context of the Löwenheim–Skolem theorem and "Skolem's Paradox", what does it mean for 'the domain of a model to be countable'? My only guess is that the number of 'objects and/or relations' in the model forms a set of countable size. Contrast this with the size of the objects in the model. e.g., if you have a set of countably infinite cardinality where the elements might be sets of uncountably infinite size.

lowdanie 6y ago
Indeed, the statement is that for any list of axioms there exists a countable set of objects satisfying them. For example, you could write down axioms for the real numbers by specifying that there should be relations called + and x with the standard properties such as commutativity, as well as an ordering relation < such that for all elements x and y there is an element z for which: x < z < y. Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well.
- pdonis 6y ago
  > Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well. You missed the crucial property that rules out the rationals (more precisely, the rationals with their standard ordering): one way of stating it is that every sequence that has an upper bound in the set, must have a least upper bound in the set. The rationals do not satisfy this property (for example, consider the sequence of successive decimal expansions, each one to one more decimal place, of sqrt(2)), but the reals do. The challenge for me is to understand how there can still be countable sets that also satisfy that property of the reals. (Obviously any countable set can be put into one-to-one correspondence with the rationals, but for a countable set that satisfies the least upper bound property of the reals, such a correspondence with the rationals would put an ordering on the rationals that was not the standard one.)
  - zzless 6y ago
    In fact, he did not miss anything. Using the language he started with (variables range over 'numbers', and the relations are <, >, +, and *), the reals and the rationals indeed have the same properties (elementary theory as logicians would put it). The reason things like \sqrt2 present no problems is that it is simply impossible to define such 'sequences of numbers' in this theory (you are only allowed to 'refer' to numbers by your variables, not ordinary sets and the usual language for sets is missing). If I remember right, the fact he was referring to was proved by Tarsky.
    - saithound 6y ago
      The reals and the rationals do not have the same elementary theory over the language (>,+,*).
      - zzless 6y ago
        You are correct, one would have to exclude the multiplication for that.
    - pdonis 6y ago
      > he reason things like \sqrt2 present no problems is that it is simply impossible to define such 'sequences of numbers' in this theory (you are only allowed to 'refer' to numbers by your variables, not ordinary sets and the usual language for sets is missing). Doesn't that mean that you can't even define the reals using the language he started with? If your language doesn't even let you express the difference between the reals and the rationals, it seems to me that the thing to do is to extend your language until it can.
      - Kranar 6y ago
        You're right that it is not possible to define the reals using the language he started with, but it's worse than that. It's also not possible to define the natural numbers using any first order theory. There is no way to extend a first order theory so that it defines the natural numbers and only the natural numbers and furthermore there is no way to define a first order theory that defines the reals and only the reals. Having said that, you were originally right that no theory of the reals can be satisfied by the rationals, but that's for a fairly unrelated reason.
- Kranar 6y ago
  >Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well. This wouldn't be correct, it's never the case that the set of rational numbers can satisfy a theory of real numbers, it's more subtle than that. It's that for any theory of the real numbers, there exist subsets of the real numbers that are countable that satisfy that theory. For example the subset of all computable real numbers will satisfy any theory of real numbers despite it being countable. It's simply not possible to define a first order theory that describes the real numbers as a whole and only the real numbers as a whole. However, there will never be any theory of real numbers that can be satisfied by the set of rational numbers. At a minimum any theory of real numbers would imply theorems that require the existence of a number that when squared was equal to 2. The rational numbers can not satisfy such a theorem.
tprice7 6y ago
I'm rusty with this stuff but I'm pretty sure your guess is correct, a countable model is one with countably many objects. For other readers who might not be familiar, I'll mention that Skolem's paradox is about how there are countable models of set theory, and yet it is a theorem of set theory that uncountable sets exist, so these countable models must contain sets that are uncountable according to the model. I think it seems less paradoxical if you think of it like this: in order for a set to be countable, there needs to exist an injection from that set to the natural numbers. So a countable model can have a set that internally looks uncountable: there is in fact an injection from that set to the natural numbers, it's just that the injection isn't included in the model.
deleted 6y ago
[deleted]
dwohnitmok 6y ago
In short: They both rely on a "background model" that you are implicitly working in. The "background model" and the model in discussion then disagree on which sets are countable. That is e.g. you fix some model (perhaps a model that satisfies ZFC). Then you work within that model to create a submodel .You can then describe the submodel using properties of the outer model. In fact it turns out that you can have submodels of ZFC that are proper sets in the outer model, i.e. a single set can contain an entire subuniverse of sets that themselves satisfy the entirety of the ZFC axioms. Using the outer model you can then talk about global properties of the submodel. In the case of the Löwenheim–Skolem theorem it turns out that you can have a submodel satisfying the axioms of ZFC that can have arbitrary infinite cardinality in the outer model. In particular you can have a submodel of ZFC that has only a countably infinite number of sets as measured by the outer model. And in fact every element of that set can also be a set of countably infinite size according to the outer model. According to the submodel there is no notion of the cardinality of itself, since ZFC does not have a set of all sets. Likewise the submodel "thinks" many sets within it are countably infinite. This is how the submodel is able to still satisfy ZFC. However, the outer model disagrees with the submodel and instead thinks that the submodel is "impoverished." The submodel is missing the functions that it needs to "realize" that bijections exist between certain sets. These functions exist in the outer model.
- dwohnitmok 6y ago
  > Likewise the submodel "thinks" many sets within it are countably infinite. I meant uncountably infinite.

lowdanie 6y ago

Indeed, the statement is that for any list of axioms there exists a countable set of objects satisfying them. For example, you could write down axioms for the real numbers by specifying that there should be relations called + and x with the standard properties such as commutativity, as well as an ordering relation < such that for all elements x and y there is an element z for which: x < z < y. Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well.

pdonis 6y ago
> Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well. You missed the crucial property that rules out the rationals (more precisely, the rationals with their standard ordering): one way of stating it is that every sequence that has an upper bound in the set, must have a least upper bound in the set. The rationals do not satisfy this property (for example, consider the sequence of successive decimal expansions, each one to one more decimal place, of sqrt(2)), but the reals do. The challenge for me is to understand how there can still be countable sets that also satisfy that property of the reals. (Obviously any countable set can be put into one-to-one correspondence with the rationals, but for a countable set that satisfies the least upper bound property of the reals, such a correspondence with the rationals would put an ordering on the rationals that was not the standard one.)
- zzless 6y ago
  In fact, he did not miss anything. Using the language he started with (variables range over 'numbers', and the relations are <, >, +, and *), the reals and the rationals indeed have the same properties (elementary theory as logicians would put it). The reason things like \sqrt2 present no problems is that it is simply impossible to define such 'sequences of numbers' in this theory (you are only allowed to 'refer' to numbers by your variables, not ordinary sets and the usual language for sets is missing). If I remember right, the fact he was referring to was proved by Tarsky.
  - saithound 6y ago
    The reals and the rationals do not have the same elementary theory over the language (>,+,*).
    - zzless 6y ago
      You are correct, one would have to exclude the multiplication for that.
  - pdonis 6y ago
    > he reason things like \sqrt2 present no problems is that it is simply impossible to define such 'sequences of numbers' in this theory (you are only allowed to 'refer' to numbers by your variables, not ordinary sets and the usual language for sets is missing). Doesn't that mean that you can't even define the reals using the language he started with? If your language doesn't even let you express the difference between the reals and the rationals, it seems to me that the thing to do is to extend your language until it can.
    - Kranar 6y ago
      You're right that it is not possible to define the reals using the language he started with, but it's worse than that. It's also not possible to define the natural numbers using any first order theory. There is no way to extend a first order theory so that it defines the natural numbers and only the natural numbers and furthermore there is no way to define a first order theory that defines the reals and only the reals. Having said that, you were originally right that no theory of the reals can be satisfied by the rationals, but that's for a fairly unrelated reason.
Kranar 6y ago
>Clearly the real numbers are a model for these axioms. But as it turns out the countable set of rational numbers is a model as well. This wouldn't be correct, it's never the case that the set of rational numbers can satisfy a theory of real numbers, it's more subtle than that. It's that for any theory of the real numbers, there exist subsets of the real numbers that are countable that satisfy that theory. For example the subset of all computable real numbers will satisfy any theory of real numbers despite it being countable. It's simply not possible to define a first order theory that describes the real numbers as a whole and only the real numbers as a whole. However, there will never be any theory of real numbers that can be satisfied by the set of rational numbers. At a minimum any theory of real numbers would imply theorems that require the existence of a number that when squared was equal to 2. The rational numbers can not satisfy such a theorem.

tprice7 6y ago

I'm rusty with this stuff but I'm pretty sure your guess is correct, a countable model is one with countably many objects. For other readers who might not be familiar, I'll mention that Skolem's paradox is about how there are countable models of set theory, and yet it is a theorem of set theory that uncountable sets exist, so these countable models must contain sets that are uncountable according to the model. I think it seems less paradoxical if you think of it like this: in order for a set to be countable, there needs to exist an injection from that set to the natural numbers. So a countable model can have a set that internally looks uncountable: there is in fact an injection from that set to the natural numbers, it's just that the injection isn't included in the model.

deleted 6y ago

[deleted]

dwohnitmok 6y ago

In short: They both rely on a "background model" that you are implicitly working in. The "background model" and the model in discussion then disagree on which sets are countable. That is e.g. you fix some model (perhaps a model that satisfies ZFC). Then you work within that model to create a submodel .You can then describe the submodel using properties of the outer model. In fact it turns out that you can have submodels of ZFC that are proper sets in the outer model, i.e. a single set can contain an entire subuniverse of sets that themselves satisfy the entirety of the ZFC axioms. Using the outer model you can then talk about global properties of the submodel. In the case of the Löwenheim–Skolem theorem it turns out that you can have a submodel satisfying the axioms of ZFC that can have arbitrary infinite cardinality in the outer model. In particular you can have a submodel of ZFC that has only a countably infinite number of sets as measured by the outer model. And in fact every element of that set can also be a set of countably infinite size according to the outer model. According to the submodel there is no notion of the cardinality of itself, since ZFC does not have a set of all sets. Likewise the submodel "thinks" many sets within it are countably infinite. This is how the submodel is able to still satisfy ZFC. However, the outer model disagrees with the submodel and instead thinks that the submodel is "impoverished." The submodel is missing the functions that it needs to "realize" that bijections exist between certain sets. These functions exist in the outer model.

dwohnitmok 6y ago
> Likewise the submodel "thinks" many sets within it are countably infinite. I meant uncountably infinite.