Sets

A set is a collection of objects. If A and B are sets, ∧ is conjunction, ∨ is disjunction, ¬ is negation, and ⇔ is equivalence then

• Θ is the empty set.
• |A| is the cardinality of A which is the number of elements in A.
• a∈A means a is a member of A
• A⊆B⇔A⊂B∨A=B. A is a subset of B.
• A⊂B⇔a∈A⇒a∈B. A is a proper subset of B.
• a∈A∪B⇔a∈A∨a∈B. The union of A and B.
• a∈A∩B⇔a∈A∧a∈B. The intersection of A and B.
• a∈A-B⇔a∈A∧¬a∈B. The difference of A and B.

Some identities:

• A∩B=B∩A
• A∪B=B∪A
• A∩Θ=A
• A∪Θ=A
• A∪(B∪C)=(A∪B)∪C
• A∩(B∩C)=(A∩B)∩C
• A∪(B∩C)=(A∪B)∩(A∪C)
• A∩(B∪C)=(A∩B)∪(A∩C)
• A-(B∪C)=(A-B)∩(A-C)
• A-(B∩C)=(A-B)∪(A-C)

A set is sometimes written {a,b,c}, or {x|f(x)}. A set A is a singleton set if |A|=1. Two sets A and B are disjoint if A∩B=Θ. A set of sets {A0,A1,...,An} is pairwise disjoint if 0≤i≠j≤n Ai∩Aj=Θ.

Some sets:

• The set R is the set of all real numbers.
• The set Z⊂R={...,-2,-1,0,1,2,...} is the set of all integers.
• The set N⊂Z={0,1,2,...} is the set of all natural numbers.

A set whose a cardinality is a natural number is finite. A set which is not finite is infinite. If there is an bijection between the set A and N, then we say that A is countably infinite.

The power set of a set A, written either as P(A) or 2A, is the set of all subsets of A

The Cartesian product of the sets A0,A1,...,An is the set {(a0,a1,...,an)|a0∈A0∧a1∈A1∧...∧an∈An}. This is sometimes written as A0×A1×...×An.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.