0
$\begingroup$

I'm reading Jech/Hrbacek's: Introduction to Set Theory.

Notice that the definition of the constant $\emptyset$ is justified by the Axiom of Existence and Lemma $3.1$

Intuitively, sets are collections of objects sharing some common property, so we expect to have axioms expressing this fact. But, as demonstrated by the paradoxes in Section $1$, not every property describes a set; properties "$X\not\in X$" or "$X=X$" are typical examples

In both cases, the problem seems to be that in order to collect all objects having such a property into a set, we already have to be able to perceive all sets. The difficulty is avoided if we postulate the existence of a set of all objects with a given property only if there already exists some set to which they belong.

The Axiom Schema of Comprehension: Let $\textbf P(x)$ be a property of $x$. For any set $A$, there is a set $B$ such that $x\in B$ if and only if $x \in A$ and $\textbf P(x)$.

What does the author mean by the part in italics? My guess is that "perceive all sets" mean having all sets at hand which in the course of the abstraction doesn't really matter, while doing the suggested fix, we can think: If such and such happens, then something happens. (I guess in this case, we don't need to be sure that the set exist in question exists). Is this it?

$\endgroup$
  • $\begingroup$ I am not quite sure either. One big thing the axiom of (restricted) comprehension does is prevent Russell's paradox. I think what he might be getting at is that in order to apply unrestricted comprehension, you need knowledge of all sets to pick out one satisfying your property. $\endgroup$ – TokenToucan Mar 13 '16 at 7:22
  • $\begingroup$ The part in italics adds nothing really. It could probably be left out altogether. $\endgroup$ – Dan Christensen Mar 13 '16 at 14:11
1
$\begingroup$

Consider the notion of set introduced by Cantor in 1879 :

I say that a manifold (a collection, a set) of elements that belong to any conceptual sphere is well-defined ["Eine Mannichfaltigkeit (ein Inbegriff, eine Menge) von Elementen, die irgend welcher Begriffsphare angehoren"]

followed in 1883 by the "mature" concept :

By a manifold or a set I understand in general every Many that can be thought of as One, i.e., every collection of determinate elements which can be bound up into a whole through a law, and with this I believe to define something that is akin to the Platonic εἶδος or ἰδέα. ["Unter einer Mannichfaltigkeit oder Menge ...].

In the first "definition" we have sets as collections "of elements that belong to any conceptual sphere", like e.g. the "conceptual sphere" of the Euclidean plane "made of" points: we can define e.g. the triangle as a particular (i.e. satisfying a certain property) collection of point belonging to the plane.

But what about the more "mature" concept, where we consider "pure" sets ? We are considering the "conceptual sphere" of sets itself: in this case we have, in some vague sense, to consider them "already there":

we already have to be able to perceive all sets [as existing].

According to this "natural" point of view, Cantor and others used the so-called "naive" Comprehension Axiom; the idea behind Comprehension Axiom is that for every condition that we can "imagine" there is a set containing all and only those objects that satisfy the condition.

Rephrased in first-order language, it becomes : for every condition that we can express in the language, i.e. for every formula $\phi(x)$ with $x$ free, there exists the set of those objects such that ...

Unfortunately, a simple argument based on it allowed Russell to derive his Paradox.

In order to avoid this paradox (and others) different solutions are available; for example, restrict the possible "conditions" that can be used in the Comprehension Axiom.

The solution formulated by Zermelo (1908) and improved subsequently by Fraenkel and Skolem, is based on the Axiom (Schema) of Separation (or Specification): a "condition" can be applied to "generate" a new set only starting from an already existing set (i.e. "separating" it from the already existing domain of sets).


See The Early Development of Set Theory.

$\endgroup$
1
$\begingroup$

perceive

This means: within the scope of first-order logic. The process of forming sets by filtering a bigger collection by some first-order predicate should ideally only apply to bigger collections that are actually sets.

perceive all sets

This means: paradoxes like Russell's paradox hinge on the assumption that the collection $\mathbf{Set}$ of all sets is a set. If it isn't, then the Axiom you quoted ensures you can't form the subset of $\mathbf{Set}$ of all sets that don't contain themselves.

$\endgroup$
1
$\begingroup$

The sentence you've quoted in italics is weird, not only because it is vague but because it is in some sense wrong or at least misleading.

Consider the fact that the quantifiers themselves 'perceive' all elements in the domain of discourse, in that the quantified statements are either true or false, as if the domain is already there and the statements hence have a truth value. So what could it possibly mean that we cannot 'perceive' all sets?

One might say, perhaps it is intended to mean that we cannot 'perceive' of the collection of all sets, but that is silly; of course we can. Not only that, this collection is first-order definable! If you look at all the first-order formulae in one free variable, each of them defines a collection of all elements that satisfy it. Consider that the empty set, which is assumed to exist (or follows from the other less self-evident axioms), and corresponds to the formula "$x \ne x$" or more simply "$\bot$". Is it reasonable to say that this formula is privileged as compared to "$x = x$" or "$\top$"? In terms of what we intuitively can talk about, of course not.

Furthermore, it is not only that we can perceive such collections, but we in fact do so in many areas of mathematics even though it is technically not allowed in ZFC! Here are some examples:

  1. We make statements like "Let $diam(G)$ be the maximum distance between two vertices of $G$, for every finite (unweighted) graph $G$." Every graph theorist who reads this automatically treats $diam$ as a function with input being a finite graph and output being a natural number. But in ZFC there is simply no such function, because existence of such a function would imply a contradiction!

  2. We talk about the class of ordinals or of cardinals, or other kinds of classes. As with the above example, often there is some syntactic trick to talk about the objects in such classes without ever forming the collection, but most mathematicians are not familiar with set theoretic issues and treat these as collections anyway. Some set theorists also prefer to work in Morse-Kelley set theory which can be understood to assume that every object is a class of sets and that some classes are themselves sets, and so it makes it convenient to talk about collections like the class of finite graphs, but crucially we still cannot talk about the collection of all classes! However, what this solution does is simply to push the Russel paradox one level up, and the next logical step is to repeat this. Unfortunately this cannot be done 'all the way up', and the problem never goes away completely.

  3. We use Venn diagrams and usually do not care about fixing a superset that contains all the sets in question so that we can take relative complements. For specific sets, this can be dealt with in ZFC by using the union as the superset. But this is not intuitively satisfying because we easily conceive of the absolute complement (the collection of everything that is not a member of a collection), and not unreasonably. After all, a set is essentially an indicator function on the set-theoretic universe; at least that is the way we always wanted it, but of course this indicator function is not a set... The point though is that it is unsatisfying to allow an indicator function to correspond to a set but disallow its negation.

Now some people might say that our intuition is problematic, and Russel's paradox shows that it is inconsistent to have the collection of everything. The first part may be so, but the second part is nonsense, since an alternative set theory called NFU not only is a boolean lattice with a universal set but is also consistent as long as PA is consistent! Since almost every logician believes that PA (which is extremely weak compared to ZFC) is consistent, they would have no choice but to believe that NFU is consistent too.

What then is the problem? If you see how NFU avoids the paradoxes, it is via the stratification in the comprehension axiom. In ZFC and many type theories, there is also stratification, this time in the sorts (sets and proper classes for ZFC, and type universe hierarchies for type theories). I am personally not convinced that even stratification is necessary for a consistent foundational system over classical logic, but that's totally off-tangent.

$\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.