0
$\begingroup$

When we do set theory, we take our first-order variables to range over all sets. But if we take our second-order variables to range over sets of sets in the range of the first-order variables, then second-order comprehension will fail. A simple instance of second-order comprehension such as $\exists X\forall y (Xy \longleftrightarrow y \not\in y)$ will be false on account of Russell’s paradox, according to which no set contains all and only those sets that are not members of themselves.

This doesn't seem correct, but I don't see how it can be avoided without bringing in a class/set distinction which isn't in the axiom as presented in shaprio 1991 for example.

$\endgroup$
  • 4
    $\begingroup$ $y \not \in y$ is not a valid formula of second order logic; the $\in$ relation can only be between a first-order variable and a second-order variable. $\endgroup$ – Carl Mummert Apr 12 '16 at 14:20
4
$\begingroup$

In Second-order Logic, the comprehension schema (considering for simplicity only unary predicate variables) is:

$∃X∀x [ \varphi(x) ↔ X(x) ]$,

where $x$ is an individual variable, $X$ is a unary predicate variable and $X$ does not occur free in $\varphi$.

What prevents form generating inconsistencies ?

The proviso that $X$ is not free in $\varphi$ prevents from using $\lnot X(x)$ to get:

$∃X∀x [ \lnot X(x) ↔ X(x) ]$.

$\endgroup$
2
$\begingroup$

In second-order set theory the second-order quantifier is quantifying classes. And indeed in $\sf ZFC$ there exists a class of exactly those sets which are not members of themselves: it's called the universe.

Also, it might be worth pointing out that second-order $\sf ZF$ is considered with a second-order Replacement axiom schema, rather than a Comprehension schema.

The idea is to compare this to "other" worlds where we use second-order logic. Over the natural numbers the second-order is about sets of numbers, not numbers, namely a collection of numbers; over the real numbers we quantify over a collection of real numbers; in topology we quantify over a collection of open sets, and so on.

So in set theory, the second-order quantification is over collections of objects, which are called classes since the first-order objects are called sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.