## 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