Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects.

1 Basics

We begin by going through the basic notations, and how to represent sets by using these notations and Venn diagrams.

1.1 Set roster notation

In the roster form, we list down all the elements of a set within curly brackets. In sets, we only write down the distinct elements, i.e. repeated elements only need to be written down once.

Examples:

• Let A be set of letters in the word “apple”. Then, A = {a, p, l, e}
• Let B be the set of positive integers less than 5. Then, B = {1, 2, 3, 4}

1.2 Set builder notation

With set builder notation, we can represent sets more succintly. For example, if we want to represent the set of numbers from 1 to 1000 with set roster notation, we would have to list down 1000 elements.

• In set builder notation, we split the set into two portions. The left represents the universe of discourse and the right is the property of the elements that belong to the set.
• The universe of discourse or universe for short, is the defined class that contains the sets.
• “|” symbol means “such that”.
• “∈” symbol means “is a member of”.

Examples:

• {x ∈ Z | x is odd} represents the set of all odd integers. “Z” here represents integers.
• {x ∈ N | x is an even and less than 15} is equivalent to {2, 4, 6, 8, 10, 12, 14}.

Common universe of discourse:

Symbol	Meaning
N	natural numbers
Z	integers
Q	rational numbers
R	real numbers
C	complex numbers
I	imaginary numbers

1.3 Cardinality of a set

Cardinality of a set S, denoted by |S| is the number of elements in the set.

• If a set has infinite elements, its cardinality is ∞.

Examples:

• | {1, 2, 3, 4} | = 4
• | {1, 2, 3, 4, …} | = ∞

1.4 Types of sets

There are many types of sets. A set can be described as a finite set, an infinite set, a subset, a proper subset, a universal set, a singleton set, an empty set, etc.

1.4.1 Finite and infinite sets

A set with a finite number of elements is a finite set and a set with an infinite number of elements is an infinite set.

Examples:

• {x | x ∈ N and 1 < x < 5} is a finite set.
• {x | x ∈ N and x > 10} is an infinite set.

1.4.2 Universal sets

A universal set is the set of all elements in the universe of discourse. It is denoted by the capital letter “U”. We can define U as the set of animal species in Kenya, the set of STEM subjects and so on.

1.4.3 Proper and improper subsets

A set X is a subset of set Y (denoted as X ⊆ Y) if every element of X is an element of Y.

• In other words, X ⊆ Y iff ∀x ∈ U(x ∈ X → x ∈ Y).
• If there exists an element in the set X such that it is not an element in the set Y, then it can no longer be considered a subset of Y.
• Every set is a subset of itself. This implies that equal sets are subsets of each other.

A proper subset can be defined as “subset of but not equal to”.

• A set X is a proper subset of Y (denoted as X ⊂ Y) iff every element of X is an element of Y and |X| < |Y|.

1.4.4 Empty set or null set

An empty set is a set with no elements.

• It is denoted by ∅ or { }.
• An empty set is a subset of every set.
• |∅| = 0

1.4.5 Singleton set

A singleton set is a set that contains only one element.

Example:

• S = {x | x ∈ N, 7 < x < 9} = {8}.
• |S| = 1 hence it is a singleton set.

1.4.6 Equal sets vs equivalent sets

• A set X is equal to a set Y if and only if they contain the same elements.
• A set X is equivalent to a set Y if they have the same cardinalities.

1.4.7 Overlapping sets vs disjoint sets

• Two sets are said to be overlapping when they have at least one common elements.

• Two sets are said to be disjoint when they do not have any common elements.

  

1.4.8 Power sets

A power set of a set S, denoted as P(S) is the set of all subsets of S.

• The cardinality of |S| = 2$^n$, where n is the number of elements.

Example:

Let A = {1, 2, 3}. Then,

• P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1,3}, {2,3}, {1, 2, 3}}

• |P(A)| = 2$^3$ = 8

2 Set Operations

Now that we have a basic sense of what sets are like, let’s look at what kind of operations we can do on sets.

2.1 Union

The union of sets A and B is denoted as A $∪$ B. It is the disjunction of the elements of the sets A and B.

2.2 Intersection

The intersection of sets A and B is denoted as A $∩$ B. It is the conjunction of the elements of the sets A and B.

2.3 Complement

The complement of the set A is denoted as A'. It is the set of elements outside of A.

2.4 Set difference

The difference between the sets A and B, wirtten as A - B or A \ B, is the set of elements that are in A but not in B.

2.5 Cartesian product

The cartesian product of n number of sets A₁, A₂, …, A_n,… denoted as A₁ X A₂ X … X A_n can be defined as all possible ordered pairs (x₁, x₂, …, x_n) where x₁ ∈ A₁, x₂ ∈ A₂, …, x_n ∈ A_n.

Example:

Let A = {a, b} and B = {1, 2}

• The cartesian product of A and B is written as A X B.
• A X B = {(a, 1), (a, 2), (b, 1), (b,2)}
• The cartesian product of A and B is written as B X A.
• B X A = {(1, a), (1, b), (2, a), (2,b)}

3 Inclusion-Exclusion Principle

The inclusion-exclusion principle states that for n number of finite sets,

• |A₁ ⋃ A₂ ⋃ A₃ ⋃ … ⋃ A_n| = $Σ$|Ai ⋂ Aj| + $Σ$|Ai ⋂ Aj ⋂ Ak| – … + (-1)^n-1 |A₁ ⋃ A₂ ⋃ A₃ ⋃ … ⋃ A_n|.

The formula looks really complicated but the concept is actually easy to grasp if break it down into a few examples:

Example 1: Inclusion-exclusion principle on 2 sets

Example 2: Inclusion-exclusion principle on 3 sets

4 Set Identities

An identity is an equation that is universally true for all elements in some set. It is conceptually similar to the laws of logic that we learned previously. We should familiarise ourselves with these set identities as it will very useful when we need to prove the equality of sets.