¬(A ∩ B) = (¬A) ∪(¬B)The paradoxes
There are no problems dealing with finite sets because we can list their
elements, as in A = {1, 2, 3, 4, 5}, but in Cantor’s time, infinite sets were more
challenging.
Cantor defined sets as the collection of elements with a specific property.
Think of the set {11, 12, 13, 14, 15,.. .}, all the whole numbers bigger than
- Because the set is infinite, we can’t write down all its elements, but we can
still specify it because of the property that all its members have in common.
Following Cantor’s lead, we can write the set as A = {x: x is a whole number >
10}, where the colon stands for ‘such that’.
In primitive set theory we could also have a set of abstract things, A = {x: x is
an abstract thing}. In this case A is itself an abstract thing, so it is possible to
have A ∈ A. But in allowing this relation, serious problems arise. The British
philosopher Bertrand Russell hit upon the idea of a set S which contained all
things which did not contain themselves. In symbols this is S = {x: x∉x}.
He then asked the question, ‘is S ∈ S?’ If the answer is ‘Yes’ then S must
satisfy the defining sentence for S, and so S∉S. On the other hand if the answer
is ‘No’ and S ∈ S, then S does not satisfy the defining relation of S = {x: x ∉ x }
and so S ∈ S. Russell’s question ended with this statement, the basis of Russell’s
paradox,
S ∈ S if and only if S ∉ S
It is similar to the ‘barber paradox’ where a village barber announces to the
locals that he will only shave those who do not shave themselves. The question
arises: should the barber shave himself? If he does not shave himself he should.
If does shave himself he should not.
It is imperative to avoid such paradoxes, politely called ‘antinomies’. For
mathematicians it is simply not permissible to have systems that generate
contradictions. Russell created a theory of types and only allowed a ∈ A if a were
of a lower type than A, so avoiding expressions such as S ∈ S.
Another way to avoid these antinomies was to formalize the theory of sets. In
this approach we don’t worry about the nature of sets themselves, but list formal
axioms that specify rules for treating them. The Greeks tried something similar