SET THEORY WITH COMPLEMENTS

MARTIN GOLDSTERN

Abstract. We show that the following theory ZFCK is consistent (assuming the consistency of ZFC)

ZFCK consists of the usual ZFC axioms with the following modifications:

• Foundation is not required. Call a set grounded if the ε-relation on its transitive closure is well-founded.

• Separation only postulates that subclasses of grounded sets exists,

• Replacement postulates that the images of grounded sets exist.

• Power set postulates that the power set of any grounded set exists.

• The infinity axiom postulates that there is a smallest inductive set (or: a smallest limit ordinal > 0).

• In addition, we require that every set has a complement, so in particular the universal set (=complement of ∅, the “set of all set”) exists.

This note deals with set theories that admit non-wellfounded sets. We will use the following definitions.

• A set x is called wf if the structure (x, ∈) is well-founded.

• A set x is called grounded if it is contained in a well-founded transitive set. If transitive closures exist, then x is grounded iff its transitive closure is well-founded. If ω exists and certain instances of replacement and AC hold, then a set x is grounded iff there is no ∈- decreasing ω-sequence starting with x.

In ZF minus Foundation, the statements “every set is well-founded” and “every set is grounded” are equivalent, and either of them can be called the “regularity axiom.”

T.E.Forster’s book “Set theory with a universal set”, discusses (among others) set theories of Church and Mitchell.

In both theories, foundation is not required, every set has a complement, and replacement and Aussonderung are only required for grounded sets.

In Church’s set theory (CUS), arbitrary unions and intersections exist, but the power set axiom is restricted to grounded sets.

In Mitchell’s set theory, all power set exist, but not all unions; not even all unions of two sets. Both theories are consistent. For the proof of the consistency of Church’s set theory, the

compactness theorem is invoked; this means that it is conceivable that there is no model whose ω is (externally) well-founded.

Schimanovich has asked if it is possible to have complements of all sets, replacement for grounded sets, and power sets of all sets. We give a partial answer to this question by sketching a model of the fragment of CUS described above, i.e., of the following axioms:

- Extensionality.

- There exists an empty set (it is unique; call it 0).

- small union: For all x, y: x ∪ y exists (this follows from pairing and big union)

- Pairing: For all x, y: {x, y} exists (this follows from replacement as soon as we have a set with two elements)

- Big union: For all x, ⋃ x exists.

- Infinity: There exists a smallest inductive set, call it ω. (w is inductive iff 0 ∈ w ∧ ∀y ∈ w : y ∪ {y} ∈ w)

Date: 2000-03-27.

1991 Mathematics Subject Classification. Primary 03E70; secondary 03E30.

- Complements: The complement of every set exists.

(I.e., ∀x ∃y : ∀z(z ∈ y ⇔ z ∉ x))

- Replacement: For any definable function class F and any grounded set x, F [x] exists.

- Aussonderung: For every definable class C and every set x, x ∩ C exists. (This follows from

replacement and the empty set axiom.) We will write ZFPK for this axiom system.

The natural numbers of the model M we construct will be naturally isomorphic to the true natural numbers; moreover, the classes ORD^{M} of all ordinals of M and even the class W F^{M} of all grounded sets of our model will be naturally isomorphic to the true ordinals, and the all sets, respectively.

Notation 1. Let (V, ∈) be a model of ZFC. Everything we do from now on will take place in V, so we may as well assume that V is the whole universe (a class).

We will use boldface letters to denote (definable) classes of V.

Assumption 2. We will assume that there is a class F which is a bijection between V and Ord^{V}, so V = HOD^{V}, e.g., V = L.

(This assumption is harmless since we are interested in a consistency result only.)

This implies that every proper class of V can be mapped bijectively to the ordinals of V (using a class function).

Notation 3. Let ϵ and M be classes, ϵ ⊆ M × M.

1. For m ∈ M we let m_{ϵ} := {x ∈ M : xϵm} be the “extension” of m.

2. For clarity we may write Ext_{M}(m) or Ext_{M}(m) for m_{ϵ}, depending on whether m_{ϵ} ⊆ M is a set or possibly a proper class.

3. Let A ⊆ M. If there is a unique m ∈ M with m_{ϵ} = A, then we write A^{ϵ} for this m, and we

