Can we introduce complements on top of the standard set theory $\text{ZF}$ and have some comprehension axioms about them, like in defining a "small set" as an element of a stage of the Cumulative Hierarchy as:

$\text {Define:} \ \ small (s) \longleftrightarrow \exists f \ \exists d \ (Ord(d) \wedge dom(f)=d \\ \wedge \forall i,a,j,b \ (\langle i,a \rangle \in f \wedge \langle j,b \rangle \in f \to [i=j \leftrightarrow a=b] \wedge [j=i+1 \to b=P(a)]) \ \wedge \forall l (l \in d \wedge \neg \exists k \in d (l=k+1) \to \forall c (\langle l,c \rangle \in f \rightarrow c=\bigcup (\{y| \exists i \in d (i < l \wedge \langle i,y \rangle \in f)\}))) \\ \wedge \exists i,v \ (\langle i,v \rangle \in f \wedge s \in v))$

where $``Ord(d)"$ means $d$ is a Von Neumann ordinal, and $``dom(f)"$ means the domain of $f$.

Now we hold Extensionality over the whole domain of discourse, also we stipulate axioms of Pairing, Union, and Power over the whole domain of discourse. Now the only axioms that needs to be restricted are empty and Infinity to be small sets, and instances of the axiom schema of Replacement, which needs to be applied only to collections having 1-1 correspondence with a small set, i.e. the formula of the replacement would be:

$$[\forall x \ \exists z \ \forall y \ (\phi(x,y) \to y=z)] \to \forall A \ (small (A) \to \exists B \ \forall y \ (y \in x \leftrightarrow \exists x \in A \phi(x,y)))$$

Then we add complements over the whole domain of discourse, i.e.

$$\forall A \exists A' \forall y (y \in A' \leftrightarrow y \not \in A)$$

That appears to be safe, and I think we can even add small set choice to it.

My questions are:

[1] Are there known attempts in that direction?

[2] Can the above approach be extended, provided that set Union be $$ \forall A \ \exists x \ \big{[}\forall small \ y \ \big{(}y \in x \leftrightarrow \exists z \in A \ (y \in z) \big{)} \wedge \big{(}small(A) \to small(x) \big{)} \big{]}$$ , as to involve not just axiomatizing 'complements', but also to axiomatize existence of any function that is a 1-1 correspondence relation? Formally this is:

If $\phi(r,s)$ is a formula in which only $``r",``s"$ appear free, then:

$$\forall x,y \ [\forall z \big{(}\phi(z,x) \leftrightarrow \phi(z,y) \big{)} \to x=y] \ \to \forall A \ \exists x \ \forall y \ \big{(}y \in x \leftrightarrow \phi(y,A) \big{)} $$

is an axiom.

[3] can the axiom schema in [2] be strengthened as to allow parameters?

  • 4
    A minor comment: The "standard set theory" (standard in the sense of "usual", not in the technical sense of standard vs nonstandard) is not ZF. It is ZFC. – Goldstern Feb 16 at 22:32
  • 4
    A major comment: ZF contains the axiom of foundation/regularity. You did not include this axiom for a good reason: If $V$ is the complement of the empty set, then you must have $V\in V$, which contradicts foundation. – Goldstern Feb 16 at 22:33
up vote 4 down vote accepted

