The Rise of Anti-Set Theory

This report details the discovery and proliferation of a radical new form of set-theory that has come to be known across math departments across the world as Anti-Set Theory. The earliest appearance of Anti-Set Theory is shrouded in mystery, but my best efforts have traced it to the work of two little-known logicians named Narl Cowman and Bishi Ranger. The germinal notion that would eventually grow into Anti-Set Theory was the idea of a theory of sets obtained by taking all of our familiar intuitions about sets, and require their exact opposites to hold. Any property that would hold of all sets, would of necessity not hold of any the objects in this theory. An attractive idea by any standard, and one self-evidently worthy of pursuit. And thus Anti-Set Theory was born.

The development of Anti-Set Theory progressed in three phases: the Era of Simple Negation (which was plagued with unattractively permissive axioms and a proliferation of models), the Age of Negation after the Universal Quantifier (where the previous problems were resolved, but new problems of consistency and paradox arose), and finally the Modern Age of Axiomatic Anti-Set Theory (where there arose the split between “revolutionary” and “traditionalist” Anti-Settists, as they came to be known). Each of these phases will be explained in more depth in what follows.

The Era of Simple Negation

The first formulations of Anti-Set Theory suffered for practical reasons that were obvious in retrospect, but took embarrassingly long to remedy. The early anti-settists naively took their project to be to simply take the axioms of existing set theories and negate each of them, then to collect them into a new axiomatic theory and explore the consequences. While the idea to build off of existing set theories was a worthy one, there was a serious problem with this approach. Namely, the axioms of existing set theories were designed to be quite strong and restrictive, which made their negations overly weak and permissive. Many axioms had the form “All sets have this property”, the negation of which becomes “At least one set doesn’t have this property”, not “NO sets have this property.” The latter was the ambition of the original anti-settists, but it would take them until the Age of Negation After the Universal Quantifier about a half hour later to realize the crucial error they were making.

For instance, in the axioms of ZF (the orthodox axiomatization of set theory until Anti-Set Theory took the world by storm), there is an axiom known as “the Axiom of Pairing.” This axiom says, in plain English, that for any two sets x and y, there exists a set containing just x and y and nothing else (which we typically write as {x, y}). In the language of first-order logic, it said “∀x∀y∃z∀w (w∈z ↔ (w=x ∨ w=y))” (or in a more readable short-hand, “∀x∀y∃z (z = {x, y})”). Anti-Settists saw clearly the obvious benefit of having a set theory with the opposite property, namely that for any two sets x and y, the pair set {x, y} must NOT exist. But their original formulation of the Axiom of Anti-Pairing used simple negation: “¬∀x∀y∃z (z = {x, y})”, which is equivalent to “∃x∃y∀z (z ≠ {x, y})”, or “there are two sets x and y such that no set contains just x and y.” This was obviously too weak for what was desired.

The same problem cropped up for anti-union, anti-comprehension, anti-foundation, and virtually every other axiom of ZF. A new idea was needed. And soon enough, it came: we should place our negations AFTER the initial block of universal quantifiers, not before. The brilliance of this breakthrough is hard to overestimate. Fields Medals were awarded and backs were patted. This brings us to the second phase of the history of Anti-Set Theory.

The Age of Negation After the Universal Quantifier

Now that the Anti-Settists knew how they were going to proceed, they got busy axiomatizing their new theory. Every set has a power set? No more, now no set has a power set. The union of each set exists? Nope! Unions are banned. Infinite sets? Absolutely not.

The first few axioms to be proposed were anti-pairing, anti-union, anti-powerset, and anti-foundation and they took the following form:

Anti-Pairing: ∀x∀y¬∃z∀w (w ∈ z ↔ (w = x ∨ w = y))
Anti-Union: ∀x¬∃y∀z (z ∈ y ↔ ∃w (w ∈ x ∧ z ∈ w))
Anti-Powerset: ∀x∀y∃z (z ⊆ y ∧ z ∉ x)
Anti-Foundation: ∀x∀y (y ∈ x → ∃z (z ∈ x ∧ z ∈ y))
Anti-Infinity: ∀x¬∃y∀z (z ∈ x → ∀w (w = z⋃{z} → w ∈ y))

But soon they began running into trouble. The first hint that something was amiss appeared with the Axiom of Anti-Comprehension. The Axiom of Comprehension says that for any property Φ definable as a sentence of first-order ZF, and for any set X, there exists the subset of X consisting of those elements that satisfy Φ. Anti-Comprehension could thus be written:

Anti-Comprehension: ∀x∀y (y ≠ {z∈x | φ(z)})

Perhaps you can see the problem. What if φ is a tautology? Or in other words, what if φ(z) is a property satisfied by ANY and EVERY set, like, say, z=z? Then our axiom tells us that for any set x, the subset consisting of those elements that are equal to themselves cannot exist. But that’s just x itself! In other words, for any set x, x does not exist. The first Anti-Settists had unwittingly destroyed the entire universe of sets!

