|
|
Paul Conant's home page
When is truth vacuous? Is infinity a bunch of nothing?
John Allen Paulos. Probability and politics
D.J. Velleman. Set theory and logic
Herbert B. Enderton. Set theory and logic
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.
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)
A set is defined by its elements, not by its descriptions. For example, let A = {r|r is a real root of x2 -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.
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 the statement that our belief that any set A has a null subset is false. Using { }A to mean null subset of A, we have:
~({ }A subset A), or,
~(x e { }A ® x e A), or,
~x ~e { }A or x e A), or,
x e { }A and x e A,
a contradiction, even if A is also empty.
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.
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.