How can certain predicates be proven to not have sets as their extension?

Question

In Mathematical Thought and Its Objects, Charles Parsons says the following:

As Zermelo originally stated the axiom of separation, it is that for any “definite” propositional function P and any set a, there is a set b consisting of exactly those elements of a for which P holds. Whatever he may have meant by a “definite” propositional function or property, it seems clear that it can be regimented by some kind of second-order logic, and we can state the axiom as

(10) (∀z)(∀F)(∃y)(∀x)[x ∈ y ↔ (x ∈ z ∧ Fx)].

But in applying the axiom, one instantiates for the variable ‘F’ predicates that have not been determined to have sets as their extensions and in fact many predicates that can be proved not to have sets as their extensions.

My question is:

• What sort of predicates can be said to not have sets as their extensions?
• How might an argument proceed to prove such a thing?

Answer 1

Parsons' comment is relative to the original (1908) Zermelo's axiomatization of set theory.

One of the weak point of the axiomatization was the use of the vague concept of "definite property" in the statement of Separation Axiom:

Whenever the propositional function Fx is definite for all elements of a set M ... [“Klassenaussage F(x) definit fur alle Elemente einer Menge M...”]

In his mature (1930) axiomatization, Zermelo explicitly uses second-order logic in the formulation:

Axiom of separation: Every propositional function F(x) separates from every set m a subset mF containing all those elements x for which F(x) is true. Or: To each part of a set there in turn corresponds a set containing all elements of this part.

In 1929, Zermelo redefined the set of "allowed" propositional functions as those expressions

constructed from the fundamental relations of the system only by virtue of the logical elementary operations of negation, conjunction and disjunction, as well as quantification, all these operations in arbitrary yet finite repetition and composition.

If we formalize it, we get exactly Parsons' formulation:

(∀z)(∀F)(∃y)(∀x)[x ∈ y ↔ (x ∈ z ∧ Fx)]

where Fx is a propositional function built up from "fundamental relations".

For set theory, the fundamental relations are like:

x=y and x ∈ y.

Thus, x=x and the "paradoxical" x ∉ x are allowed, because they are well-formed expressions.

But the well-known Russell's paradox is blocked because we have no "universal set" z to use with Separation in order to "cut out" from it the set y of all and only those x such that: x ∈ z ∧ x ∉ x.

Thus, the "legitimate" predicate x=x does not define a set, because there is no way, with Zermelo's axioms, to prove that the set { x | x = x } exists.

What we can do, with Separation, is to prove that, for any existsing set z, the subset of z : { x | x ∈ z ∧ x = x } exists.

Another example can be found with Cantor's Paradox (1897): assume that we can define a predicate Card(x) such that Card(c) holds iff c is a cardinal number. Then the set { x | Card(x) } does not exists.

The paradoxes related to "size", like Russell's and Cantor's one, are blocked by the restriction imposed by Separation to comprehension.

The formal condition of "definiteness" stated by Zermelo is aimed at ruling out a different family of paradoxes: the so-called "semantical" antinomies, like the Richard and Konig's ones, because an expression like e.g. "definable in English by a finite number of words" is not expressible by way of "fundamental relations".

Answer 2

A simple example is that of Russell's paradox. Consider the predicate 'x ∉ x', where x is free. In standard set theory (ZF) there is no set corresponding to that predicate.

Indeed, one of the causes of the paradox is the assumption that for every predicate there is a set that is its extension. This assumption is the unrestricted comprehension axiom in naive set theory. In ZF it is replaced by the restricted comprehension axiom (also called axiom of separation), which does not share that assumption.