say “m realizes A”. Otherwise, we say “A^{ϵ} does not exist” or “A is not realized.” Hence, (A^{ϵ})_{ϵ} = ϵ if A^{ϵ} exists, and (m_{ϵ})^{ϵ} = m if (M, ϵ) satisfies (the relevant instance of) the axiom of extensionality.

The extensionality axiom says: For all m ≠ m′: m_{ϵ} ≠ m′_{ϵ}.

The pairing axiom, union axiom, empty set axiom, infinity axiom, replacement axiom and separation axiom are all instances of the same scheme, namely the comprehension axiom. The validity of each of these axioms in a structure (M, ϵ) can be phrased as the existence of X^{ϵ} for certain sets X ⊆ M. For example, (M, ϵ) satisfies the power set axiom iff:

For all m ∈ M, {x ∈ M : (M, ϵ) ⊧ x ⊆ m}^{ϵ} exists. We will define two subclasses M ⊆ V, ϵ ⊆ M × M, such that (M, ϵ) satisfies ZFPK where

power set is restricted to grounded sets.

We will work inside V. Fix two distinct sets (e.g., 0 and 1), and call them “s”, “b” (small , big).

Definition 4. Our model M will be a subclass of {s, b} × V. Elements of the form (s, x) will have “small” extensions (but not necessarily hereditarily small), elements of the form (b, x) will be complements of small objects.

1. M′_{0} := Ord^{V}, M_{0} := {b} × M′_{0}.

2. For α > 0, M_{α} and M′_{α} will be defined by transfinite induction:

\begin{aligned}M′_{α} & := \{x ∈ V : x ⊆ ⋃_{β<α} M_{α}\} \\ M_{α} & := \{s\} × M′_{α} \end{aligned}

3. M := ⋃_{α∈Ord} M_{α}.

Definition and Fact 5. We call an element (s, x) “pure” iff x ∩ M_{0} = ∅. Elements (b, α) are never pure. (s, x) is “hereditarily pure” if (s, x) is pure and all elements of x are hereditarily pure.

Clearly the class of hereditarily pure elements of M is canonically isomorphic to V. There is a class F ⊆ V which is a bijection between Ord and ⋃_{α∈Ord\{0}} M_{α}.

Definition 6. We define a relation ϵ ⊆ M × M by defining extensions m_{ϵ} for all m ∈ M:

(s, x)_{ϵ} := x (b, α)_{ϵ} := M \ (s, F(α))_{ϵ}

That is, the element (b, α) represents the complement of (s, F(α)).

While the (s, x)_{ϵ} is always a set, (b, α)_{ϵ} is always a proper class.

Fact 7. 1. Whenever x ⊆ M is a set in V, then x^{ϵ} is well-defined.

2. Every (b, α) is not grounded.

Proof.

Part 1. Find α such that x ⊆ M_{α}, then x^{ϵ} := (s, x) ∈ M_{α+1}.]

Part 2. Let F(α) = x.

Pick a large enough β (larger than the rank of x), then (b, β)ϵ̸x, so (b, β) ∈ (b, α). So we can find (in V) an ϵ-descending sequence ((b, α_{n}) : n ∈ ω), and this sequence is clearly

realized in (M, ϵ).

Fact 8. For all x ⊆ M, ⋃_{yϵ̸x} y_{ϵ} = M.

Proof. check...

Now check that (M, E) satisfies ZFK with a restricted power set axiom.

- Extensionality: clear.

- Empty set axiom: (s, ∅)_{ϵ} = ∅.

- Complements: (b, α)_{ϵ} is the complement (in M) of (s, F(α)_{ϵ}).

- Pairing: For any m_{1}, m_{2} ∈ M, (s, {m_{1}, m_{2}})_{ϵ} = {m_{1}, m_{2}}.

- Power set: Every grounded set is of the form (s, x).

Let P := {y : (M, ϵ) ⊧ y ⊆ (s, x)}. Then P is a set, so P^{ϵ} = (s, P).

- Replacement: Let F ⊆ M × M be a class function, whose domain is a grounded set, say dom(F) = (s, x)_{ϵ}. Then the range of F is some set y, and y^{ϵ} = (s, y).

