3 ms·

I didn’t see this one listed, and thought it was pretty cool when I studied it in a course a few years ago: https://en.m.wikipedia.org/wiki/Skolem's_paradox ht

I didn’t see this one listed, and thought it was pretty cool when I studied it in a course a few years ago: https://en.m.wikipedia.org/wiki/Skolem's_paradox https://en.m.wikipedia.org/wiki/Skolem's_paradox “ Skolem's paradox is that every countable axiomatisation of set theory in first-order logic, if it is consistent, has a model that is countable. This appears contradictory because it is possible to prove, from those same axioms, a sentence that intuitively says (or that precisely says in the standard model of the theory) that there exist sets that are not countable.” “ Skolem went on to explain why there was no contradiction. In the context of a specific model of set theory, the term "set" does not refer to an arbitrary set, but only to a set that is actually included in the model. The definition of countability requires that a certain one-to-one correspondence, which is itself a set, must exist. Thus it is possible to recognise that a particular set u is countable, but not countable in a particular model of set theory, because there is no set in the model that gives a one-to-one correspondence between u and the natural numbers in that model.”

H8crilA 5y ago
Just to make this more concrete: 1. There is a countable model of real numbers. 2. There even is a countable model of the entire set theory.
- Viliam1234 5y ago
  > There is a countable model of real numbers. What exactly happens when you try to apply Cantor's diagonal argument to this model? I guess that at some step, you get an answer like "outside of the model, yes this exists, but inside the model the answer is no", but I would like to see it precisely, how exactly the in-model reasoning diverges from the outside-model reasoning.
  - matt-noonan 5y ago
    Inside the model, “the reals are uncountable” means you have two sets R and N, and there is no surjective function from N onto R. That function would be a set as well; a certain subset F of NxR, say. But even if we can externally enumerate R, there is no reason to expect that our external enumeration corresponds to a set F that exists in the model.
  - Kranar 5y ago
    Consider that there are "real numbers" as in some kind of construct that we as humans are interested in understanding, and then there's ZFC-real numbers, which is an attempt to formalize "real numbers" rigorously. What we know is that we can never rigorously take "real numbers" and uniquely formalize them and so any formal investigation of "real numbers" will be prone to multiple interpretations. Given this, consider all models M that contain some set R(M) that satisfies ZFC's definition of real numbers and where R(M) is actually countable. Furthermore M also contains some set N(M) that satisfies ZFC's definition of natural numbers. Within this model M, since N(M) satisfies ZFC's definition of the naturals, it is ZFC-countable (that is it satisfies ZFC's definition of a countable set). Furthermore applying Cantor's diagonal argument to M, one can show that M does not contain a set that represents a surjection from N(M) to R(M), hence R(M) is ZFC-uncountable (it satisfies ZFC's definition of being uncountable). That said, all this means is that ZFC-countable, and ZFC-uncountable do not fully capture what it actually means to be countable or uncountable. ZFC-countable means a set has the same cardinality as whatever set satisfies ZFC's definition of natural numbers, which is not the same as what we as humans consider to be actual natural numbers. Similarly being ZFC-uncountable just means a set has a greater cardinality than the set that satisfies ZFC's definition of natural numbers, but that does not mean that such a set is actually uncountable. There is no way to extend ZFC so that what we consider to be actually countable or uncountable has one single unique interpretation. If there were then we could claim that said unique interpretation captured precisely our notion of countable and uncountable. What we can do is jump up a level to second order logic, and in that logic it actually is possible to have one unique interpretation of countable and uncountable sets so that there is a unique and countable set of naturals and a unique and uncountable set of reals, but second order logic comes with its own set of ambiguities and issues that for the most part mathematicians reject outright.
chriswarbo 5y ago
I like to think of this as a game, with one player choosing the axioms and the other choosing a model. If the first player picks a (countable) set of axioms, the second player can always respond with a countable model. Likewise, if the second player picks a countable model, the first player can always extend the axioms in a consistent way, to rule out that model. This can alternate back-and-forth forever. Uncountability is hence a 'leaky abstraction': something we want to investigate and study in general terms, even though particular occurances might have some loophole/edge-case. I think about infinity and infinitesimals in a similar way, like iterative processes (e.g. the natural numbers arise from a process that increments; calculus arises from iteratively shrinking 'dx', e.g. by halving; etc.). Combining/interleaving such processes is tricky, so it's often more convenient to take their limits individually and manipulate those as objects; that's justified if those manipulations could potentially be implemented by some interleaving, but can otherwise result in paradoxes (e.g. Thomson's lamp)

H8crilA 5y ago

Just to make this more concrete: 1. There is a countable model of real numbers. 2. There even is a countable model of the entire set theory.

Viliam1234 5y ago
> There is a countable model of real numbers. What exactly happens when you try to apply Cantor's diagonal argument to this model? I guess that at some step, you get an answer like "outside of the model, yes this exists, but inside the model the answer is no", but I would like to see it precisely, how exactly the in-model reasoning diverges from the outside-model reasoning.
- matt-noonan 5y ago
  Inside the model, “the reals are uncountable” means you have two sets R and N, and there is no surjective function from N onto R. That function would be a set as well; a certain subset F of NxR, say. But even if we can externally enumerate R, there is no reason to expect that our external enumeration corresponds to a set F that exists in the model.
- Kranar 5y ago
  Consider that there are "real numbers" as in some kind of construct that we as humans are interested in understanding, and then there's ZFC-real numbers, which is an attempt to formalize "real numbers" rigorously. What we know is that we can never rigorously take "real numbers" and uniquely formalize them and so any formal investigation of "real numbers" will be prone to multiple interpretations. Given this, consider all models M that contain some set R(M) that satisfies ZFC's definition of real numbers and where R(M) is actually countable. Furthermore M also contains some set N(M) that satisfies ZFC's definition of natural numbers. Within this model M, since N(M) satisfies ZFC's definition of the naturals, it is ZFC-countable (that is it satisfies ZFC's definition of a countable set). Furthermore applying Cantor's diagonal argument to M, one can show that M does not contain a set that represents a surjection from N(M) to R(M), hence R(M) is ZFC-uncountable (it satisfies ZFC's definition of being uncountable). That said, all this means is that ZFC-countable, and ZFC-uncountable do not fully capture what it actually means to be countable or uncountable. ZFC-countable means a set has the same cardinality as whatever set satisfies ZFC's definition of natural numbers, which is not the same as what we as humans consider to be actual natural numbers. Similarly being ZFC-uncountable just means a set has a greater cardinality than the set that satisfies ZFC's definition of natural numbers, but that does not mean that such a set is actually uncountable. There is no way to extend ZFC so that what we consider to be actually countable or uncountable has one single unique interpretation. If there were then we could claim that said unique interpretation captured precisely our notion of countable and uncountable. What we can do is jump up a level to second order logic, and in that logic it actually is possible to have one unique interpretation of countable and uncountable sets so that there is a unique and countable set of naturals and a unique and uncountable set of reals, but second order logic comes with its own set of ambiguities and issues that for the most part mathematicians reject outright.

chriswarbo 5y ago

I like to think of this as a game, with one player choosing the axioms and the other choosing a model. If the first player picks a (countable) set of axioms, the second player can always respond with a countable model. Likewise, if the second player picks a countable model, the first player can always extend the axioms in a consistent way, to rule out that model. This can alternate back-and-forth forever. Uncountability is hence a 'leaky abstraction': something we want to investigate and study in general terms, even though particular occurances might have some loophole/edge-case. I think about infinity and infinitesimals in a similar way, like iterative processes (e.g. the natural numbers arise from a process that increments; calculus arises from iteratively shrinking 'dx', e.g. by halving; etc.). Combining/interleaving such processes is tricky, so it's often more convenient to take their limits individually and manipulate those as objects; that's justified if those manipulations could potentially be implemented by some interleaving, but can otherwise result in paradoxes (e.g. Thomson's lamp)