Can a model be countable from its own perspective ?

[mpitluk]

Can a model be countable from its own "perspective"?

I'm reading about Skolem. And I'm wondering about the result of the paradox: that countability (at least in first-order formulations) is relative. Now, even when we state Skolem's theory -- if a first-order theory has an infinite model then it has a countable model -- from what "perspective" is this model countable? From another model? Absolutely?

If we say that a model M is countable "from its own perspective" that means there is some bijection (set) B in the domain of M containing every set in the domain of M (including B) and the set of natural numbers. But that can't happen, because then B would be a member of itself.

So, when we casually talk about countability, we take it to be an absolute notion. But, what does this say about Skolem's Paradox?

 

[Hurkyl]

Now, even when we state Skolem's theory -- if a first-order theory has an infinite model then it has a countable model -- from what "perspective" is this model countable?

The same "perspective" from which we are using the words like 'theory' and 'model'.

 

[Amir Livne]

A model can be countable from its own perspective, in some sense. It depends what other axioms it satisfies in addition.

If a model (which is a set for the universe and a 2-relation on it for membership) contains the set ω and a function from ω to the universe it can be said to be countable. This cannot happen in a standard model, which has the normal membership as its membership relation, since then you'd have an infinite decreasing series of sets.

But if you don't require your model to have the axiom of Regularity, you can have a function between a set and the universe.

 

[mpitluk]

If a model (which is a set for the universe and a 2-relation on it for membership) contains the set ω and a function from ω to the universe it can be said to be countable. This cannot happen in a standard model, which has the normal membership as its membership relation, since then you'd have an infinite decreasing series of sets.

What is a standard model?--a model that satisfies the standard first-order ZFC axioms? And what is an infinite decreasing series of sets? Also, must a countable model contain the natural numbers? It seems like it is not necessary, as we have been saying that (typically?) saying a model is countable is really a statement made from "outside" the model.

But if you don't require your model to have the axiom of Regularity, you can have a function between a set and the universe.

I gave a kind of explanation of why I thought that you couldn't have model say of itself that it is countable: because then there would be a set S containing the domain and the natural numbers. But since S is in the domain, it would be a proper subset of itself. Does this assume regularity?

 

[Amir Livne]

What is a standard model?--a model that satisfies the standard first-order ZFC axioms?

A standard model is one where the elements of the universe are sets, and the membership relation is the normal membership relation. In symbols, [itex]\mathcal{M} \models x \in y[/itex] is true iff [itex]x \in y/itex]

And what is an infinite decreasing series of sets?

I'm not sure about my English here. I meant a phenomenon like [itex]A_{1} \ni A_{2} \ni A_{3} \ni \ldots[/itex]. This cannot happen with normal sets, which obey the axiom of regularity: every set has a minimal element w.r.t the membership relation. In other words, [itex]\forall A. \exists B \in A. A \cap B = \emptyset[/itex]. This fails for the set [itex]\{A_{1}, A_{2}, \ldots\}[/itex].

Also, must a countable model contain the natural numbers? It seems like it is not necessary, as we have been saying that (typically?) saying a model is countable is really a statement made from "outside" the model.

It kind of depends on what you mean by "model"... Some of the constructions in the study of models of set theory are called models but don't contain all the natural numbers. If your model satisfies the empty set axiom and the pairing axiom, it will contain all of the natural numbers.

But the good question is - how can a model even say about itself that it is countable? A set [itex]A[/itex] is countable in the model [itex]\mathcal{M}[/itex] if
[tex]\mathcal{M} \models \exists f. \left[ f\ consists\ of\ pairs \wedge \mathrm{dom} f = \omega \wedge \mathrm{rng} f = A \wedge \neg\exists(a_{1},b_{1}),(a_{2},b_{2})\in f. (a_{1} = a_{2} \wedge b_{1} \neq b_{2}) \right][/tex]
This says [itex]f[/itex] is a function from the natural numbers to [itex]A[/itex]. Actually the formula will be a bit nore complicated since you need to define the natural numbers, but let's ignore this difficulty. This formula cannot work for the whole universe since it is not a set in models we want to consider. But you can write a similar formula that captures the idea os a function from a set to the universe:
[tex]\mathcal{M} \models \exists f. \left[ f\ consists\ of\ pairs \wedge \mathrm{dom} f = \omega \wedge \forall A.\exists (a,b)\in f. (b = A) \wedge \neg\exists(a_{1},b_{1}),(a_{2},b_{2})\in f. (a_{1} = a_{2} \wedge b_{1} \neq b_{2}) \right][/tex]

