Sets

Informally, a set is a collection of elements (also called members). 

If X is a set and e is an element of X, then we write eX.  If e is in not in X, then we write eX

We have two ways of specifying the elements of a specific set. 

extensionally
We can list all the elements of the set, in curly braces, separated by commas.  The list is termed the set's extension.  For example, {1,2,3} is the set whose elements are 1, 2, and 3; the extension of "the positive integers no greater than 3" is {1,2,3}.  Each element of the set is listed exactly once. 
intensionally
Let P(x) be a predicate that is true or false for each possible x in some already-existing set E.  Then we write the set S of elements x for which P(x) is true as S={xE | P(x)}.  Where it is clear from context what set E is intended, we simply write {x | P(x)}.  It is clear that in all such cases SE. 

The empty set is the unique set that contains no elements.  We write the empty set as or {}. 

A singleton set is a set containing exactly one element.  For example, {a}, {}, and { {a} } are all singleton sets (the lone member of { {a} } is {a}). 

The cardinality or size of a set is the number of elements it contains.  We write the cardinality of set S as |S|. 

The cardinality of the integers is represented by ω; many (but not all) infinite sets also have this cardinality and are said to be countably infinite, countable, or enumerable, because their elements can be "counted" or placed in correspondence with the integers.  Examples:  || = 0, |{a,b,c}| = 3, |{all even numbers}| = ω

Relations between sets

Set X is a subset of set Y iff eX implies eY for every e.  We write this as XY is an order relation

Sets X and Y are equal iff they have exactly the same elements.  Equivalently, X and Y are equal iff XY and YX

Constructing a set from other sets

The intersection of sets X and Y, written XY, is the set {x | xX and xY}. 

The union of sets X and Y, written XY, is the set {x | xX or xY}. 

The difference of sets X and Y, written X-Y or X\Y, is the set {x | xX and xY}.  Where X can be assumed:  the complement of Y with respect to X, written Y, is the set X-Y

The powerset of set X, written X or P X or 2X, is the set of all subsets of X.  (Detailed discussion)  A powerset is a partially-ordered set

