## Introduction

Sets are a primitive foundational concept in mathematics. Advanced concepts such as counting, probability, relations, functions, groups, and rings rely on a solid understanding of sets.

This learning module has many interactive demos. It is easier to work with them on a larger screen.
Bookmark and revisit if you are currently on a small screen device.

Sets are a primitive foundational concept in mathematics. Advanced concepts such as counting, probability, relations, functions, groups, and rings rely on a solid understanding of sets.

A **set** is an unordered collection of distinct objects. The objects that make up a set are called its **elements** or **members**.

- The collection of all even natural numbers less than 10 is a set. It consists of the elements \( 2, 4, 6, \) and \( 8 \).
- The set of all vowels in the English alphabet contains the members \( a, e, i, o, u \).

It is customary to use uppercase letters such as \( A, B, C, \ldots \) to denote sets. Lowercase letters such as \( a, b, c, \ldots \) are used to denote the elements of a set.

Consider a set \( S \) consisting of the elements \( a \), \( b \), and \( c \). This set definition is denoted as \( S = \lbrace a, b, c \rbrace \) to show the membership.

The specific ordering of elements in a set does not matter. By definition, they are unordered collections. So, the set \( S = \lbrace a, b, c \rbrace \) can also be written as \( S = \lbrace b, c, a \rbrace \).

However, note that it is mathematically more elegant to write them in an order that avoids confusion and enables intuition to the reader. Hence, the preferred form is \( S = \lbrace a, b, c \rbrace \).

The number of elements in a set is known as the **cardinality** of the set.
The cardinality of the set \( S = \lbrace a, b, c \rbrace \) is 3.

In set notation, the cardinality of a set S is usually denoted as \( | S | \). In our example, \( | S | = 3 \).

Consider the set \( S = \lbrace a, b, c \rbrace \).

In our example, the element \( a \) belongs in the set \( S \). This relationship is denoted as \( a \in S \). It is read as "\( a \) in \( S \)".

The element \( d \) does not belong in the set \( S \). This relationship is denoted as \( d \not\in S \). It is read as "\( d \) not in \( S \)".

Sometimes it is infeasible to describe a set by explicitly listing its elements.
In such circumstances, it is common to describe sets based on shared properties of its elements.
In other words, it is easier to give a recipe to *build* the set.

Such notation, known as the **set builder notation** is written as

