Null set uniqueness theorem

John Allen Paulos. Probability and politics
D.J. Velleman. Set theory and logic
Herbert B. Enderton. Set theory and logic
Axioms of Zermelo-Fraenkel set theory

Note: This page was corrected in August 2006 to include a missing
not-symbol and a missing parenthesis. Also, a redundant statement was
deleted and some other minor changes were made.
   

Comment: Some are puzzled by the standard set theoretic fact that even when set A does not equal set B, A - A equals B - B (also written A\A and B\B). To beginners, it is sometimes counterintuitive that the empty subset of A is indistinct from the empty subset of B.

In the Zermelo-Fraenkel version of set theory, the unique empty set is given as an axiom. However, using the rules of logic, it is possible to derive the empty set from other axioms of ZF. See the link above for all the ZF axioms.

The theorem below is not strictly necessary, but hopefully may still prove of use.

---

We accept these rules of inference, letting "~" stand for "not":

   The expression i)    x ® y       means "x implies y", which is equivalent to  ii)   if x is true, then y is true        which is equivalent to  iii)  ~x or y       which "means either x is false, or y is true".  Example:  i)    A person's being alive implies that he or she has       a beating heart  ii)   If a person is alive, then he or she has a       beating heart  iii)  Either a person has a beating heart, or       he or she is dead      

This permits us to write "x ® y" as "~x or y" (although English idiom often has "y or ~x" but the statements are equivalent as a truth table check shows).

We take "x « y" to mean "x is true only if y is true and y is true only if x is true" which can be written (x ® y) and (y ® x)

---

We accept these definitions and conditions a priori:

A set is defined by its elements, not by its descriptions. For example, let A = {r|r is a real root of x² -5x + 6 = 0} and B = {2,3}. In that case, A = B.

Every element is unique. That is, if A = {2} and B = {2,2}, then A = B.

A set is permitted to be an element of another set, (but in standard theory it can't be a member of itself). By this we see that every set is unique.

A subset of a set is itself a set.

B subset of A means (using "e" for "element of"):

x e B ® x e A

Equality means

x e B « x e A, meaning B is a subset of A and A is a subset of B.

---

First, let us see that every set has a an empty subset, meaning you cannot remove the null subset from a set.

Let us provisionally call B a subset of A and then require that B have no elements.

By definition, x e B ® x e A, which is equivalent to

x ~e B or x e A

which is true, since x is not a member of B. Even if x is not a member of A (perhaps A is empty), the statement remains true.

That is, a subset with no elements satisfies the definition of subset.

Now suppose our presumption that any set A has a null subset is false. Using { }_A to mean null subset of A, we have:

i. ~(x e { }_A ® x e A), or,

ii. ~(x ~e { }_A or x e A), or,

iii. x e { }_A and x ~e A,

This last is false simply because x ~e { }_A. That is, "x e { }_A or x ~e A" is true, but the "and" makes the statement wrong.

Hence our suggestion is correct.

Now to prove uniqueness we simply need show that { }_A = { }_B for arbitrary sets A and B. We have

x e { }_A « x e { }_B, or,

(x ~e { }_A or x e { }_B) and (x ~e { }_B or x e { }_A).

To the left of the "and" we have the truthfulness of x not being an element of { }_Aand similarly to the right.

Hence { }_A = { }_B

Remembering that any subset is a set, our claim that only one null set exists is verified.

---

It is also instructive to verify the uniqueness of the null set by considering complement sets.

Adopting the notation for the complement set, we have

x e A\B ® x ~e B

We know that A = A and so A is a subset of A. This fact allows us to write:

x e A\A ® x ~e A

which is true. Look at the rewritten statement:

~(x ~e A) ® ~(x e A\A), or

x e A ® x ~e A\A.

Now this holds for any variable. Hence A\A is a set with no elements.

Now suppose B ~= A. Nevertheless,

x e B\B « x e A\A

as we see from

(x ~e B\B or x e A) and (x e B\B or x ~e A),

which is true.

So let us denote A\A with an empty set symbol { } and consider the cases { }\{ }, ~{ }\{ }, and { }\~{ }.

i.    x e { }\{ } --> x e { } and x e { }           which holds vacuously [note transformations above]  ii.   x e ~{ }\{ } --> x e ~{ } and x ~{ }           which is true.  iii.  x e { }\~{ } --> x e { } and x ~e ~{ }           which means       x e {}\~{} --> x e {} and x e {}           which is false, meaning that the expression           {}\~{} is not defined in standard set 

theory.

Now we have that A\A = B\B = { }\{ } = { }, establishing that the null subset of any set is indistinct from the null subset of any other set, meaning that there is exactly one null set.

Note on 'exclusive or' symbolism

Today's preferred symbol for the exclusive or operation is "XOR". Yet even today the plus sign "+" is used to denote exclusive or. This symbol derives from "<--/-->", meaning "does not strictly imply." The truth table for nonexclusive or is

 i)     A  B     ----     T  F   T     F  T   T     T  T   T     F  F   F 

whereas the truth table for exclusive or is

ii)     A  B     ----     T  F   T     F  T   T     T  T   F     F  F   F 

By transforming the statement A <--/--> B, we will arrive at table ii. To wit: A <--/--> B

= not-((A --> B) & (B --> A))

= not-((not-A v B) & (not-B v A))

applying de Morgan's negation law, we get

not-(not-A v B) v not-(not-B v A)

A second application of that law yields

(A v not-B) v (not-A v B)

This formalism includes the possible expression:

(A & not-B) and (B and not-A), which is equavalent to

(A & not-A) & (B & not-B)

which, as a contradiction, must be disregarded, leaving the two remaining possibilities:

A & not-B

B & not-A

, conforming to table ii.

---

---

Thanks to John Peterson, an alert reader who caught a point of confusion that was due to two typographical errors, since corrected.