Another problem arose with Anti-Replacement. Recall that Replacement says that for any function F(x) definable in a sentence of first-order ZF, and for any set X, the image of X under F exists. So Anti-Replacement states that this image does not exist. But what if F is the identity function? Then Anti-Replacement tells us that the image of X under the identity map (namely, X itself) does not exist. And again, we’ve proved that no sets exist.

Quite simply, the problem the Anti-Settists were running into was that while their original axioms were too weak, their new axioms were too strong! So strong that they DESTROYED THE UNIVERSE. That’s strong.

The solution? Anti-Comprehension and Anti-Replacement were discarded. But there was another problem in the Axiom of Anti-Extensionality. Extensionality says that any two sets are the same if they share all the same elements. So Anti-Extensionality says that if two sets share all the same elements, then they are not the same. But if we compare any set X with itself using this standard, we find that X cannot equal X! This was even worse than before, because it violates the first-order tautology ∀x (x = x). Not only did this second wave of Anti-Settists destroy the universe, they also broke the rules of logic!

So Anti-Extensionality had to go. That much everybody agreed on. And the removal of this axiom settled the last of the paradoxes of Anti-Set Theory. But no sooner had the dust settled than a new controversy arose as to the nature of Extensionality…

The Great Schism: The Modern Age of Anti-Set Theory

So far, the Anti-Settists had compiled the following list of axioms:

Anti-Pairing: ∀x∀y¬∃z∀w (w ∈ z ↔ (w=x ∨ w=y))
Anti-Union: ∀x¬∃y∀z (z∈y ↔ ∃w (w∈x ∧ z∈w))
Anti-Powerset: ∀x∀y∃z (z⊆y ∧ z∉x)
Anti-Foundation: ∀x∀y (y∈x → ∃z (z∈x ∧ z∈y))
Anti-Infinity: ¬∃x∀y (y ∈ x → ∀z (z = y⋃{y} → z ∈ x))

You might have noticed that the Axiom of Anti-Infinity looks a little strange. The Axiom of Infinity tells us that there’s a set X that contains all empty sets, and such that for any set Y contained in X, if Y has a successor then that successor is also in X. So the Axiom of Anti-Infinity will say that there is no such set. We’ll prove shortly that in fact, the other axioms entail that there are no empty sets, so it’s vacuously true of every set that it “contains all empty sets.” Thus the only restriction placed on our universe by the Axiom of Anti-Infinity is that there’s no set that contains the successors of all its members with successors.

For a while, everybody agreed on this list of axioms and all was well. But after a couple of hours, new rumbles arose about Extensionality. A new contingent of Anti-Settists began arguing in favor of including the Axiom of Extensionality. It’s hard to describe exactly what was going in the minds of these individuals, who appeared to be turning their backs on everything that Anti-Set Theory was all about by accepting an ORDINARY axiom alongside all of their beautiful Anti-Axioms. Some of them expressed a concern that they had gone too far by turning their back on extensionality, and worried that Anti-Set Theory was so far removed from our intuitions that it no longer deserved to be called a theory of sets. Others pointed out that Anti-Set Theory as it was currently formulated ruled out certain models that they felt deserved to belong to the pantheon of Anti-Set Universes. The rest of the Anti-Settists called them crazy, but they persisted. The fighting reached fever pitch one afternoon in a meeting of the leading Anti-Settists, where one individual who shan’t be named accused another of “selling out” to Traditional Set Theory, and a fist-fight nearly broke out. This led to the Great Schism.

Anti-Settists fractured into two contingents that became known as the traditionalists, who advocated an extensional Anti-Set Theory, and the revolutionaries, who wanted an intensional Anti-Set Theory where two sets could share all the same elements but still be different. In recent history the fighting has cooled off, probably because both sides noticed that there actually didn’t seem to be all that huge of a difference between extensional and intensional anti-set theory. The primary realization was that the other axioms banned any objects based off of the elements they contained (so that anti-pairing, for instance, really says that there can be no set with the same elements as the pair of x and y, not just that the pair of x and y doesn’t exist).

Extensional Anti-Set Theory
Extensionality: ∀x∀y (∀z (z ∈ x ↔ z ∈ y) → x = y)
Anti-Pairing: ∀x∀y¬∃z∀w (w ∈ z ↔ (w = x ∨ w = y))
Anti-Union: ∀x¬∃y∀z (z ∈ y ↔ ∃w (w ∈ x ∧ z ∈ w))
Anti-Powerset: ∀x∀y∃z (z⊆y ∧ z∉x)
Anti-Foundation: ∀x∀y (y ∈ x → ∃z (z ∈ x ∧ z ∈ y))

Intensional Anti-Set Theory
Anti-Pairing: ∀x∀y¬∃z∀w (w ∈ z ↔ (w = x ∨ w = y))
Anti-Union: ∀x¬∃y∀z (z ∈ y ↔ ∃w (w ∈ x ∧ z ∈ w))
Anti-Powerset: ∀x∀y∃z (z⊆y ∧ z∉x)
Anti-Foundation: ∀x∀y (y ∈ x → ∃z (z ∈ x ∧ z ∈ y))

That covers the history of Anti-Set Theory up to modern times. Let’s now take a look at some of the peculiar details of the theory.

