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

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?
• Are you confusing this with Russell's paradox? Because once you have a containing set, any predicate F will then work for specification. – user4894 Apr 15 '17 at 13:56
• @user4894. It's a quotation of Parsons, and I doubt that he was confused. – user3017 Apr 15 '17 at 14:01
• (10) suggests but does not state that F ranges over "definite" (or "determinate") functions or properties. so it looks,circular to me - F could be "is a puff of smoke". – user20153 Apr 15 '17 at 19:09

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".

• What you say here appears to be correct, but I don't see how it answers the question. Parsons says that some predicates can be proven to not have sets as their extensions. Are you claiming as Eliran is that that simply refers to self-referential predicates, or is there something more to it? – user3017 Apr 20 '17 at 10:30
• @PédeLeão - I'm saying exactly what I've written... :-) The predicates x = x and x ∉ x are legitimate examples of Fx, from the "syntactical" point of view (i.e. according to the rules of the language); thus, they can be used in Separation. A different question is if the predicate x = x "defines" a set, and the answer is: NO, because Zermelo's axioms does not license us to prove the existence of the set { x | x = x }. – Mauro ALLEGRANZA Apr 20 '17 at 11:10
• According to my understanding, Parsons' paragraphi is a resumé of Zermelo's approach; if it is not clear enough, maybe is due to the fact that it is too short. I've tryied to provide the background... It is obviously incorrect (as you have noticed) to say that "Parsons is criticizing Zermelo's original axiom of separation for overlooking Russell's paradox." But of course you are free to decide what (if any) answer satisfy you :-) – Mauro ALLEGRANZA Apr 20 '17 at 11:13
• I understand what you wrote, but I don't see how it answers the question. I'm not asking about what Zermelo considered to be legitimate examples of Fx, but about the predicates that Parson's is referring to that don't have sets as their extensions. Are you saying that they are the same thing? Namely, x = x and x ∉ x? – user3017 Apr 20 '17 at 12:21
• @PédeLeão - exactly; but this is not "what Parsons is asserting"... It is a well-know result of Zermelo's set theory that (in the models of the theory) the sets { x | x = x } and { x | x ∉ x } do not exists. Thus, "it has been proved [that the "predicates" Fx:= (x = x) and Fx := (x ∉ x)] do not to have sets as their extensions." – Mauro ALLEGRANZA Apr 20 '17 at 12:26

A simple example is that of Russell's paradox. Consider the predicate 'xx', 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.

• Your answer suggests that Parsons is criticizing Zermelo's original axiom of separation for overlooking Russell's paradox. That strikes me as odd given that Wikipedia states: "[Russell's] paradox had been discovered a year before by Ernst Zermelo but he did not publish the idea." – user3017 Apr 15 '17 at 13:54
• The z in OP's formulation is the containing set. So either OP"s question is confused or else there's something else going on. – user4894 Apr 15 '17 at 13:55
• @user4894 I think Parsons is saying that Zermelo knew that the axiom of unrestricted comprehension would generate Russell's paradox, but that Zermelo (incorrectly) believed that his formulation of the axiom of separation in terms of "definite properties" above would sidestep the issue. That's why Parsons is pointing out that you can still regiment the axiom separation in second order logic in such a way that the paradox would occur. That's my read of the paragraph above at least. – shane Apr 15 '17 at 14:03
• @PédeLeão I was not suggesting that (you're right that it would be very odd). The very axiom in question is what prevents the paradox in ZF. But it isn't obvious whether the axiom should be formulated in first or second order logic, and that's what Parsons is discussing. I agree with shane's comment above. – Eliran Apr 15 '17 at 14:15