- Infinity: Let x := {0^{M}, 1^{M}, … }. Clearly x^{ϵ} = (s, x) witnesses the infinity axiom. It remains to show the union axiom. We first check the “small union” axiom, i.e., ∀a ∈ M ∀b ∈ M : (a_{ϵ} ∪ b_{ϵ})^{ϵ} exists. Let u := a_{ϵ} ∪ b_{ϵ}. There are three cases to consider:

1. a, b ∈ M_{0}

2. a, b ∉ M_{0}

3. a ∈ M_{0}, b ∉ M_{0} (or conversely). Case 1: u = (b, x)_{ϵ} ∪ (b, y)_{ϵ} = −(F(x)_{ϵ} ∩ F(y)_{ϵ}). Let z := F(x)_{ϵ} ∩ F(y)_{ϵ}), then z ∈ V, z ⊆ M,

so ∃γ F(γ) = z. Clearly (b, γ)_{ϵ} = −F(γ) = −z, so u^{ϵ} = (b, γ).

Case 2: trivial. Case 3: u = (b, x)_{ϵ} ∪ (s, y)_{ϵ} = −(F(x)_{ϵ} ∩ (−y_{ϵ})). Let z := F(x)_{ϵ} ∩ (−y_{ϵ}), then again z ∈ V,

z ⊆ M, so ∃γ F(γ) = z. Clearly (b, γ)_{ϵ} = −F(γ) = −z, so u^{ϵ} = (b, γ).

Union axiom: We have to check that for all m ∈ M, the set U(m) := {x ∈ M : ∃y ∈ M xϵy, yϵm} is of the form y_{ϵ} for some y ∈ M.

If m ∈ M_{0}, then it is easy to see that U(m) = M, so assume m ∉ M_{0}. Note that U(m) = ⋃_{yEm} y_{ϵ} = ⋃_{(s,y)ϵm}(s, y)_{ϵ} ∪ ⋃_{(b,y)ϵm}(b, y)_{ϵ}. By the previous discussion, it is enough to show that both (⋃_{(s,y)ϵm}(s, y)_{ϵ})^{ϵ} and (⋃_{(b,y)ϵm}(b, y)_{ϵ})^{ϵ}

exist.

Note that u_{1} := ⋃_{(s,y)ϵm}(s, y)_{ϵ} is an element of V and a subset of M, so u_{1}^{ϵ} = (s, u_{1}).

Let and u_{2} := ⋃_{(b,y)ϵm}(b, y)_{ϵ}. If the index set of this union is not empty, then −u_{2} = ⋂_{(b,y)ϵm} −(b, y)_{ϵ} = ⋂_{(b,y)ϵm} y_{ϵ}, ...

This concludes the proof that the model (M, ϵ) satisfies ZFPK. The usual methods then give a finitary proof of that Con(ZF) implies Con(ZFPK): Assume that φ_{1}, …, φ_{n} is the proof of a contradiction from ZFPK, then the relativized formulas φ_{1}^{M}, …, φ_{n}^{M} can be used to get a proof of a contradiction from ZF.

A drawback of our model is that most set-theoretical constructions will fail for non-grounded sets. For example, a non-grounded in our model set can never be the domain of a function.

A note on non-hereditarily well-founded sets

We show here the inconsistency of a set theory in which complement and power set exists, and where replacement and/or separation are required for all sets on which the ∈-relation is well-founded.

Call a set x “good” if ∀y ∈ x : 0 ∈ y. Let M := P (−P (−{0})). It is easy to check that x ∈ M iff x is good. Note that y ∈ x, x ∈ M implies 0 ∈ y, whereas y ∈ M implies 0 ∉ y. Hence x, y ∈ M ⇒ x ∉ y. So the ∈-relation is well-founded on M. However, M is quite big, so

the usual proofs will show that neither replacement nor separation can be applied to M, given a modest amount of other ZF axioms.

For example, replacement immediately yields the set WF of well-founded sets, which leads to a contradiction.

Similarly, WF can be obtained by separation plus two applications of the union axiom.

Algebra, Technische Universität, Wiedner Hauptstr 8-10, A-1040 Wien, Austria

E-mail address: Martin.Goldstern@tuwien.ac.at