It is possible to include such a function in your model, but it will have to be very crippled. For example, the axiom of union will give you a set of all sets. But you could make up such a model. Writing it down completely is a mess but the idea is to have the minimum of sets required: the natural numbers, [itex]\omega[/itex] itself, the pairs that make up your function and the function itself.

I gave a kind of explanation of why I thought that you couldn't have model say of itself that it is countable: because then there would be a set S containing the domain and the natural numbers. But since S is in the domain, it would be a proper subset of itself. Does this assume regularity?

This is not related to countability I think. For the model to "speak" about itself in terms that are relevant for sets, it usually needs to be a set of the same model, thich fails the axiom of regularity (among others; even without regularity, you'd have Cantor's paradox). With standard models this is genuinely impossible, but with nonstandard models you can have it: e.g. [itex]M = \{0,1,V\}[/itex] with membership defined by [itex]0 \in 1, 0 \in V, 1 \in V, V \in V[/itex]. This is a model with an empty set, a nonempty set, and a universal set. Not a very interesting one though.

 

[mpitluk]

A standard model is one where the elements of the universe are sets, and the membership relation is the normal membership relation. In symbols, [itex]\mathcal{M} \models x \in y[/itex] is true iff [itex]x \in y/itex]
I'm not sure about my English here. I meant a phenomenon like [itex]A_{1} \ni A_{2} \ni A_{3} \ni \ldots[/itex]. This cannot happen with normal sets, which obey the axiom of regularity: every set has a minimal element w.r.t the membership relation. In other words, [itex]\forall A. \exists B \in A. A \cap B = \emptyset[/itex]. This fails for the set [itex]\{A_{1}, A_{2}, \ldots\}[/itex].
It kind of depends on what you mean by "model"... Some of the constructions in the study of models of set theory are called models but don't contain all the natural numbers. If your model satisfies the empty set axiom and the pairing axiom, it will contain all of the natural numbers.

But the good question is - how can a model even say about itself that it is countable? A set [itex]A[/itex] is countable in the model [itex]\mathcal{M}[/itex] if
[tex]\mathcal{M} \models \exists f. \left[ f\ consists\ of\ pairs \wedge \mathrm{dom} f = \omega \wedge \mathrm{rng} f = A \wedge \neg\exists(a_{1},b_{1}),(a_{2},b_{2})\in f. (a_{1} = a_{2} \wedge b_{1} \neq b_{2}) \right][/tex]
This says [itex]f[/itex] is a function from the natural numbers to [itex]A[/itex]. Actually the formula will be a bit nore complicated since you need to define the natural numbers, but let's ignore this difficulty. This formula cannot work for the whole universe since it is not a set in models we want to consider. But you can write a similar formula that captures the idea os a function from a set to the universe:
[tex]\mathcal{M} \models \exists f. \left[ f\ consists\ of\ pairs \wedge \mathrm{dom} f = \omega \wedge \forall A.\exists (a,b)\in f. (b = A) \wedge \neg\exists(a_{1},b_{1}),(a_{2},b_{2})\in f. (a_{1} = a_{2} \wedge b_{1} \neq b_{2}) \right][/tex]

It is possible to include such a function in your model, but it will have to be very crippled. For example, the axiom of union will give you a set of all sets. But you could make up such a model. Writing it down completely is a mess but the idea is to have the minimum of sets required: the natural numbers, [itex]\omega[/itex] itself, the pairs that make up your function and the function itself.
This is not related to countability I think. For the model to "speak" about itself in terms that are relevant for sets, it usually needs to be a set of the same model, thich fails the axiom of regularity (among others; even without regularity, you'd have Cantor's paradox). With standard models this is genuinely impossible, but with nonstandard models you can have it: e.g. [itex]M = \{0,1,V\}[/itex] with membership defined by [itex]0 \in 1, 0 \in V, 1 \in V, V \in V[/itex]. This is a model with an empty set, a nonempty set, and a universal set. Not a very interesting one though.

Thanks for this great answer.

Why is it impossible for a standard model to say of itself that it is countable?