$$ S = \lbrace x : \text{a property that defines which } x\text{'s are included} \rbrace $$

The set of all real numbers that are less than 5 can be described as

$$ S = \lbrace x : x < 5 \rbrace $$

Two sets are considered **equal** if and only if they contain the exact same elements. This relationship is denoted as \( A = B \).
Conversely, if two sets are not equal, the relationship is denoted as \( A \ne B \).

By definition, a set contains distinct elements. Having duplicates in a set is meaningless because of the definition of set equality.

Consider the sets \( A = \lbrace 1, 1, 2, 3 \rbrace \) and \( B = \lbrace 1, 2, 3 \rbrace \). Two sets are considered equal if they contain the same elements. Because any element in \( A \) is also in \( B \), it is the case that \( A = B \).

In this example, the duplicates in the set \( A \) were shown to explain the futility of a set with repetitions, since it turns out to be equal to another without them. **Multi-sets** are a general concept that allow for repetitions. \( A \) would be considered a multi-set in this case.

A set \( A \) is known as a subset of the set \( B \), if every element in the set \( A \) is also in the set \( B \). The subset relationship is denoted as \( A \subseteq B \). Note that \( A \subseteq B \) includes the possibility of the sets being equal, or \( A = B \).

If \( A \ne B \) and \( A \subseteq B \), then it means that all elements of \( A \) are present in \( B \), but it has strictly fewer elements than in \( B \). In this case, \( A \) is considered to be a **proper subset** of the set \( B \). This relationship is denoted as \( A \subset B \).

Consider the sets \( A = \lbrace 1, 2, 3 \rbrace \), \( B = \lbrace 1, 2, 3 \rbrace \), and \( C = \lbrace 1, 2, 3, 4 \rbrace \).

- Every element of the set \( A \) is also contained in the set \( B \). Moreover, \( A = B \). Thus, \( A \subseteq B \).
- The set \( C \) contains every element of the set \( A \) and those of set \( B \). Also, \( A \ne C \) and \( B \ne C \). Therefore, \( A \subset C \) and \( B \subset C \).

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and see if they are related by the subset relationship.

Consider the sets \( A \), \( B \), and \( C \), such that \( A \subseteq B \) and \( B \subseteq C \). This implies that all elements of the set \( A \) are also in set \( C \). Thus, \( A \subseteq C \).

A set devoid of any elements is known as the **empty set**. It is also alternatively known as the **null set** or the **void set**.

It is usually denoted as \( \emptyset = \lbrace \rbrace \).

The set consisting of all possible subsets of a set \( A \) is known as the **power set** of \( A \).

For example, if \( A = \lbrace 1,2 \rbrace \), then its power set is \( \lbrace \lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 1, 2 \rbrace \rbrace \).

Note that the null set is part of the power set.

The set of all **positive integers**, also known as **natural numbers**, is denoted as \( \natural = \lbrace 1, 2, 3, \ldots \rbrace \).

The set of all **integers** (positive, negative, and zero) is denoted by \( \mathbb{Z} = \lbrace \ldots, -2, -1, 0, 1, 2, 3, \ldots \rbrace \).

The set of all **real numbers** is denoted by \( \real \). The set of positive real numbers is usually denoted as \( \real^+ \).

The set of all **rational numbers** are real numbers that can be expressed in the form \( \frac{m}{n} \) where \( m, n \in \mathbb{Z} \) and \( n \neq 0 \), is denoted by \( \mathbb{Q} \).

Real numbers that are not rational, are known as **irrational numbers**. They are represented as \( \mathbb{I} \).

Finally, the set of **complex numbers**, those that can be expressed as \( a + bi \) where \( a, b \in \real \) and \( i = \sqrt{-1} \), is denoted as by \( \mathbb{C} \).

Note the relationship among these special sets

$$ \natural \subset \mathbb{Z} \subset \mathbb{Q} \subset \real \subset \mathbb{C} $$

The set of all real numbers between \( a \) and \( b \), excluding \( a \) and \( b \) is known as the **open interval** between \( a \) and \( b \). It is denoted as \( (a,b) \).

$$ (a,b) = \lbrace x \in \real: a < x < b \rbrace $$

The set of all real numbers between \( a \) and \( b \), including \( a \) and \( b \) is known as the **closed interval** between \( a \) and \( b \). It is denoted as \( [a,b] \).

$$ [a,b] = \lbrace x \in \real: a \le x \le b \rbrace $$

The set of all real numbers between \( a \) and \( b \), such that one of the boundaries is included in the set is known as **half-open** or **half-closed** interval.

Depending on the boundary being included in the set, they are denoted and defined as follows

$$ [a,b) = \lbrace x \in \real: a \le x < b \rbrace $$ $$ (a,b] = \lbrace x \in \real: a < x \le b \rbrace $$

There are several ways to combine sets to form another set.

The **union** of two sets \( A \) and \( B \), denoted as \( A \cup B \), results in a set that includes all elements belonging to either \( A \) or \( B \).

$$ A \cup B = \lbrace x : x \in A \text{ or } x \in B \rbrace $$

Note that the order of the operands does not matter for the set union. So, \( A \cup B = B \cup A \).

Set union generalizes to more than two sets to include elements contained in any of those sets. The union of \( n \) sets \(A_1, A_2, \ldots, A_n\) is denoted as

\begin{align} \bigcup\limits_{i=1}^n A_i = &~ A_1 \cup A_2 \ldots \cup A_n \\\\ = &~ \lbrace x: x \text{ in any of } A_i, \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace \end{align}

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \) and the set \( B = \lbrace 2, 3, 4 \rbrace \). Then, \( A \cup B = \lbrace 1, 2, 3, 4 \rbrace \).

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and understand the composition of their union, \( \sA \cup \sB \).