Church’s “Set Theory with a Universal Set” and its variants have complements, with Replacement restricted to sets equinumerous to a well-founded set:

  • Alonzo Church 1974a. “Set Theory with a Universal Set,” Proceedings of the Tarski Symposium, Proceedings of Symposia in Pure Mathematics XXV, ed. Leon Henkin, American Mathematical Society, ISBN: 978-0821814253, pp. 297-308. (Delivered 24 June 1971.)
  • Alonzo Church 1974b. “Notes on a Relative Consistency Proof of Axioms A– K of Church’s Set Theory with a Universal Set,” unpublished lecture notes, Church Archives, box 47, Folder 5.
  • Emerson Mitchell 1976. A Model of Set Theory with a Universal Set, unpublished Ph.D. thesis, University of Wisconsin at Madison.
  • “A Variant of Church’s Set Theory with a Universal Set in which the Singleton Function is a Set” (abridged), in Logique et Analyse, Vol 59, No 233 (2016) pp. 81–131, doi:10.2143/LEA.233.0.3149532. The full version is available at the Centre National de Recherches de Logique: http://www.logic-center.be/Publications/Bibliotheque/SheridanVariantChurch.pdf.
  • “Fixing Frege’s Set Theory,” slides from a talk on Church’s and my set theories with a universal set, delivered remotely at the University of Oxford Mathematical Institute, October 2013, and at the Stanford Mathematics Department, April 2014: http://www-logic.stanford.edu/seminar/1314/Sheridan_Fixing_Freges_Set_Theory.pdf.

See also Arnold Oberschelp 1973. Set Theory over Classes, Dissertationes Mathematicæ (Rozprawy Mat.) 106. [Mathematical Reviews 42 #8300], but note that the crucial part of the consistency proof in both [Friedrichsdorf 1979] and [Oberschelp 1973] is merely a reference to [Oberschelp 1964a], which uses a significantly different formalism.

More generally (chiefly, but not exclusively, about Quine’s New Foundations), see http://math.boisestate.edu/~holmes/holmes/setbiblio.html, and also https://en.wikipedia.org/wiki/Universal_set#Restricted_comprehension.

  • Thanks a lot. From preliminary readings of some of your articles, it appears that this theory is different, since (unlike your variants) it doesn't allow an unrestricted "pairwise" union, nor it allows any form of unrestricted union (unlike Church's and Oberschelp variants). – Zuhair Al-Johar Feb 19 at 18:00
  • continuation: Another note: this theory can have a single comprehension axiom schema by adding an axiom of a full set union for sets having all their members being small sets or complements of small sets, by then there is no need for replacement, and this theory becomes a comprehension related theory (like NF), unlike the customary theories you've alluded to. – Zuhair Al-Johar Feb 19 at 18:00
  • Of course, generally speaking, these theories do share many aspects with this theory, that in some sense if this theory is not inconsistent, then it can be said to belong to the very same general line of thought of those theories. Thanks again. – Zuhair Al-Johar Feb 19 at 18:03

The following is actually an answer to whether the theory presented in this post can interpret $\text{NBG}$.

The answer is to the positive! Moreover, it can interpret Morse-Kelley class theory $\text{MK}$.

The axioms of the theory are all those present in this post with the only exception of "Set Union" which is modified as suggested in [2].

$\text{Poof}$

$\text{Definitions:}$

$x \ is \ Class^{MK} \iff small(x) \lor \forall y \subset x \big{(}small(y) \to \exists small \ k (k \in x \wedge k \not \in y) \big{)}$

$x \ is \ set^{MK} \iff small(x)$

$ x =^{MK} y \iff \forall small \ z \ (z \in x \leftrightarrow z \in y)$

$ y \in^{MK} x \iff y \in x \wedge small(y)$

The proof of extensionality is straightforward. Now $V$ would be any set that has all small sets among its elements, for instance, we'll take $V$ to be the set of all sets in this theory (i.e. the complementary set of $\emptyset$). That $V$ contains an infinite element and is closed under set union, pairing and power is obvious, so is $\in^{MK}\text{Regularity}.$

What remains is to prove the class comprehension schema of $\text{MK}$.

$\text{LEMMA}$: This theory prove the following Separation schema:

$\forall A \ \exists x \ \forall small \ y \ (y \in x \longleftrightarrow y \in A \wedge \phi(y))$

Proof: the relation $A_1=\{y|\exists z \in A \wedge y=\langle 0,z \rangle\}$ is 1-1, so is the relation

