Basics of Set

Subjects to be Learned

• equality of sets
• subset, proper subset
• empty set
• universal set
• power set

Contents

Definition (Equality of sets): Two sets are equal  if and only if  they have the same elements.
More formally,   for any sets A and B,  A = B   if and only if   x [ x A      x B ] .

Thus for example {1, 2, 3} = {3, 2, 1} , that is the order of elements does not matter, and {1, 2, 3} = {3, 2, 1, 1}, that is duplications do not make any difference for sets.

Definition (Subset): A set A is a subset of a set B if and only if   everything in A is also in B.
More formally,   for any sets A and B,  A is a subset of B, and denoted by A B,   if and only if   x [ x A      x B ] .
If A B, and A B, then A is said to be a proper subset of B and it is denoted by A B .

For example {1, 2} {3, 2, 1} .
Also {1, 2} {3, 2, 1} .

Definition(Cardinality): If a set S has n distinct elements for some natural number n, n is the cardinality (size) of S and S is a finite set. The cardinality of S is denoted by |S|.

For example the cardinality of the set {3, 1, 2} is 3.

Definition(Empty set): A set which has no elements is called an empty set.
More formally,  an empty set, denoted by , is a set that satisfies the following:
x   x ,
where means "is not in" or "is not a member of".

Note that and {} are different sets. {} has one element namely in it. So {} is not empty. But has nothing in it.

Definition(Universal set): A set which has all the elements in the universe of discourse is called a universal set.
More formally,  a universal set, denoted by U , is a set that satisfies the following:
x   x U .

Three subset relationships involving empty set and universal set are listed below as theorems without proof. Their proofs are found elsewhere.

Note that the set A in the next four theorems are arbitrary. So A can be an empty set or universal set.

Theorem 1: For an arbitrary set A   A U .

Theorem 2: For an arbitrary set A   A .

Theorem 3: For an arbitrary set A   A A .

Definition(Power set): The set of all subsets of a set A is called the power set of A and denoted by   2A  or   (A) .

For example for A = {1, 2},  (A) = { , {1}, {2}, {1, 2} } .

For B = {{1, 2}, {{1}, 2}, } ,  (B) = { , {{1, 2}}, {{{1}, 2}}, {}, { {1, 2}, {{1}, 2 }}, { {1, 2}, }, { {{1}, 2}, }, {{1, 2}, {{1}, 2}, } } .

Also   () = {}   and   ({}) = {, {}} .

Theorem 4: For an arbitrary set A,  the number of subsets of A is 2|A| .

Test Your Understanding of Basic Set Concepts

Next -- Mathematical Reasoning

Back to Schedule