The **intersection** of two sets \( A \) and \( B \), denoted as \( A \cap B \), results in a set that includes all elements belonging to both the sets.

$$ A \cap B = \lbrace x : x \in A \text{ and } x \in B \rbrace $$

Note that the order of the operands does not matter for the set intersection. So, \( A \cap B = B \cap A \).

Set intersection generalizes to more than two sets to include elements contained in all of those sets. The intersection of \( n \) sets \(A_1, A_2, \ldots, A_n\) is denoted as

\begin{align} \bigcap\limits_{i=1}^n A_i = &~ A_1 \cap A_2 \ldots \cap A_n \\\\ = &~ \lbrace x: x \text{ in all of } A_i, \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace \end{align}

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \) and the set \( B = \lbrace 2, 3, 4 \rbrace \). Then, \( A \cap B = \lbrace 2, 3 \rbrace \).

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and understand the composition of their intersection, \( \sA \cap \sB \).

The **set difference** of two sets \( A \) and \( B \), denoted as \( A \setminus B \) or as \( A - B \), results in a set that includes all elements of the set \( A \) that do not belong to the set \( B \).
$$ A \setminus B = \lbrace x : x \in A \text{ and } x \not\in B \rbrace $$

Note that the order of the operands matters for the set difference. So, \( A - B \ne B - A \).

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \) and the set \( B = \lbrace 2, 3, 4 \rbrace \). Then, \( A \setminus B = \lbrace 1 \rbrace \) and \( B \setminus A = \lbrace 4 \rbrace \).

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and understand the composition of their difference, \( \sA \setdiff \sB \).

The **symmetric difference** of two sets \( A \) and \( B \), denoted as \( A \setsymmdiff B \) results in a set that contains elements that are either in A or in B, but not both.
Intuitively, it is the union of the relative complement of \( A \) and \( B \).

$$ A \setsymmdiff B = (A \setdiff B) \cup (B \setdiff A) $$

Consider the set \( A = \lbrace 1, 2, 3 \rbrace \) and the set \( B = \lbrace 2, 3, 4 \rbrace \). Their symmetric difference \( A \setsymmdiff B = \lbrace 1, 4 \rbrace \).

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and understand the composition of their symmetric difference, \( \sA \setsymmdiff \sB \).

Venn diagrams are a convenient way to visualize sets and their relationships. In a Venn diagram, sets are usually denoted as ellipses containing their elements.

For example, the following chart shows the sets \( \sA, \sB, \) and \( \sC \).

In the above Venn diagram, the set operations that we studied before are evident.

- Union: \( \sA \cup \sB = \set{2,0,6,8,5,1,7} \)
- Intersection: \( \sA \cap \sB = \set{1,6} \)
- Difference: \( \sA \setdiff \sB = \set{2,0,5} \)
- Symmetric difference: \( \sA \setsymmdiff \sB = \set{2,0,5,8,7} \)
- Subsets: \( \sA \not\subset \sB \)

Similar relationships can be drawn involving \( \sC \)

Sets with no common elements among them are known to be **disjoint**.

With no common elements, the intersection of disjoint sets is empty. In other words, \( A \cap B = \lbrace \rbrace \) if \( A \) and \( B \) are disjoint.

Of course, if the sets are disjoint then the set difference \( A - B = A \).

When dealing with several sets, it is sometimes necessary to talk about the all-encompassing set consisting of union of all the sets under consideration. This special set is known as the **universal set**.

If \( U \) denotes the universal set under consideration, then all the elements of \( U \) that are not in \( A \) is known as the **complement** of the set \( A \). It is denoted as \( \complement{A} \).

Thus, the set difference \( U - A = \complement{A} \).

Owing to this definition, the set difference \( A - B \) is sometimes also known as the **relative complement** of the set \( B \) in \( A \).

Sometimes, when dealing with unions and intersections over numerous sets, it is convenient to index the set notation using an **index set**, say \( C \). Each element \( c \in C \) is an index into a set \( S_c \) that we wish to include in our operations. Such a collection of sets is known as an **indexed collection of sets**.
Thus, the union and intersection over such an indexed collection is defined as