Theorem 1: No anti-sets contain exactly one element.

Proof: Suppose that there was an anti-set X such that X contained Y and nothing else. Then the sentence “Aw (w ∈ X ↔ (w = Y ∨ w = Y))” would be true. But this would be a violation of anti-pairing, as there can be no set whose elements are the same as the pair {Y, Y}. So no such anti-set can exist.

Theorem 2: No anti-sets contain exactly two elements.

Proof: Suppose there was an anti-set X such that X contained Y, Z, and nothing else. Then the sentence “Aw (w ∈ X ↔ (w = Y ∨ w = Z))” would be true. But this would be a violation of anti-pairing. So no such anti-set can exist.

Theorem 3: No anti-sets contain an empty anti-set.

Proof: Suppose that some set X contained a set Y, where Y is empty. By Anti-Foundation, every element of X must share an element with X. So Y must share some element with X. But Y contains nothing, so it can’t share any element with X. Contradiction. So no such anti-set exists.

Theorem 4: No anti-set can be its own union.

Proof: Follows trivially from the axiom of Anti-Union: UX doesn’t exist for any x, so if X = UX, then X doesn’t exist. (This rules out anti-sets with the same structure as limit ordinals.)

Theorem 5: No empty anti-sets exist.

Proof: Suppose there exists an empty anti-set X. Then the union of X is also an empty anti-set. The Axiom of Anti-Union says that there can be no anti-set with the same elements as the union of any anti-set. So there can be no empty anti-set. Contradiction, so no empty anti-set exists.

These theorems tell us a lot about the structure of anti-sets. In particular, every anti-set contains at least three elements, and each of those elements in turn contains at least three elements, and so on forever. So we only have infinite descending membership-chains of anti-sets.

Also, we’ve ruled out anti-sets with zero, one, and two elements, so you might think that no three-element anti-sets can exist either. But the same argument we used for one- and two-element anti-sets doesn’t work any longer, since pairing never produces three-element sets. In fact, the first model of Anti-Set Theory discovered contained exactly five anti-sets, each of which had three elements. This model is an intensional model, as it’s crucial that two of the sets (C and X) contain the same elements. We’ll call this the Primordial Anti-Set Model.

Universe: P, A, B, C, X
P = {A, B, C}
A = {B, C, X}
B = {A, C, X}
C = {A, B, X}
X = {A, B, X}

Here’s two attempts to visualize this model:

Beautiful! Let’s check each of the axioms to convince ourselves that it really is a valid model.

Anti-Union: U(P) = A ⋃ B ⋃ C = {A, B, C, X}. Similarly, you can show that U(A), U(B), U(C), and U(X) all contain A, B, C, and X. And {A, B, C, X} is not an anti-set in the universe, so no violations of Anti-Union occur.

Anti-Pairing: This one’s easy, since each of our sets contains three elements, and no three-element set can be formed by pairing.

Anti-Powerset: Note that the axiom of power set only says “there’s a set containing all the existing sets that are subsets of X, for each X”, but it doesn’t bring into existence any new subsets. So for instance, in this model, the power set of P is just {P}, as P is the only subset of P that exists. But {P} doesn’t exist! Similarly, for each element, its power set is just the set of itself, which doesn’t exist by anti-pairing.

Anti-Foundation: Does any set contain an element that it doesn’t have anything in common with? You can just verify this by inspection.

Anti-Infinity: (EDIT: this model and the following one actually violate Anti-Infinity! Realized this after originally posting. A future post will provide more details.)

Now, this was a model only of Intensional Anti-Set Theory, not Extensional Anti-Set Theory. Here’s a way to modify it to get a model that works in both theories:

Universe: T, A, B, C
T = {A, B, C}
A = {T, B, C}
B = {A, T, C}
C = {A, B, T}

Again, convince yourself that this universe satisfies the axioms.

Using a similar construction, we can show that there are models of anti-set theory with exactly N sets, for every N ≥ 4. Our universe: T, A1, A2, …, AN-1. T = {An | n ∈ {1,2,…,N-1}, Ak = {T} ⋃ {Aj | j ∈ {1,2,…,N-1} \ {k}}.

Many lines of research remain open in the field of Anti-Set Theory. Can Anti-Sets serve as a new foundation for mathematics? Are there models of Anti-Set Theory that contain structures isomorphic to the natural numbers? Is the theory still consistent if we include an Axiom of Anti-Choice? (Adding Anti-Choice rules out the models we’ve discussed so far. Perhaps only infinite universes are allowed with Anti-Choice.) Other proposed additions to the axioms include the simple negation of extensionality, and an “Axiom of Undefinability”, which says that no set exists whose elements satisfy a definable property. How would these additions affect the universe of sets?

I want to close by noting that set theory sometimes gets a bad rap among mathematicians and the wider community for being too abstract or not “useful enough.” We hope that the advent of Anti-Set Theory will make it plain to the public that there is a future world in which set theory can be of GREAT practical use to everybody. The possible applications of Anti-Set Theory are too numerous to count, so numerous in fact that I regard as unnecessary naming any specific examples.