2
$\begingroup$

How is uncountability characterized in second order logic?

Also, why is this characterization of uncountability "absolute" in the way that FOL's characterization of uncountability is not?

A very direct answer will be much appreciated.

Much thanks.

  • 0
    Yes indeed, this would be more appropriate at [math.se]. I'll move it there.2012-06-11

2 Answers 2

3

The definition of uncountability is essentially the same as it is in first order logic: a set $X$ is uncountable if there is no surjective function $F$ from the natural numbers $\mathbb{N}$ onto $X$ (there are other ways of formulating uncountability, but they are equivalent to this definition).

Consequently in order to provide a formal definition in second order logic we must first define the following: the set of natural numbers $\mathbb{N}$; functions and their properties in second order logic; and finally the definition of uncountability.


Let's start with functions. Let $F$ be a unary function symbol, and let the domain of $F$ be given as

$$ \mathrm{dom}(F) = \left\{ x : \exists{y} (F(x) = y) \right\} $$

while the range of $F$ is

$$ \mathrm{ran}(F) = \left\{ y : \exists{x} (F(x) = y) \right\}. $$

These sets exist via the second order comprehension scheme.


Now we characterise the natural numbers $\mathbb{N}$ in second order logic. Given a function symbol $S$ for the successor function and a constant symbol $0$, the natural numbers is the set satisfying the following axioms. By a theorem of Dedekind, this suffices to characterise the natural numbers up to isomorphism.

$$ \forall{x}(0 \neq S(x)) \\ \forall{n}\forall{m} (S(n) = S(m) \rightarrow n = m) \\ \forall{P} ( P(0) \wedge \forall{n} (P(n) \rightarrow P(S(n))) \rightarrow \forall{n} (P(n)). $$


Finally we are in a position to present a definition of uncountability in second order logic. A set $X$ is countable just in case it satisfies the following definition.

$$ \mathrm{countable}(X) =_{df} \exists{F} (\mathrm{dom}(F) = \mathbb{N} \wedge \mathrm{ran}(F) = X \wedge \forall{x \in X}\exists{y \in \mathbb{N}} (F(y) = x). $$

The definition of uncountability is then just the negation of the countability condition.


The question of why this characterisation is 'absolute' in a way that the first order characterisation is not can be found in the Dedekind categoricity theorem cited above. Given the standard semantics for second order logic, all structures satisfying the second order Peano axioms are isomorphic—the theory is categorical.

Because of this, the Löwenheim–Skolem theorem is false for second order logic (with the standard semantics), so the kind of model-theoretic relativity you get in first order logic does not appear (at least to the same extent). We don't get models where the whole domain is countable (from the 'external' perspective), but the model itself thinks that there are uncountable sets just because certain functions don't exist.

4

There are slightly faster ways to define countability and uncountability in second-order logic, using more knowledge of the ambient set theory to avoid having to refer to axioms of arithmetic. In particular we can use the fact that "countable" is the smallest infinite cardinality.

First, a set $X$ is infinite if there is a function from that set to itself that is injective but not surjective. That can be expressed as a formula $\operatorname{Inf}(X)$ in second-order logic with only the equality relation, by quantifying over functions. Now a set $X$ is countably infinite if if is infinite and for every infinite subset $Y$ of $X$ there is a bijection from $Y$ to $X$. This can also be expressed as a formula of second order logic. Finally, a set is uncountable if it is infinite and not countable.

  • 1
    You can also write that $X$ is uncountable if it is infinite and has an infinite subset $Y$ but $X$ and $Y$ are not in bijection.2012-06-12
  • 0
    @CarlMummert: I checked out your [answer](http://math.stackexchange.com/questions/31826/what-are-natural-numbers?rq=1) to [What are the natural numbers](http://math.stackexchange.com/questions/31826/what-are-natural-numbers) and it seemed relevant here, esp.: "The question of which model of the second-order Peano axioms is really the "natural numbers" is like the question of which isomorphic copy of F2 is "really" F2. It's a fine question for philosophers, but as mathematicians we have a perfectly good idea what F2 is, up to isomorphism, and a good idea what ℕ is, up to isomorphism." (cont...)2012-06-13
  • 0
    @CarlMummert: ... Does the same idea apply to $\omega_1$ in SO formulations of ZFC? Can I just replace ℕ with $\omega_1$? E.g.: "The question of which model of the second-order ZFC axioms is really $\omega_1$ is like the question of which isomorphic copy of F2 is "really" F2. It's a fine question for philosophers, but as mathematicians we have a perfectly good idea what F2 is, up to isomorphism, and a good idea what $\omega_1$ is, up to isomorphism." Does that work?2012-06-13
  • 0
    @CarlMummert: If so, then there seems to be a subtle distinction: uncountability is absolute in ZFC but only to the extent that all models of the second-order ZFC axioms understand what $omega_1$ is **up to isomorphism**, that is, there is not ***a*** absolute notion of uncountability. So, if someone asked the philosophical question: does SOL capture the absoluteness of uncountability? Mathematics proper can only say, "Yes, but only up to isomorphism."2012-06-13
  • 0
    @pichael: Note that SOL formulation of ZFC is a bit problematic in a philosophical sense: SOL requires a notion of sets to exist already, but sets are usually taken as elements in a model of some set theory. So you cannot *really* use SOL ZFC as a foundation, but rather use it when talking about sets which are already models of [FOL] ZFC. There's nothing wrong with that, but it's a caveat that should be mentioned.2012-06-13
  • 0
    @Asaf: OK that makes sense. To clarify some things: (1) "There's nothing wrong with that" -- what is "that" referring to? (2) I'm not explicitly seeing the problem between (a) SOL requiring sets to already exist, (b) set's usually being taken as elements in a model of some set theory, and (c) taking SOL ZFC as foundational. Is it because SOL uses already existing sets that must have been "built" from somewhere -- that is, somewhere like FOL ZFC?2012-06-13
  • 0
    @pichael: (1) Considering a model of SOL ZFC; (2) yes, as you say we need to have sets from somewhere, and foundational theories suppose to be the "ground" on which you grow the rest of the mathematical notions. SOL assumes that the notion of "set" is already defined, which if you think about it for a minute, means that there was some other theory "below" which told us what exactly is a set (our naive grasp of the concept simply sucks), so SOL theories are not *really* foundational because of that, in particular SOL ZFC.2012-06-13
  • 0
    @Asaf: Awesome, that is so helpful. So you can't _really_ reject the relativity of cardinality in FOL on the grounds that SOL offers an absolute notion of cardinality because, in a sense, FOL grounds SOL -- although, I'm not sure in what sense of "grounding" (logically? conceptually? set-buildingly?) hence philosophy.SE...2012-06-13
  • 2
    @Asaf: an interesting point is that the consistency of ZFC is usually justified by arguing that the axioms hold for the collection of "all sets" - that is, the cumulative hierarchy - which is exactly what the second order quantifiers in second order ZFC want to quantify over. So if we want to say that second order ZFC is not well specified, we also have to give up the idea that the "standard model" of ZFC is well specified.2012-06-14
  • 0
    @pichael: unfortunately, this comment thread is too small to contain a full discussion of whether second order logic with full semantics is coherent. Philosophers argue both ways, it's a complicated issue. But you are right that in general mathematical axioms only capture things up to isomorphism; that idea is the basis for the branch of mathematical philosophy known as structuralism.2012-06-14