$$ \bigcup_{c \in C} = \lbrace x : x \in S_c \text{ for some } c \in C \rbrace $$ $$ \bigcap_{c \in C} = \lbrace x : x \in S_c \text{ for all } c \in C \rbrace $$

A collection \( C \) of subsets of a set \( A \) is said to be **pairwise disjoint** if every two distinct subsets that belong to \( C \) are disjoint.

Consider a set \( A = \lbrace w, x, y, z \rbrace \) and the collections \( C_1 = \lbrace \lbrace x,y \rbrace, \lbrace z \rbrace \rbrace \) and \( C_2 = \lbrace \lbrace x, y \rbrace, \lbrace y,z \rbrace \rbrace \).

Of these, the collection \( C_1 \) is pairwise disjoint, but the collection \( C_2 \) is not, because the element \( y \) repeats in both subsets of \( C_2 \).

A pairwise disjoint collection of the subsets of a set \( A \) such that each element of \( A \) is contained in some subset of the collection is known as a **partition** of the set \( A \).

In other words, a partition of a set \( A \) is a collection \( S \) of nonempty subsets of \( A \) such that each element of \( A \) belongs to exactly one subset in \( S \).

Consider a set \( A = \lbrace w, x, y, z \rbrace \) and the collections \( C_1 = \lbrace \lbrace x,y \rbrace, \lbrace z,w \rbrace \rbrace \) and \( C_2 = \lbrace \lbrace x, y \rbrace, \lbrace z \rbrace \rbrace \).

Of these, the collection \( C_1 \) is a partition, but the collection \( C_2 \) is not a partition because the element \( w \) does not appear in any of the subsets.

For a set \( A \), the empty set \(\emptyset\), and the universal set \( U \), the following laws are known as the **identity laws** because the set \( A \) retains its identity after these operations with the universal set and the empty set.

- \( A \cup \emptyset = A \)
- \( A \cap U = A \)

For a set \( A \), the empty set \(\emptyset\), and the universal set \( U \), the following laws are known as the **domination laws**, because the set \( A \) gets dominated after these operations with the universal set and the empty set.

- \( A \cup U = U \)
- \( A \cap \emptyset = \emptyset \)

For a set \( A \), the following laws are known as the **idempotent laws** because these operations when applied on the set itself does not affect the set.

- \( A \cup A = A \)
- \( A \cap A = A \)

The complement of a complement is the original set is known as the **complementation law**.

$$ \complement{(\complement{A})} = A $$

The following laws are known as the **commutative laws** because the union and intersection operations do not depend on the order of the operands.

For sets \( A \) and \( B \)

- \( A \cup B = B \cup A \)
- \( A \cap B = B \cap A \)

The following laws are known as the **associative laws** because repeated application of the union or the intersection operation does not depend on the order of operands.

For sets \(A, B, C \)

- \( A \cup (B \cup C) = (A \cup B) \cup C \)
- \( A \cap (B \cap C) = (A \cap B) \cap C \)

The following laws are known as **distributive laws** because the intersection of a union is a union of the intersections and vice versa.

For sets \(A, B, C \)

- \( A \cup (B \cap C) = (A \cap B) \cup (A \cap C) \)
- \( A \cap (B \cup C) = (A \cup B) \cap (A \cup C) \)

The **De Morgan's laws** for sets state that the complement of a union is the intersection of complements of the sets involved and vice versa.

For sets \( A \) and \( B \)

- \( \complement{(A \cup B)} = \complement{A} \cap \complement{B} \)
- \( \complement{(A \cap B)} = \complement{A} \cup \complement{B} \)

The order of elements in a set does not matter. Thus, \( \lbrace x, y \rbrace = \lbrace y, x \rbrace \).

In mathematics, an ordered collection of objects is known as a **sequence**. Unlike sets, repetitions of the same object are allowed in a sequence. Sequences are encapsulated by parentheses as \( (a_1, a_2, \ldots, a_n) \), to distinguish them from sets.