$A_2=\{y|[\exists z \in A (\phi(z) \wedge y=\langle 0,z \rangle)] \lor [\exists z \in A (\neg \phi(z) \wedge y=\langle 1,z \rangle)] \}$

We need also to prove this form of intersection:

$\forall A, B \ \exists X \ \forall small \ y \ (y \in X \longleftrightarrow y \in A \wedge y \in B)$

Proof: let us take $A \cap B$ to be $(A^c \cup B^c)^c$

Now our separation set is $(A_1 \cap A_2)^{-1}$.

where the $``^{-1}"$ operator uses the following consequence of the last axiom:

$\phi(z,x) \iff \\ (\forall m \in x [\exists small \ k \ (m=\langle 0, k \rangle) \lor \neg small (m)] \wedge \ \exists y \in x (\neg small(y)) \wedge [\exists m \in x (small(m) \wedge m=\langle 0,z \rangle) \lor \exists m \in x (\neg small(m) \wedge z= \langle 0,m \rangle) ] ) \lor (\neg \forall m \in x [\exists k (small(k) \wedge m=\langle 0, k \rangle) \lor \neg small (m)] \wedge \exists m \in x (z= \langle 1,m \rangle)) $

In reality, we don't need the full scheme in [2] for that development! What is needed is to only prove the existence of $A_2$ sets for every set $A$ and every formula $\phi$, and $X^{-1}$ for every set $X$, that's it.

I believe that an answer to your question [1] is the system that Dana Scott developed in his paper, "Axiomatizing Set Theory" found in Proceedings of Symposia in Pure Mathematics, Volume 13, Part II, 1974, pp. 207-14. This system is, in Scott's words, the formalization of the following intuition:

But note that our original intuition of set is based on the idea of having collections of already fixed objects. The suggestion of considering all-inclusive collections [such as the set of all sets not containing itself, the set of all ordinals, etc.--my comment] only came in later by way of formal simplification of language. The suggestion proved unfortunate, and so we must return to the primary intuitions. These intuitions can gain an initial precision through formulating the two basic axioms of extensionality and comprehension, which we now discuss in detail.

Scott first, however, develops the following, "nameless", axiom:

Let the variables $a$, $b$, $c$, $a^{'}$, $b^{'}$, $c^{'}$, $a^{''}$,... range over sets and the variables $x$, $y$, $z$, $x^{'}$, $y^{'}$, $z^{'}$, $x^{''}$... range over arbitrary objects. The symbol $=$ is used for identity and $\in$ for membership. Whether it is really interesting or profitable to allow for non-sets in the theory is debatable; but let us not exclude them yet. We agree that the condition $x$ $\in$ $y$ should imply that $y$ is a set, a principle that we can formulate in logical symbols thus:

$\forall$$x$,$y$[$x$ $\in$ $y$ $\rightarrow$ $\exists$$a$[$y$ = $a$]]

Of course this must be taken as a axiom; but it is so primitive, so much just a convention of grammar, that we will not even give it a name.

Scott then gives the axioms of extensionality and comprehension:

Extensionality. $\forall$$a$,$b$[$\forall$$x$[$x$ $\in$ $a$ $\leftrightarrow$ $x$ $\in$ $b$] $\rightarrow$ $a$ = $b$].

Comprehension. $\forall$$a$ $\exists$$b$$\forall$$x$[$x$ $\in$ $b$ $\leftrightarrow$ $x$ $\in$ $a$ $\land$ $\Phi$($x$)].

Regarding Extensionality, Scott writes:

The extensionality axiom formalizes our idea that a set is nothing more than a collection of objects: It is uniquely determined by its elements.

Regarding the Comprehension axiom, Scott has a bit more to say:

