Let F(x) be a formula belonging to the language of first order ZF in which x is the one and only variable that occurs free and let N(x) be the negation of F(x). Are any examples known of an F(x) and an N(x) such that not just one but each one of the two sentences "The set (x:F(X)) exists" and "The set (x:N(x)) exists"-which can be expressed in the language of first order ZF-are inconsistent with ZF? An obvious candidate for F(x) is the formula which defines the Russell set but in that case N(x) defines the null set (because of the Axiom of Foundation in ZF) and there is no inconsistency.
$\begingroup$
$\endgroup$
2
asked May 5, 2013 at 17:55
-
3$\begingroup$ "$x$ has size $3$". "$x$ belongs to an even level of the cumulative hierarchy." $\endgroup$– Andrés E. CaicedoCommented May 5, 2013 at 18:29
-
1$\begingroup$ I agree with your comment to Asaf's answer that you did not formulate your question clearly enough. Or, better: the question you have in mind is not the one that you wrote. In my opinion, your question does not fit the title, because there is nothing "paradoxical" about having a proper class whose complement is also a proper class; compare this with the existence of an infinite set of natural numbers whose complement is also infinite. $\endgroup$– GoldsternCommented May 7, 2013 at 8:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Here are two examples:
Let $F(x)$ be the statement "There exists $y$ such that $x$ is the power set of $y$", or formally, $$F(x)=\exists y\forall u(u\subseteq y\leftrightarrow u\in x).$$
Since every set has a (unique) power set, we have that the class of power sets is not a set; but also the class of those which are not power sets is not a set either, because if $x=\mathcal P(y)$ then $x\setminus\lbrace\varnothing\rbrace$ is not a power set.
Let $F(x)$ be the statement "$x$ is an ordinal". It is known that the class of ordinals is not a set, but the class of those which are not ordinals is not a set either, e.g. $\mathcal P(\alpha)$ for every ordinal $\alpha$, is not an ordinal (with the exceptions of $0$ and $1$ of course).
answered May 5, 2013 at 18:18
-
$\begingroup$ Perhaps I did not formulate my question clearly enough. I am working within ZF in which there is no distinction between sets and classes-all sets are classes and all classes are sets. And, I am not looking for a pair of sentences which contradict each other. I am looking for a pair, such that each sentence-by itself- is inconsistent with ZF. The sentences I have in mind are the sort that lead to well known paradoxes such as Curry's or "the paradox of the set of all grounded sets". Such sentences are usually called Axioms of Comprehension. $\endgroup$ Commented May 6, 2013 at 18:46
-
$\begingroup$ Garabed Gulbenkian, and in both cases you have sentences that saying "There exists $x$ such that $x=\lbrace y\mid F(y)\rbrace$" and similarly for $N(y)$, is a contradiction. There is no "set of all ordinals" and there is no set of "all which are not ordinals"; and there is no set of "power sets" and there is no set of "not power sets". Both these sentences have the property that each defines a class which is provably not a set (in ZF). Do note that in ZF sets exists and classes can be defined (from parameters perhaps), which is quite a distinction (in the metatheory). $\endgroup$– Asaf Karagila ♦Commented May 6, 2013 at 19:29
$\begingroup$
$\endgroup$
5
You are looking for a definable class $C$ such that (ZFC-provably) neither $C$ nor its complement can be a set. There are lots of those. Note that a class is not a set iff it contains elements of arbitrarily high rank. If you define a class at random, I would think the chances are at least 99% that it has this property.
Some examples.
- The class of all sets containing your favorite set $s_0$. (As an element. Or, as a subset - unless $s_0=\emptyset$.)
- The class of all groups. (Or, your favorite class of structures, unless it happens to be the class of all sets.)
- The class of all finite sets. The class of all sets of size $\kappa$.
- The class of all sets of even rank.
No, this is too easy, I must have misunderstood the question...
-
$\begingroup$ @ Asaf and Goldstern: I see now what is wrong with my question. I failed to realize that the Foundation axiom of ZF already prohibits -as you point out-the existence of sets containing elements whose rank is arbitrarily high. This makes my question (in its present form) absurdly easy to answer. I must modify it by stipulating that the axioms of my set theory are just those of ZF other than Foundation. Sorry about that. $\endgroup$ Commented May 8, 2013 at 14:25
-
$\begingroup$ No, I think your problem is with replacement. Already ZF minus replacement shows that the complements of most proper classes are themselves proper classes. ("most" in a non-technical sense) $\endgroup$ Commented May 8, 2013 at 22:05
-
$\begingroup$ Are you saying that if I delete Replacement as well from the list of axioms of my set theory, I will still have the same trouble with my question? Maybe I need a much weaker set theory. $\endgroup$ Commented May 9, 2013 at 18:38
-
$\begingroup$ I am sorry, my fingers must have slipped. What I want was: already ZF minus FOUNDATION shows that the complements of most proper classes are again proper classes. (And replacement is important in those proofs. For example, the class of even ordinals is a proper class, because using replacement you can get from it the class of all ordinals, which is not a set, by Burali-Forti. Or: the class of all singletons is a proper class, because by replacement you can get from it the class of all sets, which not a set, by Russell.) $\endgroup$ Commented May 9, 2013 at 21:47
-
$\begingroup$ Your arguments and examples convince me that if my set theory T is to be a sub-theory of ZF, neither Foundation nor Replacement can be an axiom of T. Otherwise there will be too many sets X such that the statement "X does not exist" will already be a theorem of T-and my question will be too easy to answer. In any case no pair of sets that are complements of one another can ever both exist or else the axiom of Union will allow the Universal set to exist and Russell's paradox to be derived (from the axiom of Separation). $\endgroup$ Commented May 11, 2013 at 15:06