A sequence of squares of all natural numbers \( A = (1, 4, 9, \ldots, \infty) \), or succinctly as \( A = (n^2)_{n \in \natural} \)

A sequence of finite length \( n \) is known as an \(n\)-tuple.

The \(k\)-th element of an \(n\)-tuple is known as its \(k\)-th **coordinate**.

An \(n\)-tuple with 2 elements is known as a \(2\)-tuple or **ordered pair**. It is denoted as \( (x,y) \).

In this case, \( x \) is the known as the first **coordinate** and \( y \) is known as the second coordinate.

The **Cartesian product** of two sets \( A \) and \( B \), denoted as \( A \times B \), is the set of all ordered pairs whose first coordinate belongs to \( A \) and whose second coordinate belongs to \( B \).

$$ A \times B = \lbrace (x,y) : x \in A \text{ and } y \in B \rbrace $$

A Cartesian product of \( n \) sets \(A_1, A_2, \ldots, A_n\) is denoted as \( A_1 \times A_2 \times \ldots \times A_n \) and defined as

$$ A_1 \times A_2 \times \ldots \times A_n = \lbrace (a_1,a_2,\ldots,a_n) : a_i \in A_i \forall i \in \lbrace 1, 2, \ldots, n \rbrace \rbrace $$

If \( A = \lbrace x, y \rbrace \) and \( B = \lbrace 1, 2, 3 \rbrace \), then their Cartesian product

$$ A \times B = \lbrace (x,1), (x,2), (x,3), (y,1), (y,2), (y,3) \rbrace $$

Enter a comma-separated list of elements for the two sets \( \sA \) and \( \sB \) and understand the composition of their Cartesian product, \( \sA \times \sB \).

Two sets with the same number of elements are said to have the **same cardinality** or to be **numerically equivalent sets**.

Consider the sets \( A = \lbrace 1, 2, 3 \rbrace \), \( B = \lbrace 7, 8, 9 \rbrace \), and \( C = \lbrace 4, 5 \rbrace \).

Note that none of these sets are equal to each other. \( A \ne B \ne C \).

However, the sets \( A \) and \( B \) are numerically equivalent, because \( |A| = |B| = 3 \).

The set \( C \) is not numerically equivalent to \( A \) or \( B \), because \( |C| = 2 \).

A set \( A \) is called **denumerable** if \( |A| = |\natural| \), that is, if the set \( A \) has the same cardinality as the set of natural numbers.
Of course, if a set is denumerable, then it is also infinite. All denumerable sets are numerically equivalent.

The following are all denumerable sets

- The set of all integers
- The set of all even integers
- The Cartesian product of two denumerable sets, for example \( \natural \times \natural \)
- \( A = \lbrace x^2 : x \in \natural \rbrace \)

The following are not denumerable sets

- The set of all real numbers
- A set with finite number of elements such as \( A = \lbrace 1, 2 \rbrace \).

A set is said to be **countable** if it is denumerable or finite. Countable sets that are also denumerable are known as **countably infinite**.

The following are all countable sets, and all but the finite set are also countably infinite.

- The set of all integers
- The set of all even integers
- The Cartesian product of two denumerable sets, for example \( \natural \times \natural \)
- \( A = \lbrace x^2 : x \in \natural \rbrace \)
- A set with finite number of elements such as \( A = \lbrace 1, 2 \rbrace \).

The following sets are not countable.

- The set of all real numbers
- The set of all rational numbers
- The real interval \( (0,1) \)

A set that is not countable is **uncountable**. An example is the real interval \( (0,1) \).

An uncountable set is infinite. But, uncountable sets are not numerically equivalent to denumerable sets.

However, uncountable sets such as any open interval \( (a,b) \) are numerically equivalent to \( \real \), the set of reals.

With a sound understanding of **sets**, we continue our journey to mathematical expertise with an introduction to Relations.
Supplemented with numerous interactive demos, the article is self-contained and builds intuition about everything you need to know about **relations** to understand more advanced concepts like functions.

Let your friends, followers, and colleagues know about this resource you discovered.

Stay up to date with new material ** for free**.