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: AB=aAaBA \subseteq B = \forall a \in A \bullet a \in B.

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


An intersection represents the elements that are members of both sets: AB={xxAxB}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: AB={xxAxB}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\B={xxAxB}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: AB=(A\B)(B\A)=(AB)\(AB)A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B).


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


Given a set PXP \subseteq X, the complement of PP is the set of all elements of XX not in PP. This is expressed as P¯={xXxP}\overline{P} = \{ x \in X \mid x \notin P \}. Basically, if PXP \subseteq X, PP¯=XP \cup \overline{P} = X. Also note that P¯=X\P\overline{P} = X \setminus P. As an example, if X={1,2,3}X = \{ 1, 2, 3 \} and P={1,3}P = \{ 1, 3 \}, then P¯={2}\overline{P} = \{ 2 \}.

Empty Set

Power Set

A power set is the set of all possible subsets of a set. Its defined like this: (A)={xxA}\wp (A) = \{ x \mid x \subseteq A \}. Also denoted as A\mathbb{P}A. Note that the empty set is a member of all power sets: A(A)\forall A \bullet \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 AA has nn elements, then (A)\wp(A) has 2n2^{n} elements.


Finite Power Set

A set containing all the finite subsets of a set XX is denoted as 𝔽X\mathbb{F} X. If XX is a finite set, then 𝔽X=X\mathbb{F}X = \mathbb{P}X.

Multi Set

The multi-set (or bag) is the generalization of the concept of a set, where multiple ocurrences of an element are permitted. For example, [A,A,B][ A, A, B ] and [A,B][ 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, A, B ], AA has a multiplicity of 2, while BB 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 with different number of ocurrences for each of its elements.

A multi-set can be defined as a relation that maps the elements in the bag to positive integers denoting multiplicity.

For example, a multi-set of elements AA, BB, and CC, where multiplicity is 3, 1, and 2, respectively, can be denoted as {(A,3),(B,1),(C,2)}\{ (A, 3), (B, 1), (C, 2) \}. Elements that are not in the multi-set are left out, rather than mapped to a multiplicity of zero.

Augmented Set

Given set XX, the augment set of XX is XX^{\perp}, which is the union of the given set and the undefined element: XX \cup \perp.

Set Families

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


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

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



FF is a partition of AA if:

Uniqueness Operator

This operation allows us to refer to a single unique element of a set that matches the given constraints. Notice that the result is undefined if the given constraints don’t result in one and only one element.

Given a finite set of different natural numbers XX, we can obtain the largest one as: μxXyXxyx>y\mu x \in X \mid \forall y \in X \bullet x \neq y \implies x > y. Similarly, given the set PersonPerson, there is only one element that wrote The Lord of the Rings. Such element is: μpPersonThe Lord of the Ringsbooks(p)\mu p \in Person \mid \text{The Lord of the Rings} \in books(p).

We might also add a term part to map the resulting element. For example: John=μpPersonThe Lord of the Ringsbooks(p)firstname(p)John = \mu p \in Person \mid \text{The Lord of the Rings} \in books(p) \bullet firstname(p).


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

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

If a set comprehension has no term part, like {xX,yYP(x,y)}\{ x \in X, y \in Y \mid P(x, y) \}, then the type the elements in the result depends on the comprehension’s characteristic tuple. In this case, the set comprehension begins with xX,yYx \in X, y \in Y, so the characteristic tuple is (x,y)(x, y), which is of type X×YX \times Y.

Notice that the variables used in the characteristic tuple depend on the variables used inside the scope of the comprehension. If we have {pX,qYP(p,q)}\{ p \in X, q \in Y \mid P(p, q) \}, then the characteristic tuple would be the pair (p,q)(p, q).

Binary Relations

Sets of tuples where the elements in the tuple have a logical relationship. Tuples may be expressed as (x,y)(x, y), or as xyx \mapsto y, known as maplet notation. Given RA×BR \subseteq A \times B, we say AA and BB are the source and target sets of RR. If AA and BB 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: AB=(A×B)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×B={(a,b)aAbB}A \times B = \{ (a, b) \mid a \in A \land b \in B \}.

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

Also note the following equations with regards to \cap and \cup: (A×B)(C×D)=(AC)×(BD)(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) and (A×B)(C×D)(AC)×(BD)(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: AA×=\forall A \bullet A \times \emptyset = \emptyset.

Lifted Form

Given a relation PX×YP \subseteq X \times Y, the lifted form of PP is denoted P̊=P{}×Y\mathring{P} = P \cup \{ \perp \} \times Y^{\perp}. This is simply the original relation plus the association of the undefined element with all the elements of the augmented target.


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

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

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

Homogeneous (Binary) Relations

A binary relation RR over AA and BB where A=BA = B is called an homogenous relation, or an endorelation over AA.

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


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

Note that if RR 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)}R = \{ (a, a), (b, b), (b, c), (c, b), (c, c) \}. This equivalence relation tells us that a=aa = a, b=bb = b, c=cc = c, and b=cb = c. Therefore we have the following equivalence classes:

Given RA×AR \subseteq A \times A, we can obtain the equivalent class of xAx \in A as [x]R={yA(y,x)R}[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: xAx[x]R\forall x \in A \bullet x \in [x]_{R}.

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


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×YR = X \times Y and ZXZ \subseteq X, the domain restriction of RR by ZZ equals {(x,y)RxZ}\{ (x, y) \in R \mid x \in Z \}. This can be noted as ZRZ \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×YR = X \times Y and PYP \subseteq Y, the range restriction of RR by PP equals {(x,y)RyP}\{ (x, y) \in R \mid y \in P \}. This can be noted as RPR \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 ZZ by doing (X\Z)R(X \setminus Z) \triangleleft R, or we can exclude all pairs whose right-side element is in PP by doing R(Y\P)R \triangleright (Y \setminus P). These restrictions can also be expressed as ZRZ ⩤ R and RPR ⩥ P, respectively.

Relational Image

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


The closure of a relation RR is the smallest relation containing RR that satisfies a certain propery. For example, if RR is an homogeneous relation, then Rr=RiRR^{r} = R \cup i_{R} represents the reflexive closure of RR. If R=RrR = R^{r}, then we say RR is its own reflexive closure. Similarly, we can represent the symmetric closure of RR as Rs=RR1R^{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 RR is formally defined as R+={nn0Rn}R^{+} = \cup\{ n \in \mathbb{N} \mid n \geq 0 \bullet R^{n} \}, which is the transitive closure of RR, the smallest transitive relation containing RR.

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

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

Given a set, such as \mathbb{Z}, and an operation, such as multiplication, we say that a set is closed under an operation if for all elements xx and yy from the set, the result of the operation (such as x*yx * y), is already a member of the set.