The comprehension axiom formalizes the idea that one a collection $a$ is fixed, we can then extract from $a$ any arbitrary subcollection $b$. The extraction process is effected by finding a property $\Phi$($x$) which distinguishes $b$ as the subset of $a$ comprehending all those elements having the property. There is no reason to place any restriction on how $\Phi$($x$) is formulated: We believe in the existence of arbitrary subsets. It is a great temptation to erase the condition $x$ $\in$ $a$, thus simplifying the axiom schema; but we all know what happens. It is much more profitable to ask: Where does the $a$ come from?

He then proceeds to discuss (from a historical perspective) the answer to the above question:

Zermelo answered the question by giving several construction principles for obtaining new $a$'s from old. Fraenkel and Skolem extended the method, and von Neumann, Bernays and Godel modified it somewhat. Actually this is a rather sad history--because set theory is made to seem so artificial and formalistic. The naive axioms are contradictory. We block the contradiction and thereby emasculate the theory. Therefore to get anywhere we reinstate a few of the principles we eliminated and hope for the best. Now it would be wrong to accuse any of the above men of holding such a simplistic view of the axiomatic process. Nevertheless it is a widely held view and one that is easy to fall into when considering the formal axioms. Let us try to see whether there is another path to the same theory more obviously based on the underlying intuition.

Scott the goes on to make the following claim:

