Set Theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects

Basic Operations


A set is a subset of another set if all its elements are also member of the other set: \(A \subseteq B = \forall a \in A (a \in B)\).

A proper, or strict subset adds the additional requirement that the sets may not be equal: \(A \subset B = A \subseteq B \land A \neq B\).


An intersection represents the elements that are members of both sets: \(A \cap B = \{ x \mid x \in A \land x \in B \}\).


A union represents the elements that are members of at least one of the sets: \(A \cup B = \{ x \mid x \in A \lor x \in B \}\).


A difference represents the elements that are members of one set, but not of the other: \(A \setminus B = \{ x \mid x \in A \land x \notin B \}\).

Symmetric Difference

A symmetric difference represents the elements that are member of any of the sets, but not of both: \(A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B)\).


The number of elements in the set \(A\) is expressed as \(\vert A \vert\). For example, \(\vert\{ 1, 2, 3 \}\vert = 3\). There also exists the alternate notation \(\#A = \vert A \vert\).

Empty Set

Power Set

A power set is the set of all possible subsets of a set. Its defined like this: \(\wp (A) = \{ x \mid x \subseteq A \}\). Note that the empty set is a member of all power sets: \(\forall A (\emptyset \in \wp (A))\). Thus, the power set of the empty set is the set of the empty set: \(\wp (\emptyset) = \{ \emptyset \}\).

If a set \(A\) has \(n\) elements, then \(\wp(A)\) has \(2^{n}\) elements.


Multi Set

The multi-set is the generalization of the concept of a set, where multiple ocurrences of an element are permitted. For example, \([ A, A, B ]\) and \([ A, B ]\) (notice the square brackets) are equal sets, but are considered different multi-sets.

The multiplicity of an element is the number of times an element occurs in a multi-set. In the case of \([ A, A, B ]\), \(A\) has a multiplicity of 2, while \(B\) has a multiplicity of 1.

The multi-set cardinality consists of the number of elements in the multi-set, including duplicate ocurrences.

Notice that a set is considered a multi-set, and for any non-empty set there are infinite multi-sets wth different number of ocurrences for each of its elements.

A multi-set can also be defined as a set alongside a function (a set of ordered pairs) that maps from the elements of the set to positive integers (denoting multiplicity). For example, a multi-set of elements \(A\), \(B\), and \(C\), where multiplicity is 3, 1, and 2, respectively, can be denoted as \((\{ A, B, C \}, \{ (A, 3), (B, 1), (C, 2) \})\).

Set Families

Set families are sets of other sets. They may be indexed, such that \(F = \{ A_{i} \mid i \in I \}\), where each \(A_{i}\) is a set.


It can be defined as follows: \(\cap F = \{ x \mid \forall A \in F (x \in A) \} = \cap_{i \in I} A_{i}\). Note that this operation is undefined if \(F = \emptyset\).

It can be defined as follows: \(\cup F = \{ x \mid \exists A \in F (x \in A) \} = \cup_{i \in I} A_{i}\).



\(F\) is a partition of \(A\) if:


A set comprehension is a handy mathematical notation to build sets based on arbitrarily complex expressions. The general form is \(\{ x \in X \mid P(x) \}\), which defines the set of all elements of \(X\) where \(P\) holds.

We can add a term part to map the elements in the set. For example, given \(address(p)\) returns the address of person \(p\), \(\{ p \in People \mid male(p) \circ address(p) \}\) is the set of addresses of all the male people.

Binary Relations

Sets of tuples where the elements in the tuple have a logical relationship. Given \(R \subseteq A \times B\), we say \(A\) and \(B\) are the source and target sets of \(R\). If \(A\) and \(B\) are of the same type, then the relation is homogeneous; if they are different, the relation is heterogeneous.

The powerset of a binary relation can be expressed with a double-headed arrow: \(A \leftrightarrow B = \wp (A \times B)\).

Cartesian Product

This operation can create binary relations from two sets consisting of all the possible tuple combinations: \(A \times B = \{ (a, b) \mid a \in A \land b \in B \}\).

The cartesian product is distributive over \(\cap\) and \(\cup\): \(A \times (B \cap C) = (A \times B) \cap (A \times C)\) and \(A \times (B \cup C) = (A \times B) \cup (A \times C)\).

Also note the following equations with regards to \(\cap\) and \(\cup\): \((A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)\) and \((A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)\).

With regards to the empty set, a cartesian product of the empty set and any set is equal to the empty set: \(\forall A (A \times \emptyset = \emptyset)\).


Given \(R \subseteq (A \times B)\), a relation from \(A\) to \(B\):

Note the following equation about inversing a composition: \((S \circ R)^{-1} = R^{-1} \circ S^{-1} \).

If a certain binary relation is homogeneous, then \(R^{n}\) represents the result of composing \(R\) with itself \(n\) number of times. For example, \(R^{3} = R \circ R \circ R\).

Homogeneous (Binary) Relations

A binary relation \(R\) over \(A\) and \(B\) where \(A = B\) is called an homogenous relation, or an endorelation over \(A\).

The identity binary relation on \(A\) is denoted as \(i_{A} = \{ (a, a) \mid a \in A \}\).


Homogenous relations may have one or more of the following properties:

Note that if \(R\) is asymmetric, then its also antisymmetric.

Equivalence Relations

Equivalence relations are binary relations that are also reflexive, symmetric, and transitive. They can be used to partition a set into equivalence classes. In this context, an ordered pair means that the pair of elements should be considered “equivalent.”

Consider \(R = \{ (a, a), (b, b), (b, c), (c, b), (c, c) \} \). This equivalence relation tells us that \(a = a\), \(b = b\), \(c = c\), and \(b = c\). Therefore we have the following equivalence classes:

Given \(R \subseteq A \times A\), we can obtain the equivalent class of \(x \in A\) as \([x]_{R} = \{ y \in A \mid (y, x) \in R \}\).

Notice an element is always in the set of its equivalent classes, since an element is always equal to itself: \(\forall x \in A (x \in [x]_{R})\).

The set of all equivalence classes of all the elements of \(A\) is called “\(A\) module \(R\)”, denoted \(A \mathbin{/} R = \{ [x]_R \mid x \in A \}\). The resulting set family is always a partition of \(A\).


A binary relation can be restricted on the domain, or on the range.

A restriction on the domain means that we only consider pairs where the left-side element is a member of a certain set. Given \(R = X \times Y\) and \(Z \subseteq X\), the domain restriction of \(R\) by \(Z\) equals \(\{ (x, y) \in R \mid x \in Z \}\). This can be noted as \(Z \triangleleft R\).

Similarly, a restriction on the range means that we only consider pairs where the right-side element is a member of a certain set. Given \(R = X \times Y\) and \(P \subseteq Y\), the range restriction of \(R\) by \(P\) equals \(\{ (x, y) \in R \mid y \in P \}\). This can be noted as \(R \triangleright P\).

We can use restrictions to exclude a list of pairs from a binary relation, which is called domain or range substraction (or anti-restriction). Following the above examples, we can exclude all pairs whose left-side element is in \(Z\) by doing \((X \setminus Z) \triangleleft R\), or we can exclude all pairs whose right-side element is in \(P\) by doing \(R \triangleright (Y \setminus P)\). These restrictions can also be expressed as \(Z ⩤ R\) and \(R ⩥ P\), respectively.

Relational Image

The relation image of a binary relation \(R \subseteq A \times B\) by a set \(P \subseteq A\) is the range of the domain restriction of \(R\) by \(P\): \(R(\vert P \vert) = range(P \triangleleft R)\). In other words, the relation image would be the set of all the results of function \(R\) where the argument is a subset of \(P\).


The closure of a relation \(R\) is the smallest relation containing \(R\) that satisfies a certain propery. For example, if \(R\) is an homogeneous relation, then \(R^{r} = R \cup i_{R}\) represents the reflexive closure of \(R\). If \(R = R^{r}\), then we say \(R\) is its own reflexive closure. Similarly, we can represent the symmetric closure of \(R\) as \(R^{s} = R \cup R^{-1}\)

The transitive closure of an homogeneous relation is determined by composing the relation with itself enough times until the final relation stops growing. The union of all finite iterations of \(R\) is formally defined as \(R^{+} = \cup\{ n \in \mathbb{N} \mid n \geq 0 \circ R^{n} \}\), which is the transitive closure of \(R\), the smallest transitive relation containing \(R\).

For example, consider \(R = \{ (a, b), (b, c), (c, d) \}\). \(R^{1} = R\), \(R^{2} = \{ (a, b), (b, c), (b, d), (a, c), (c, d) \}\), and \(R^{3} = \{ (a, b), (b, c), (a, d), (b, d), (a, c), (c, d) \}\). But at this point, \(R^{4} = R^{3}\), \(R^{5} = R^{3}\), and so on. Therefore, \(R^{+} = R^{3}\), which is the transitive closure of \(R\).

Finally, the reflexive transitive closure of an homogeneous relation \(R\) is defined as \(R^{*} = R^{+} \cup i_{R}\).