The (Cartesian) product of sets X and Y, written X×Y, is the set of pairs {(x,y) | xX and yY}.  (Example

Products may be of any positive arity (or order) n, in which case the n-ary (Cartesian) product X1×...×Xn is the set of n-tuples {(x1,...,xn) | x1X1∧...∧xnXn}.  The smallest arities have names: 

The quotient of set X by equivalence relation E, written X/E, is the set of equivalence classes into which E partitions X

Properties of set operations

Property Definition for and Definition for and
idempotent XX = X XX = X
commutative XY = YX XY = YX
associative (XY)Z = X(YZ) (XY)Z = X(YZ)
distributive X(YZ) = (XY)(XZ) X(YZ) = (XY)(XZ)
De Morgan's laws XY = X Y XY = X Y
U-(XY) = (U-X)(U-Y) U-(XY) = (U-X)(U-Y)
absorptive X(XY) = X = X(XY)

In the table above, De Morgan's laws are given twice, equivalently:  once in terms of complement (with respect to an implicit universe), and once in terms of subtraction from a specified universe U

I know no names for these useful equivalences involving set difference: 

− and − and
0. XY−((XY)(YX)) = XY
1. (XZ)(YZ) = (XY)−Z (XZ)(YZ) = (XY)−Z
2. X(YZ) = (XY)−(ZX) X(YZ) = (XY)−(ZX)

You will notice that the properties of and are interchangeable, in a sense.  Every property that is true for is also true for ; more generally, if P is a property involving and , then there is a property P (pronounced "P dual") that is P with every instance of replaced by , and every instance of replaced by , such that PP.  This relation between the two operators is termed duality and is an instance of the duality that holds in any ordered set. 

It is worth noting that set difference (−) is neither commutative nor associative:

Property Explanation
− is not commutative X−Y ≠Y−X for some X and Y
− is not associative (XY)−Z ≠X−(YZ) for some X, Y, and Z

Closure

Let S be a set, and O an operation that takes 0 or more operands (x1,x2,...) from S and returns a value.  S is closed under O iff for all x1,x2,...S, O(x1,x2,...)S. 

Examples:

The integers are closed under addition. 
The sum of any two integers is also an integer. 
The integers are not closed under division. 
Counterexample: 1 divided by 2 is not an integer. 
A powerset is closed under intersection. 
A powerset 2S contains all subsets of S.  The intersection of two subsets of S contains no elements not in S, so the intersection is also a subset of S and thus an element of 2S.

A new set can be created by closing an existing basis set under an operation; the new set is called the closure of the basis set under the operation. 

Most commonly, when we say closure we mean transitive closure, the set resulting from closing the closure of the ... of the closure of the basis set. 

The closure of {1} under +
The closure consists of the result of applying + to every pair of elements in {1}:  1+1=2.  The closure is {1,2}. 
The transitive closure of {1} under +
The closure consists of the result of
  1. 1.  applying + to every pair of elements in {1}:  1+1=2, resulting in {1,2};
  2. 2.  then applying + to every pair of elements in that closure {1,2}:  1+1=2, 1+2=3, 2+1=3, 2+4=4, resulting in {1,2,3,4};
  3. 3.  then applying + to every pair of elements in that closure {1,2,3,4}:  ... 
  4. ...

and so forth until the set is closed (after an infinite number of closures, in this case). 
The transitive closure of {1} under + is the set of positive integers. 

The transitive closure of { {a},{b},{c} } under
The closure consists of the result of
  1. applying to every pair of elements in { {a},{b},{c} }:  {a}{a{=}a}, {a}{b{=}a,b}, {a}{c{=}a,c}, {b}{a{=}a,b}, {b}{b{=}b}, {b}{c{=}b,c}, {c}{a{=}a,c}, {c}{b{=}b,c}, {c}{c{=}c}, resulting in { {a},{b},{c},{a,b},{a,c},{b,c} };
  2. then applying to every pair of elements in that closure { {a},{b},{c},{a,b},{a,c},{b,c} }, resulting in one new element {a,b,c};

Further closure cycles add no new elements.  In this case, closure was achieved after a finite number of cycles (two).  The transitive closure of { {a},{b},{c} } under is { {a},{b},{c},{a,b},{a,c},{b,c},{a,b,c} } (the powerset of {a,b,c}, incidentally). 

Enumerating infinite sets

We enumerate (count) finite sets by mapping a positive integer to each element, starting with 1 and continuing in sequence.  For example, we could count the vowels "a e i o u" thus: 

Extension of the set a e i o u
Enumerating it 1 2 3 4 5

The same approach is used to enumerate infinite sets, except that just as we can't list the extension of an infinite set but have to define it intensionally with a rule, we can't count it either but instead have to give a rule for how we would count it.  Here's one way to enumerate the integers (positive, negative, and zero).  We start at 0, then alternate sides with 1, −1, 2, −2, 3, −3, .... 

Extension of the set ... −j ... −2 −1 0 1 2 ... j ...
Enumerating it ... 2j+1 ... 5 3 1 2 4 ... 2j ...
(j is a positive integer, so −j is negative)

In our enumeration, every integer gets a distinct positive integer:  0 gets 1, positive integer j gets 2j, and negative integer −j gets 2j + 1.  Thus the integers are enumerable (because we've given a rule that enumerates them). 

You might think that the rationals (integer fractions) are not enumerable (because there are so many of them).  However, the following scheme shows the concept for enumerating the positive rationals. 

The table on the left arranges the rationals so that each rational appears at least once — rational j/k appears in column j, row k (j, k > 0).  (Actually, every number appears infinitely many times, for example 1/2 appears equivalently as 1/2, 2/4, 3/6, ....) 

The table on the right enumerates the cells of the table on the left by diagonals, Fibonacci-style. 

The positive rationals
1 2 3 4 ...
1 1/1 2/1 3/1 4/1 ...
2 1/2 2/2 3/2 4/2 ...
3 1/3 2/3 3/3 4/3 ...
4 1/4 2/4 3/4 4/4 ...
... ... ... ... ... ...
An enumeration
1 2 3 4 ...
1 1 3 6 10 ...
2 2 5 9 ...
3 4 8 ...
4 7 ...
... ...
zig-zags

All the (positive) rationals get counted at least once, so they are enumerable.  The rule can easily be extended to cover zero and the negative rationals using the approach that enumerated the integers. 

Diagonalization

digit #
list 1 2 3 4 ... n ...
1.  0. 7 5 2 0 ... 4 ...
2.  0. 4 3 1 5 ... 6 ...
3.  0. 8 6 6 3 ... 6 ...
4.  0. 2 9 2 5 ... 8 ...
... ...
n.  0. 3 2 5 6 ... 2 ...
... ...

Diagonalization is a technique for showing that the elements of a set are not countable.  We will illustrate it with the set of real numbers between 0 and 1. 

The table shows a list of the real numbers between 0 and 1, in some arbitrary order (it doesn't matter what order).  The first real number in this particular order has a decimal representation begins with 0.75206...; the second one begins with 0.43158..., the third with 0.86630..., and so on.  The (infinite) table lists the infinite number of digits of each of the numbers; we show the 1st through 5th digits, and then also the nth digit.  It doesn't matter what n is (except that in our example, it must be bigger than 5); it's just some large positive integer.  We also show the nth number in the list, which begins with 0.32568.... 

We can use diagonalization to show that there is a real number that is not in the list, even though the list is (countably) infinite.  We do this by conceptually stating a number, digit by digit: 

• Its 1st digit is different from the 1st digit of the 1st number (say, 6 instead of 7)
(although it doesn't matter which
as long as it's different).
 
• Its 2nd digit is different from the 2nd digit of the 2nd number (say, 2 instead of 3). 
• Its 3rd digit is different from the 3rd digit of the 3rd number (say, 5 instead of 6). 
• Its 4th digit is different from the 4th digit of the 4th number (say, 4 instead of 5). 
• ...
• Its nth digit is different from the nth digit of the nth number (say, 1 instead of 2). 
• And so on without end.

This number with an infinite number of digits, 0.62546..., is not in the list.  We know this, even though we don't know all the digits of the number, because it is different from the jth number in the list, for any j, in its jth digit.  It doesn't matter in what order we list the numbers; it is true in general.  We have just shown that the real numbers are not countable:  there are more real numbers than there are integers. 

Interestingly, the rationals are countable, so that in a very practical sense there are not more rationals than integers.  The rationals cannot be diagonalized because in general an arbitrary decimal fraction with an infinite number of digits is not going to be a rational number (it will be real, but not rational), so the counterexample that diagonalization produces can't be guaranteed to be a rational number.  Similarly, the integers can't be diagonalized (such a table would be infinite to the left, not the right, and show the digits of each integer in the list) because the counterexample has an infinite number of digits and no integer has an infinite number of digits. 

We can also use diagonalization to show that the powerset of a countably infinite set is not countable. 

Diagonalization is due to Georg Cantor, circa 1880. 

Russell's paradox

We must be just a bit careful when allowing sets to be elements of other sets, as this can lead to paradoxes.  The first such paradox was discovered by Bertrand Russell not long after sets were first introduced (circa 1900).  Let R be the set containing all sets that do not contain themselves.  Does R contain itself? 

  1. Assume R contains itself.  Then R cannot contain itself, as R only contains sets that do not contain themselves. 
  2. Assume R does not contain itself.  Then R must contain itself, as R contains all sets that do not contain themselves. 

Not a happy situation!

There are a number of ways of avoiding Russell's Paradox by carefully defining sets and their operations.  We avoid Russell's Paradox by restricting sets to be constructed only from sets that already exist (specifically, when naming a set by intension, we require that its elements be drawn from some other already-existing set E).  Thus we provide no way of constructing a set that contains all sets that do not contain themselves; there is only , , −, , ×, and intensional definition of a subset of an already existing set, and these aren't enough to construct R

Valid XHTML 1.0 Strict
Valid CSS!
2009Sep23We10:12
Thomas A. Alspaugh