The truth is that there is only one satisfactory way of avoiding the paradoxes: namely, the use of some form of the theory of types . That was the basis of of both Russell's and Zermelo's intuitions. Indeed the best way to regard Zermelo's theory is a simplification and extension of Russell's. (We mean Russell's simple theory of types, of course.) Thus mixing of types is easier and annoying repititions are avoided. Once the later types are allowed to accumulate the earlier ones, we can then easily imagine extending the types into the transfinite--just how far we want to go must necessarily be left open. Now Russell made his types explicit in his notation and Zermelo left them implicit. It is a mistake to leave something so important invisible, because so many people will misunderstand you. What we shall try to do here is to axiomatize the types in as simple a way as possible so that everyone can agree that the idea is natural.

He now provides the basic intuitions for his "cumulative types":

Let us proceed on a very primitive basis. In order to obtain the sets to which the comprehension axioms can be applied, we imaginesome way of dividing the sets into levels. There will be earlier levels and later levels. Let the sets up to a certain level be thought of as forming a partial universe $V$ which is regarded as a legitimate set [in Zuhair's terminology, a small set--my comment]. We can be generous and assume that all the nonsets, the set-theoretic atoms, belong to all the levels. In a later universe $V^{'}$ we have not only the elements of $V$, but also $V$ itself to be used to form subcollections of $V^{'}$; that is, $V$ $\in$ $V^{'}$ as well as $V$ $\subseteq$ $V^{'}$, where we define

$\forall$$x$,$y$[$x$ $\subseteq$ $y$ $\leftrightarrow$ $\forall$$z$[$z$ $\in$ $x$ $\rightarrow$ $z$ $\in$ $y$]].

Furthermore, not only $V$, but by the same token all the subcollections of $V$, should also be elements of $V^{'}$.

Scott continues defining the notion of type in his system:

Once a set is fixed at one level, all its subsets are fixed at a later level--that is certainly the basic idea of the theory of types. We formalize this idea not by introducing type indices, but more simply by identifying a level with the collection of all sets (and nonsets) up to that level. We let variables $V$, $V^{'}$, $V^{''}$,... range over these levels--that is, we take the idea of a type level (as identified with certain sets) as a primitive notion. The "later than" relation is transcribed simply as $V$ $\in$ $V^{'}$. It need hardly be mentioned that we assume that there is at least one level and that each level is a set--axioms that we do not stop to name. What is important is the idea that a given level is nothing more than the accumulation of all the members and subsets of all the earlier levels (and all the nonsets, if any there be). In formal terms we have this axiom:

Accumulation. $\forall$$V^{'}$$\forall$$x$[$x$ $\in$ $V^{'}$ $\leftrightarrow$ $\lnot$$\exists$$a$[$x$=$a$] $\lor$ $\exists$$V$ $\in$ $V^{'}$[$x$ $\in$ $V$ $\lor$ $x$ $\subseteq$ $V$]].

(By the way, just because we use the variables $V$, $V^{'}$, $V^{''}$,... we should not think of the levels as being arranged in a $\omega$-type sequence. In general we will want a transfinite sequence. Also note that $V$ $\in$ $V^{'}$ does not imply that $V^{'}$ is the next level; it may be a much later level.) The purpose of this axiom is to show how the levels fit together.

The next axiom captures the intuition that however far the levels go out, they eventually capture everything:

Restriction. $\forall$$x$$\exists$$V$[$x$ $\subseteq$ $V$]

In other words, the whole universe, if only it were a set, would behave as the ultimate level in the sense of the previous axiom. (Note that this axiom gives the existence of at east one level. It really should have been formulated with the clause [$x$ $\in$ $V$ $\lor$ $x$ $\subseteq$ $V$], but we shall show below that $x$ $\in$ $V$ $\rightarrow$ $x$ $\subseteq$ $V$].) This will turn out to be nothing more or less than the well-known axiom of foundation, which is generally poorly understood. We feel that in the present context, it appears as a quite natural expression of the fact that the sets are restricted to levels.

Finally, Scott includes the following reflection principle as the last axiom:

Reflection. $\exists$$V$$\forall$$x$$\in$$V$[$\Phi$($x$) $\rightarrow$ $\Phi^{(V)}$($x$)] [from which one can derive infinity and replacement--my comment. See pp.213-214].

It should be noted that Scott, from Extensionality, Comprehension, Accumulation, and Restriction, shows that

(union and power set) also drop out of these axioms [pp. 210-212--my comment]

and that by Restriction, one can add complements over the whole domain of discourse so the existence of Scott's system is a correct answer to question [1].

If you take your description and rename $\textrm{set} \mapsto \textrm{class}$ and $\textrm{small set} \mapsto \textrm{set}$, and add some further axioms beyond the ones you mention (such as global choice), then the resulting theory is von Neumann-Bernays-Goedel set theory (NBG).

NBG has some very elegant properties, including:

  • Finitely axiomatisable in exactly the same way that ZFC is not;
  • Conservative over ZFC, so NBG and ZFC prove exactly the same statements about sets;
  • All proper classes (i.e. classes which are not sets) are equally-sized in the sense that their elements are in bijective correspondence;
  • Allows one to talk about classes such as $V$ and $\mathbf{On}$ as first-class objects in the theory, instead of defining them meta-mathematically as predicates over sets.
  • 4
    But this theory has a universal set $V=\{x|x=x\}$, (the complementary set of $\emptyset$), NBG doesn't have such a set. I mean in NBG the class $V$ doesn't have itself as an element, while here it does. I'm not sure what axioms are needed to be added to this theory to get to the strength of NBG. It would be nice to know of that – Zuhair Al-Johar Feb 16 at 12:55
  • 1
    I also don't think that this theory can interpret NBG, because even if we take membership $\in^*$ to be defined as: $(y \in^* x \iff y \in x \wedge small(y))$ and re-define equality as: $x=^* y \iff \forall \ small \ z \ (z \in y \iff z \in x)$, still I don't see how to interpret the class comprehension axiom scheme of NBG? – Zuhair Al-Johar Feb 16 at 13:32
  • A universal self-containing set is asking for trouble, since you can then use subset selection to produce Russell's paradoxical set. – Adam P. Goucher Feb 16 at 13:42
  • 4
    the axiom of replacement here is restricted to prevent that, the class $V$ is a large set, so you cannot apply replacement (nor separation) on it. – Zuhair Al-Johar Feb 16 at 13:49
  • 1
    Pairing implies that every (Zuhair) set is an element of some set. Applying your translation, this becomes "every class is an element of some class", which false in NBG. – Goldstern Feb 16 at 22:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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