Relations and Order

NBG Set Theory and Binary Relation

In this chapter, we will discuss further topics on set theory, or more specifically, relations. With set as tool, we can categorize things and try to build connections between them, like defining a function from a preimage to an image. Relation is a superset , i.e., generalization of function, which is crucial to topics that we will discuss later in this chapter.

In real life, relation is referred to as some connections between one person or one group of people to the other.

1. Imagine a list of students and their grades in a class. Each student (let’s say, by their student ID) is linked to a specific grade. This “student-to-grade” pairing is an example of a functional relation, because every student has one and only one grade assigned.

2. Consider the relationship “has the same birthday as” among people. If person A has the same birthday as person B, and person B has the same birthday as person C, then person A also has the same birthday as person C. This relationship is an equivalence relation because it’s reflexive (everyone has the same birthday as themselves), symmetric (if A shares a birthday with B, then B shares a birthday with A), and transitive (if A shares a birthday with B, and B with C, then A shares a birthday with C).

3. Think about the books on a shelf organized by height. Each book can be considered as “shorter than or equal to” the book next to it if you move from left to right. This arrangement demonstrates an order relation because it’s reflexive (each book is the same height as itself), antisymmetric (if one book is both taller and shorter than another, they must be the same book), and transitive (if one book is shorter than a second, and the second is shorter than a third, then the first book is shorter than the third).

The notion is still quite similar in the context of mathematics. From many examples we can see this. Like all the mathematical operations we have defined, the mapping in a function, congruence… To sum up, relation is am abstract topic, yet not hard to understand, since it can be related to the material world easily.

Class

Additionally, we introduce a new concept related to set to explain what is relation. The set theory we discussed in the first part of this book is called Naive Set Theory, which Is actually not the modern set theory. In many aspects, it is not reliable and causes a lot of issues. A very famous example is Russell’s Paradox initiated by the British Philosopher and Mathematician.

Russell’s Paradox illustrates a significant problem in the naive set theory, which assumed sets could include themselves. The paradox is encapsulated in whether the “set of all sets that do not contain themselves” contains itself. If it contains itself, it contradicts its defining property. Conversely, if it does not contain itself, then by definition, it must contain itself. This dilemma indicated the limitations of the naive set theory approach, leading to contradictions. To address these issues, the concept of classes was introduced in NBG Set Theory (von Neumann-Bernays-Gödel set theory).

Classes allow for the conceptualization of collections too large or abstract to be considered as sets, thereby circumventing the paradoxes associated with a more naive interpretation of set theory.

Remark

An interesting fact is that the von Neumann here is exactly John von Neumann, who initiated von Neumann Architecture for computer. It seems that a great Computer Scientist is always also a great Mathematician.

Definition

A class is a collection of objects that are grouped together based on a shared property. Classes differ from sets in that they can represent collections of any size, including those too large to be considered as sets, such as the “class of all sets”. This concept is essential for avoiding paradoxes in set theory, allowing the discussion of large and abstract collections that cannot otherwise be accommodated within the framework of sets.

In NBG set theory, a class is a collection of sets that can be unambiguously defined by a property that all its members share. Formally, a class $C$ is defined as: $C = \{ x : P(x) \}$ where $P(x)$ is a property or predicate formulable in the language of set theory, applicable to sets $x$. If a class is not a set, it is called a proper class. For example, the class of all sets, which cannot be a member of any class, is a proper class.

Distinguishing set and class in NBG and Naive theory

Naive set theory operates under the general principle that any well-defined collection of objects forms a set. This unrestricted comprehension leads to paradoxes such as Russell’s paradox. In contrast, NBG set theory distinguishes between sets, which are elements of other classes, and classes, which may not necessarily be elements of other classes.

A key distinction in NBG set theory is that a set is a class that is an element of another class, while a proper class, such as the class of all sets, cannot be an element of any class. This distinction helps avoid the paradoxes typical of naive set theory by restricting certain collections from being members of other collections.

Furthermore, in NBG, sets form a subclass of classes, meaning all sets are classes but not all classes are sets. This hierarchical structure allows for a more rigorous foundation for set theory, accommodating larger collections like the class of all sets or the class of all ordinal numbers, which themselves cannot be sets due to their extensive size. We also introduce some of the axioms that is really important for the content here, they are easy to understand, but are important prerequisite for our further discussion.

Axiom

Two classes are equal if and only if they have the same elements. Formally, the axiom is expressed as: $\forall A \forall B (\forall x (x \in A \leftrightarrow x \in B) \rightarrow A = B)$

The other Axiom is on creating new classes.

Axiom

For each open sentence $P(x)$ there exists a class which consists precisely of those sets which satisfy the condition $P(x)$.

The class whose existence is postulated by the Axiom is denoted by $\{x : P(x)\}$; thus $\{x : P(x)\}$ is a term of the theory NBG and the assertion $u \in \{x : P(x)\}$ is true if and only if $u$ is a set and $P(u)$ is true.

Properties and Operations of Class

Since the definition of Class and set are related, there are a lot of overlap in their properties. The union and intersection of two classes are defined in exactly the same way as the union and intersection of two sets in naïve set theory: if $A$ and $B$ are classes, then $\begin{aligned} A \cup B &= \{x : (x \in A) \vee (x \in B)\}, \\ A \cap B &= \{x : (x \in A) \wedge (x \in B)\}. \end{aligned}$ So a set $x$ is a member of $A \cup B$ if and only if it is a member of either $A$ or $B$ (or both); $x$ is a member of $A \cap B$ if and only if it is a member of both $A$ and $B$.

The usual properties of these unions and intersections are established as in naïve set theory. Namely, we have the properties known as idempotence, $\begin{aligned} \forall X(X \cup X = X), \quad \forall X(X \cap X = X), \end{aligned}$ associativity, $\begin{aligned} \forall X \forall Y \forall Z (X \cup (Y \cup Z) = (X \cup Y) \cup Z), \\ \forall X \forall Y \forall Z (X \cap (Y \cap Z) = (X \cap Y) \cap Z), \end{aligned}$ commutativity, $\begin{aligned} \forall X \forall Y (X \cup Y = Y \cup X), \quad \forall X \forall Y (X \cap Y = Y \cap X), \end{aligned}$ and distributivity, $\begin{aligned} \forall X \forall Y \forall Z (X \cup (Y \cap Z) = (X \cup Y) \cap (X \cup Z)), \\ \forall X \forall Y \forall Z (X \cap (Y \cup Z) = (X \cap Y) \cup (X \cap Z)). \end{aligned}$

Definition

We write $x \notin y$ as an abbreviation for $\neg(x \in y)$. Then for each class $A$ we define the complement of $A$ to be the class $\begin{aligned} \sim A = \{x : x \notin A\}. \end{aligned}$

Definition

For two classes $A$ and $B$, the difference $A~B$ is defined as: $A\sim B \text{ or } A-B=\{x:(x\in A)\land(x\not\in B)\}=A\cap(\thicksim B).$

Also, note that double negation and De Morgan’s Law also work for class.

As what we have discussed in set theory that there exist some empty sets, we also have null class and universe class.

Definition

Empty class $\emptyset$ and universe class $V$ are defined by $\emptyset=\{x:x\neq x\}\ \ \ V=\{x:x=x\}.$

Classes also have their exclusive operations, including intersection and union.

Definition

Let $A$ be a class; the union and intersection of the class $A$ are the classes $\begin{array}{rcl}\bigcup A&=&\{x:(\exists y)((y\in A)\land(x\in y))\},\\ \bigcap A&=&\{x:(\forall y)((y\in A)\to (x\in y))\}\end{array}$ Where $x$ is a set and $y$ is a class.

Thus a class $C$ belongs to $\bigcup A$ if and only if $C$ is a set and $C$ belongs to at least one of the members of $A;C$ belongs to $\bigcap A$ if and only if $C$ is a set and $C$ belongs to every member of $A.$

The definition is quite different from intersection and union of sets, as class is a generalization of set from higher level abstraction. Also, the intersection and union for sets are binary operations, while unary for one class.

Below is a brief comparison.

Set Union and Intersection:

1. For two sets $A$ and $B$, their union $A \cup B$ is the set of all elements that belong to either $A$ or $B$. Formally: $A \cup B = \{x : x \in A \lor x \in B\}$.

2. For two sets $A$ and $B$, their intersection $A \cap B$ is the set of all elements that belong to both $A$ and $B$. Formally: $A \cap B = \{x : x \in A \land x \in B\}$.

Class Union and Intersection:

1. For a class $A$, the class union $\bigcup A$ is the set of all elements $x$ such that there exists a class $y$, where $y$ is a member of $A$, and $x$ is an element of $y$. Formally: $\bigcup A = \{x : (\exists y)((y \in A) \land (x \in y))\}$.

2. For a class $A$, the class intersection $\bigcap A$ is the set of all elements $x$ such that for every class $y$, if $y$ is a member of $A$, then $x$ is an element of $y$. Formally: $\bigcap A = \{x : (\forall y)((y \in A) \to (x \in y))\}$.

Comparison:

1. Set union and intersection operate on two sets, while class union and intersection operate on all member sets of a class.

2. Set union includes elements that are in either $A$ or $B$, while class union includes elements that are in at least one member of $A$.

3. Set intersection includes elements that are in both $A$ and $B$, while class intersection includes elements that are in all members of $A$.

4. The result of set union and intersection is always a set, while the result of class union and intersection is not necessarily a set , but more likely a class that contains sets.

By comparing these concepts, we can see that class union and intersection are generalizations of set operations at a higher level of abstraction. They allow us to perform operations on the member sets of a class to obtain new sets, which is particularly useful when studying advanced topics in mathematical foundations and set theory.

There are several lemmas related to intersection and union of class.

Lemma

$\bigcap \emptyset= V$ and $\bigcup \emptyset= \emptyset.$

Proof

Let $C$ be a class. Then we have $C \in \bigcap \emptyset \iff C \text{ is a set and } C \text{ belongs to every member of } \emptyset$ Since $\emptyset$ does not literally have any member. $\iff C \text{ is a set}$ Any set is a member of universe class $\iff C \in V.$ Thus $\bigcap \emptyset = V$ by the Axiom of Extensionality.

Again let $C$ be a class. Then $C \in \bigcup \emptyset \iff C \text{ is a set and there is a member } x \text{ of } \emptyset \text{ such that } C \in x$ $\iff C \in \emptyset$ (since $\emptyset$ has no members).

So $\bigcup \emptyset = \emptyset$ by the Axiom of Extensionality.

The inclusive relation of class is very similar to set.

Definition

If $A$ and $B$ are classes such that every member of $A$ is also a member of $B$, i.e., such that we have $\forall x ((x \in A) \to (x \in B)),$ we say that $A$ is included in $B$, $B$ includes $A$ or $A$ is a subclass of $B$, and we write $A \subseteq B$ or $B \supseteq A$. (If $A$ is a set and $A \subseteq B$ we say that $A$ is a subset of $B$.) If $A \subseteq B$ and there is at least one set $b$ such that $b \in B$ but $b \not\in A$, we say that $A$ is properly included in $B$, $B$ properly includes $A$ or $A$ is a proper subclass of $B$, and we write $A \subset B$ or $B \supset A$.

We can also extend power set to power class. For every class $A$ we define the power class $P(A)$ of $A$ to be the class of all subsets of $A$, i.e., $P(A) = \{x : x \subseteq A\}$. This brings us to another axiom in NBG set theory.

Axiom

For every set $x$ there exists a set $y$ such that $u \in y$ if and only if $u \subseteq x$.

The Power Set Axiom thus asserts that every subclass $u$ of a set $x$ is actually a set (since it is an element of the set $y$ whose existence is asserted by the axiom) and furthermore that the power class $P(x)$ of a set $x$ is also a set (and so is usually referred to as the power set of $x$).

The rest of the axioms are as follows.

Axiom

For all sets $x$ and $y$ the class $\{z : (z = x) \vee (z = y)\}$ is a set.

The set $\{z : (z = x) \vee (z = y)\}$ is denoted by $\{x, y\}$ and such a set is called an unordered pair. If $x = y$ the unordered pair $\{x, y\}$ is denoted by $\{x\}$ and is called singleton $x$.

Remark

In set theory, an unordered pair refers to a collection of two elements in which the sequence of the elements does not matter. This is represented as $\{a, b\}$, indicating a set that contains exactly two distinct elements $a$ and $b$. The fundamental property of unordered pairs is that $\{a, b\} = \{b, a\}$, asserting that the order of elements is immaterial.

The concept of an unordered pair is not limited to sets; it extends to classes in certain set theories that distinguish between sets and proper classes. While sets are collections of elements that themselves can be elements of other sets, proper classes are collections too large to be sets and hence cannot be elements of other collections. Nonetheless, the notion of grouping two objects into an unordered pair applies analogously, symbolizing the collection of those objects without regard to order.

Axiom

For every set $x$ the class $\bigcup x$ is a set.

We can also extend Cartesian Product to class. Let $a$ and $b$ be sets. Then the set $\{\{a\},\{a,b\}\}$ is denoted by $(a,b)$ and is called the ordered pair with first coordinate $a$ and second coordinate $b$. Lét $A$ and $B$ be classes; then the Cartesian product of $A$ and $B$ is the $c$lass

$A\times B=\{t:(\exists x)(\exists y)((x\in A)\land(y\in B)\land(t=(x,y)))\},$

i.e. $A\times B$ is the class of all ordered pairs with first coordinate in $A$ and second coordinate in $B.$

If $P(x,y)$ is an open sentence involving the free variables $x$ and $y$ we shall allow ourselves to write

$\{(x,y):P(x,y)\}$

as an abbreviation for

$\{t:(\exists x)(\exists y)((t=(x,y))\land P(x,y))\}.$

So we can abbreviate the definition of $A\times B$ to

$A\times B=\{(x,y):(x\in A)\wedge(y\in B)\}.$

Binary Relations, Composition and Inverse

In mathematics, the most fundamental and ubiquitous type of relation is the binary relation. This term refers to a relationship between two objects or sets. We understand that a ‘set’ may encompass any concept, not solely in the mathematical sense but also in a material one. Relations may exist objectively between certain objects and not at all for others. Similarly, objects or sets of objects, which exist objectively, hold the potential for an infinite number of relationships with one another. This perspective can seem philosophically abstract, positing that any scenario is conceivable. However, we can convey this more clearly. Recall our discussion of the Cartesian product as a set extension, where we consider two sets, $A$ and $B$. These sets could represent any discernible entity or indiscernible concept. Theoretically, there could be countless relationships among all elements of these sets, and the capacity of two sets to form a Cartesian product is indicative of a general type of relationship. Consequently, the elements of the power set $P(A \times B)$ exemplify all possible cases of a certain kind of relationship.

A vivid mathematical example is the definition of Euclidean spaces, where an infinite number of subspaces can be defined, each representing a unique binary relation within the space.

We first introduce the definition of a binary relation in terms of sets.

Definition

A Binary Relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product $A \times B$. For elements $a \in A$ and $b \in B$, if the pair $(a, b)$ belongs to the subset $R$, then we say $a$ is related to $b$ by the relation $R$, denoted as $aRb$, whose negation is $a\not R b$.

In last section, we introduced the higher abstraction of sets, which is class. Classes also have Cartesian product,thus, we can give a general definition to all relations using class.

Definition

A relation is a class of ordered pairs.

Let $R$ be a relation. We define the domain and range of $R$ to be the classes Dom $R$ and Range $R$ given by $\begin{array}{rcl}\text{Dom }R&=&\{x:(\exists y)((x,y)\in R)\},\\\text{Range }R&=&\{y:(\exists x)((x,y)\in R)\}.\end{array}$ If $R$ is a relation and $(x,y)\in R$, we say that $x$ is $R$-related to $y$ and that $y$ is an $R$-relative of $x$. Thus Dom $R$ is the class of all sets that have $R$-relatives, and Range $R$ is the class of all sets that are $R$-relatives.

Now we look into several concrete examples of relation.

Example

Consider the set of all points on a plane. The relation defined by the equation of a circle, $x^2 + y^2 = r^2$, includes all points $(x, y)$ that satisfy this equation. This relation is not a function because, for most values of $x$, there are two possible values of $y$ that satisfy the equation, one positive and one negative (except for the points where $x = \pm r$, where there is only one value of $y$).

In contrast, a function would allow each $x$ to be associated with exactly one $y$. For instance, the square function $y = x^2$ is a function because each value of $x$ corresponds to exactly one value of $y$.

In the figure we have defined a circle and a quadratic function, clearly we see that a function can never have two $y$ value for one $x$, while this is possible for the circle.

Figure pending: Visual Comparison of a Relation and a Function

Example

Let A be the set {1,2,3,4}. Which ordered pairs are in the relation $R=\{(a,b)\mid a$ divides $b\}?$

Solution: Because $(a,b)$ is in R if and only if $a$ and $b$ are positive integers not exceeding 4 such that $a$ divides $b$,we see that $R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}.$

Figure pending: R = {(a, b) ∣ a divides b}

This relation also differs from function, since for member of $a$, it is possible to map to multiple members in $b$.

Definition

A relation $R$ is said to be functional if each element of its domain has exactly one $R$-relative; a functional relation is also called a function. If $R$ is a functional relation then for each element $a$ of its domain we denote the unique $R$-relative of $a$ by $R(a).$

This leads us to the next axiom of NBG theory.

Axiom

For every functional relation $R$, if the domain of $R$ is a set then the range of $R$ is also a set.

Mapping, Composition, and Inverse

In naive set theory and function in part 1 of the book, we gave a rough definitions to mappings. With class, we can make it more concrete.

Definition

A mapping is an ordered pair $((A,B),R)$ where $A$ and $B$ are sets and $R$ is a functional relation between $A$ and $B$ such that Dom $R=A.$ If $f= ( ( A, B) , R)$ is a mapping we say that $f$ is a mapping from $A$ to $B;$ we call $A$ the domain of $f,B$ the codomain of $f$ and $R$ the graph of $f$. If $f$ is a mapping with domain $A$ and codomain $B$ we often write $f:A\to B.$ If $a$ is any element of the set $A$ then the set $R^{\to}(\{a\})$ consists of a single element of $B$ which we denote by $f(a);$ we call it the image of $a\textbf{ under }f$ or the value of $f\textbf{ at }a.$

It is clear from the definition of the term “mapping” that in order to describe a mapping $f$ we must give the domain $A$ and codomain $B$ of $f$ and also, for each element $a$ of the domain we must describe the unique element $b_a$ of the codomain such that $(a,b_a)$ belongs to the graph of $f$, i.e. we must describe for each element $a$ of $A$ its image under $f$ in $B.$

Let $f= ( ( A, B) , R)$ be a mapping from $A$ to $B$. For each subset $X$ of $A$ we denote the subset $R^{\to}(X)$ of $B$ by $f^{\to}(X);$ in particular, if $a$ is any element of $A$ we have $f^{\to}(\{a\})=\{f(a)\}.$ For each subset $Y$ of $B$ we denote the subset $R^{\leftarrow }( Y)$ of $A$ by $f^{\leftarrow }( Y) .$

Let $f=((A,B),R)$ be a mapping from $A$ to $B;\operatorname*{let}A_1$ be a subset of $A.$ Then the restriction of $f$ to $A_1$ is the mapping f\mid A_1= \left((A_1,B\),R\cap(A_1\times B)\right).

Earlier, we discussed composition and inverse of function. Now that we have known that function is a kind of relation, can we compose or inverse all other relations? Naturally the answer is yes.

Definition

Let $f= ( ( A, B) , R)$ be a mapping. Then $f$ is said to be surjective or to be a surjection if we have Range $R$ $= B,$i.e. if every element of $B$ is the image under $f$ of at least one element of $A.$

Next, $f$ is injective if the inverse relation $R^{-1}$ is functional. Equivalently, each element of the range of $R$ is the image under $f$ of exactly one element of $A$. In symbols, whenever $f(a_1)=f(a_2)$ for $a_1,a_2\in A$, we have $a_1=a_2$.

The mapping $f$ is said to be bijective or to be a bijection if it is both injective and surjective. If $A$ and $B$ are sets we say that $A\textbf{is}$ equipotent to $B$ or that $A\textbf{is equinumerous with }B$ if there exists a bijective mapping from $A$ to $B.$

Let $f=((A,B),R)$ be a mapping. Then $((B,A),R^{-1})$ is a mapping if and only if $f$ is bijective; in this case we write $((B,A),R^{-1})=f^{-1}$ and call $f^{-1}$ the inverse mapping of $f.$ Clearly $f^{-1}$ is a bijection from $B$ to $A$ with inverse $f.$

Here are some examples of special mappings.

Example

A function $f: A \to B$ is surjective if for every element $y$ in $B$, there is at least one element $x$ in $A$ such that $f(x) = y$. For instance, let $A = \{1, 2, 3\}$ and $B = \{a, b\}$. Define $f$ by $f(1) = a$, $f(2) = a$, and $f(3) = b$. This function is surjective because every element of $B$ is the image of at least one element of $A$.

Example

A function $f: A \to B$ is injective if no two different elements in $A$ map to the same element in $B$. For example, let $A = \{1, 2, 3\}$ and $B = \{a, b, c, d\}$. Define $f$ by $f(1) = a$, $f(2) = b$, and $f(3) = c$. This function is injective because each element of $A$ maps to a unique element of $B$.

Example

A function $f: A \to B$ is bijective if it is both injective and surjective. For instance, let $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$. Define $f$ by $f(1) = a$, $f(2) = b$, and $f(3) = c$. This function is bijective, making $A$ and $B$ equinumerous.

Example

If $f$ is a bijective function from $A$ to $B$, then the inverse $f^{-1}$ is a function from $B$ to $A$ that reverses the mapping of $f$. Using the bijective function $f$ from the previous example, we define $f^{-1}$ by $f^{-1}(a) = 1$, $f^{-1}(b) = 2$, and $f^{-1}(c) = 3$.

Definition

If $R$ and $S$ are relations, the composition of $R$ and $S$ is the relation $S\circ R$ given by $S\circ R=\{(x,z):(\exists y)(((x,y)\in R)\wedge((y,z)\in S))\}.$ If $R$ is a relation between $A$ and $B$ and $S$ is a relation between $B$ and $C$ then clearly $S\circ R$ is a relation between $A$ and $C$, and we have $\operatorname{Dom}\left(S\circ R\right)\subseteq\operatorname{Dom}R$ and Range $(S\circ R)\subseteq\operatorname{Range}S.$

The idea of composition also works for mappings.

Definition

Let $f= ( ( A, B) , R)$ and $g= ( ( B, C) , S)$ be mappings. Then clearly $((A,C),S\circ R)$ is also a mapping, which we denote by $g\circ f$ and call the composition or composed mapping of $f$ and $g$. For each element $a$ of $A$ we have $( g\circ f) ( a) = g( f( a) ).$

Remark

The other equivalent definition is that Let $R$ be a relation from a set $A$ to a set $B$ and S a relation from $B$ to a set $C$. The $composite$ of $R$ and S is the relation consisting of ordered pairs $(a,c)$, where $a\in A, c\in C$ , and for which there exists an element $b\in B$ such that $( a, b) \in R$ and $( b, c) \in S.$ We denote the composite of $R$ and $S$ by $S\circ R.$

Similarly, we can define inverse relation.

Definition

If $A$ and $B$ are classes then a relation between $A\textbf{ and }B$ is a subclass of $A\times B$, i.e. a relation $R$ such that Dom $R\subseteq A$ and Range $R\subseteq B.$ A relation on a class $A$ is a subclass of $A\times A.$

If $R$ is a relation, the inverse of $R$ is the relation $R^{-1}$ given by $R^{-1}=\{(x,y):(y,x)\in R\}.$ If $R$ is a relation between $A$ and $B$ then $R^{-1}$ is a relation between $B$ and $A;$ clearly Dom $R^{-1}=\operatorname{Range}R$ and Range $R^{-1}=\operatorname{Dom}R.$

Let $R$ be a relation, $A$ any class. Then the image of $A\textbf{ under }R$ is the class consisting of all $R$-relatives of all members of $A.$ We denote this class by $R^{\to}(A).$ Thus $R^{\to}(A)=\{y:(\exists x)((x\in A)\land((x,y)\in R))\}.$ Again let $R$ be a relation and $\ker B$ be any class. Then the inverse image of $B$ under $R$ is the class $( R^{- 1}) ^{\to }( B) ,$ which we write $R^{\leftarrow}( B) .$ Thus $\begin{aligned}R^{\leftarrow}(B)=\{x:(\exists y)((y\in B)\land((x,y)\in R))\}.\end{aligned}$ With functional relation and mapping, we can define a more specific relation, which very special and practical.

Definition

Let $A$ be any set; let $D_A=\{x:(\exists a)((a\in A)\land(x=(a,a)))\}$ (we call $D_A$ the diagonal of $A\times A).$ Then $D_A$ is a functional relation between $A$ and $A$ with domain $A.$ The mapping $I_A=((A,A),D_A)$ from $A$ to $A$ is called the identity mapping of $A.$ Clearly we have $I_{A}(a)=a$ for each element $a$ of $A.$

Example

The identity mapping $I_A$ for a set $A$ is a function that maps every element to itself. Here are some examples of identity mappings on various sets:

• Let $B = \{x \in \mathbb{R} \mid -1 \leq x \leq 1\}$. The identity mapping on $B$ is $I_B : B \to B$ where $I_B(x) = x$ for all $x \in B$.

• Let $C = \{\text{apple}, \text{banana}, \text{cherry}\}$. The identity mapping on $C$ is $I_C : C \to C$ where $I_C(\text{fruit}) = \text{fruit}$ for each fruit in set $C$.

• Let $D = \mathbb{Z}$. The identity mapping on $D$ is $I_D : \mathbb{Z} \to \mathbb{Z}$ where $I_D(n) = n$ for all $n \in \mathbb{Z}$.

The diagonal for each of these sets would be as follows:

• The diagonal of $B$, $D_B$, would be the set of all ordered pairs $(x, x)$ such that $x \in B$.

• The diagonal of $C$, $D_C$, would be the set $\{(\text{apple}, \text{apple}), (\text{banana}, \text{banana}), (\text{cherry}, \text{cherry})\}$.

• The diagonal of $D$, $D_D$, would be the set of all ordered pairs $(n, n)$ such that $n \in \mathbb{Z}$.

In all these cases, the identity mapping illustrates the concept of a function where the input is the same as the output for each element of the set.

Families of Sets

In part 1, we discussed sequence. Sequence is defined (see definition def_sequence) by a relation between index and a mathematical expression related to the index, and commonly the index $i$ has $i\in \mathbb{N}$. Sequence is actually a special family of set.

Definition

Let $I$ and $A$ be classes, and $F$ is a functional relation between $I$ and $A$. Then $F$ is sometimes called a family of elements of $A$ indexed by $I$ (or with $I\textbf{ as index class})$ and we write $(F(i))_{i\in I}$ instead of $F$. In particular, if $E$ is a set then a family of elements of $\mathbf{P}(E)$ is called a family of subsets of $E$ indexed by $I.$ If $F$ is such a family and we write $X_i=F(i)$ for each element $i$ in $I$ then we denote the family $F$ by$\left ( X_i\right ) _{i\in I}.$

If $X$ is a set of subsets of a set $E$ then the diagonal $D_X$ is a family of subsets of $E$ which may sometimes be denoted by $(x)_{x\in X}.$

Let $F= ( X_{i}) _{i\in I}$ be a family of subsets of a set $E.$ We define the union of the family to be $\bigcup_{i\in I}X_i=\{x:(\exists i)((i\in I)\land(x\in X_i))\}.$ Thus $x$ belongs to the union of the family $(X_i)_{i\in I}$ if and only if it belongs to at least one of the sets $X_i$ with $i$ in $I.$ Of course if $X$ is a set of subsets of $E$ the union of the corresponding family $D_X$ coincides with the union of the set $X$ as previously defined: $\bigcup_{x\in X}x=\bigcup X.$

Again let $(X_i)_{i\in I}$ be a family of subsets of a set $E.$ The intersection of this family is defined to be $\bigcap_{i\in I}X_i=\{x:(x\in E)\land(\forall i)((i\in I)\Longrightarrow(x\in X_i))\}.$ So $x$ belongs to the intersection of the family $(X_i)_{i\in I}$ if and only if it belongs to all the sets $X_i$ with $i$ in $I.$

We notice that if $I$ is empty then we have $\bigcap_{i\in I}X_i=E.$ If X i a non-empty set of subsets of $E$ the intersection of the corresponding family $D_X$ coincides with the intersection of the set $X$ as previously defined${: }\bigcap _{x\in X}x= \bigcap X.$

Example

Consider the set $E$ and a family of its subsets $(X_i)_{i \in I}$, where $I = \{1, 2, 3\}$ and

• $X_1 = \{a, b\}$

• $X_2 = \{b, c\}$

• $X_3 = \{a, c, d\}$

The union of the family $(X_i)_{i \in I}$ is the set of elements that are in at least one of the sets $X_i$: $\bigcup_{i \in I} X_i = X_1 \cup X_2 \cup X_3 = \{a, b, c, d\}$

The intersection of the family $(X_i)_{i \in I}$ is the set of elements that are in every one of the sets $X_i$: $\bigcap_{i \in I} X_i = X_1 \cap X_2 \cap X_3 = \emptyset$

Definition

Let $E$ be a set. A sequence in $E$ is a function from the set of natural numbers $\mathbb{N}$ to $E$. The sequence can be represented as a family of sets $(x_i)_{i \in \mathbb{N}}$, where each $x_i$ is an element of $E$, and $i$ is the index representing the position of the element in the sequence.

The $n$-th term of the sequence is denoted by $x_n$, and the sequence itself can be written as $(x_n)_{n=1}^{\infty}$, which is the family of elements of $E$ indexed by $\mathbb{N}$.

Let $(X_i)_{i\in I}$ be a family of sets with index set $I.$ Let $X=\bigcup_{i\in I}X_i.$ Then the product of the family $(X_i)_{i\in I}$ is the set

\prod_{i\in I}X_i=\{f:(f\in\operatorname{Map}(I,X))\wedge(\forall i)((i\in I)\Longrightarrow(f(i)\in X_i))\}.$$ If we write $f(i)=x_i$ for each index $i$ in $I$ it is sometimes helpful to denote the element $f$ of $\prod_{i\in I}X_i$ by $\prod_{i\in I}x_i.$ For each index $j$ in $I$ we define a mapping $\pi_j$ from $\prod_{i\in I}X_i$ to $X_j$ by setting $$\pi_j(f)=f(j)\text{ for every }f\mathrm{~in~}\prod_{i\in I}X_i.

The mapping $\pi_j$ is called the $j$ -th projection mapping from $\prod_{i\in I}X_i.$

Example

Consider two sets $X_1 = \{a, b\}$ and $X_2 = \{1, 2\}$. The index set is $I = \{1, 2\}$. The product of the family of sets $(X_i)_{i \in I}$, which is $X_1 \times X_2$, consists of all ordered pairs where the first element is from $X_1$ and the second is from $X_2$. Thus, the product is: $\prod_{i \in I} X_i = X_1 \times X_2 = \{(a, 1), (a, 2), (b, 1), (b, 2)\}$

Each ordered pair represents a function $f$ mapping $I$ to the union of $X_1$ and $X_2$. For instance, one such function corresponding to the ordered pair $(a, 1)$ is defined by: $f(1) = a, \quad f(2) = 1$

Projection mappings $\pi_j$ from $\prod_{i \in I} X_i$ to $X_j$ are defined for each index $j \in I$ by setting: $\pi_1(f) = f(1), \quad \pi_2(f) = f(2)$

Hence, for our function $f$, the projections are: $\pi_1(f) = a, \quad \pi_2(f) = 1$

Family of Sets is related to another axiom of NBG set theory.

Axiom

Let $(E_i)_{i\in I}$ be a family of nonempty sets indexed by a set $I$. Then the product $\prod_{i\in I}E_i$ is non-empty.

We can also define choice function of class.

Definition

Let $(E_i)_{i\in I}$ be a family of non-empty sets. By a choice function for this family we mean a mapping $f$ from $I$ to $\bigcup_{i\in I}E_i$ such that for every index $i$ in $I$ we have $f(i)\in E_i;$ thus a choice function is an element of the product $\prod_{i\in I}E_i.$ If we have $E_i\cap E_j=\emptyset$ for every pair of distinct elements $i, j$ of $I$ we say that the family $( E_i) _{i\in I}$ is $pairwise$ $disjoint)$ then the range of a choice function for $(E_i)_{i\in I}$ is a subset of $\bigcup_{i\in I}E_i$ which contains exactly one element from each set of the family. Such a set is called a selection set for the (pairwise disjoint) family $(E_i)_{i\in I}.$

Thus the Axiom of Choice asserts that for every family of non-empty sets there exists a choice function and so for every pairwise disjoint family of non-empty sets there exists a selection set.

Example

Consider the family of non-empty, pairwise disjoint sets: $\begin{aligned} E_1 &= \{1, 2\}, \\ E_2 &= \{3, 4\}, \\ E_3 &= \{5, 6\}, \end{aligned}$ with the index set $I = \{1, 2, 3\}$.

A choice function $f$ for this family might be defined as: $\begin{aligned} f(1) &= 1, \\ f(2) &= 4, \\ f(3) &= 5. \end{aligned}$ This function $f$ chooses one element from each set $E_i$, making the selection set for this family $\{ f(1), f(2), f(3) \} = \{1, 4, 5\}$.

Reflexivity, Symmetry, and Transitivity

With basic relation we have defined, we can now look into some special relations with some specific properties. These properties are important, since these property will be used to further classify relations for us. All special relations could be related to the diagonal of the sets or classes involved in that specific relation.

The first special relation is actually already covered in the diagonal of class, which is the idea of reflexivity, meaning a relation from an object to itself.

Definition

Let $R$ be a relation on a set $X$. The relation $R$ is said to be reflexive if $D_X \subseteq R$, where $D_X = \{(x, x) \mid x \in X\}$. That is, for every element $x$ in $X$, the pair $(x, x)$ belongs to $R$.

Example

Consider the following relations on the set $\{1, 2, 3, 4\}$:

• $R_1 = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)\}$

• $R_2 = \{(1, 1), (1, 2), (2, 1)\}$

• $R_3 = \{(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)\}$

• $R_4 = \{(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)\}$

• $R_5 = \{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)\}$

• $R_6 = \{(3, 4)\}$

Which of these relations are reflexive?

Solution: The relations $R_3$ and $R_5$ are reflexive because they both contain all pairs of the form $(a, a)$, namely, $(1, 1), (2, 2), (3, 3),$ and $(4, 4)$. The other relations are not reflexive because they do not contain all of these ordered pairs. In particular, $R_1, R_2, R_4,$ and $R_6$ are not reflexive because $(3, 3)$ is not in any of these relations.

And as a complement of Reflexivity, we can define Irreflexivity

Definition

A relation $R$ on a set $X$ is called irreflexive if $D_X \cap R = \emptyset$, i.e., no pair of the form $(x, x)$ belongs to $R$ for any $x$ in $X$.

Now we discuss symmetry of relation.

Definition

A relation $R$ on a set $X$ is symmetric if for every $x, y$ in $X$, if $(x, y) \in R$ then $(y, x)$ is also in $R$, i.e., $R = R^{-1}$

We can also define the complement of this kind of relation.

Definition

Let $R$ be a relation on a set $X$. The relation $R$ is said to be asymmetric if for any $x, y$ in $X$, whenever $(x, y) \in R$, then $(y, x) \notin R$. This implies that no pair can be in both $R$ and $R^{-1}$ unless $x = y$, which is not permitted for asymmetric relations, thus $R \cap R^{-1} = \emptyset$, i.e. $R \neq R^{-1}$, .

There is also a type of relation called antisymmetric relation.

Definition

A relation $R$ on a set $X$ is antisymmetric if for all $x, y$ in $X$, if $(x, y) \in R$ and $(y, x) \in R$, then $x = y$. That is, $R \cap R^{-1} \subseteq D_X$.

Some may confused by these similar terms. Below are the clarification and some examples.

• A relation $R$ on a set $X$ is symmetric if for any $x, y \in X$, whenever $(x, y)$ is in $R$, then $(y, x)$ is also in $R$. Symmetry implies a mutual relationship.

• A relation $R$ is asymmetric if for any $x, y \in X$, whenever $(x, y)$ is in $R$, $(y, x)$ is not in $R$. Asymmetry denotes a one-way relationship.

• A relation $R$ is antisymmetric if for any $x, y \in X$, whenever both $(x, y)$ and $(y, x)$ are in $R$, it must be that $x = y$. Antisymmetry allows for a hierarchical ordering.

Let’s explore these properties through examples:

Example

The relation “is a sibling of” is symmetric. If Tom is a sibling of Jerry, then Jerry is a sibling of Tom.

Example

The “less than” relation on the real numbers is asymmetric. If $3 < 4$, then it is not the case that $4 < 3$.

Example

The “divides” relation for integers is antisymmetric. For example, $6$ divides $12$, and $12$ does not divide $6$. But we can have 6 divides 6 itself.

Exercises

Exercise

Determine whether each of the following is a set or a class in NBG set theory, and explain why.

1. The collection of all sets that do not contain themselves.

2. The set of all natural numbers.

3. The class of all ordinal numbers.

Solution

Below are the solutions.

1. The collection of all sets that do not contain themselves is a proper class. This is because any attempt to consider it as a set leads to Russell’s paradox, thus it cannot be a set within any consistent set theory including NBG.

2. The set of all natural numbers is a set. It is well-defined and does not lead to any paradoxes within NBG set theory. Furthermore, it is an element of the class of all sets.

3. The class of all ordinal numbers is a proper class because it is too large to be a set. If it were a set, it would lead to contradictions similar to those arising from considering the “set of all sets.”

Exercise

Russel’s Paradox is fixed by introducing more strict set axioms to the set theory. In NBG theory, a proper class is defined as a top-level class that cannot be subclass of any other classes or sets, and this is the key to avoid the paradox in naive set theory. Explain in details that how this concept avoids the case in Russel’s Paradox.

Solution

With the introduction of the concept of classes, we can discuss collections that are too large to be considered as sets, such as the “class of all sets.” Therefore, the set described by Russell’s Paradox, denoted by $R$, is no longer considered a legitimate set but rather a “proper class.” This means that we refrain from discussing $R$ as a set, thereby avoiding the paradox because proper classes are not subject to the operations and axioms that constrain sets. As a result, the axiomatic system does not permit the formation of sets that would lead to Russell’s Paradox.

Exercise

Let $A,B,C$ be classes such that $A\subseteq B,B\subseteq C$, $C\subseteq A.$ Prove that $A=B=C.$

Exercise

Let $A,B,C$ be classes such that $A\subset B,B\subset C.$ Prove that $A\subset C.$

Below are exercises for binary relation.

Representation of Relations

In last section. we discussed binary relation and their properties. This section focuses on ways of representation. Symbolic language is accurate and not prone to make misunderstanding, yet it is not quite easy to understand to human minds. Therefore, we need straightforward ways to visualize them and assure the accuracy in the same time.

Representation By Matrix

The first commonly used method is matrix. A relation between finite sets can be represented using a zero-one matrix. Suppose that $R$ is a relation from $A=\{a_1,a_2,\ldots,a_m\}$ to $B=\{b_1,b_2,\ldots,b_n\}.$ (Here the elements of the sets $A$ and $B$ have been listed in a particular, but arbitrary, order. Furthermore, when $A=B$ we use the same ordering for $A$ and $B.)$ The relation $R$ can be represented by the matrix $\mathbf{M}_R=[m_{ij}]$, where $m_{ij}=\left\{\begin{matrix}1\text{ if}(a_i,b_j)\in R,\\0\text{ if}(a_i,b_j)\notin R.\end{matrix}\right.$

Example

Consider the binary relation $R$ on the set $X = \{1, 2, 3\}$ defined by the pairs $R = \{(1, 2), (2, 3), (3, 1)\}$. We can represent $R$ as a matrix $M$ where the entry $m_{ij}$ is 1 if $(i, j) \in R$ and 0 otherwise. Thus, the matrix $M$ representing $R$ is given by: $M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$ This matrix shows that there is a relation from 1 to 2, 2 to 3, and 3 to 1, as indicated by the ones in the matrix.

What about some other special relations? Here are more examples.

Reflexive Relations in Matrix

We defined reflexivity through the diagonal of a relation matrix. A relation on a set is reflexive if and only if every diagonal entry $m_{ii}$ is $1$. The off-diagonal entries may be chosen independently, so a reflexive relation need not be the identity relation.

Example

A reflexive relation on a set $X = \{1, 2, 3\}$ requires that every element is related to itself. Thus, for the relation $R$ to be reflexive, it must include the pairs $R = \{(1, 1), (2, 2), (3, 3)\}$ at minimum. The matrix $M$ representing such a reflexive relation $R$ is given by: $M = \begin{bmatrix} 1 & a & b \\ c & 1 & d \\ e & f & 1 \end{bmatrix}$ Here, the diagonal elements of the matrix are all set to 1, reflecting the reflexive property that each element is related to itself. This diagonal structure is reminiscent of an identity matrix, where all diagonal elements are 1, and all off-diagonal elements are 0. In the context of relations, the presence of 1s on the diagonal is crucial for reflexivity. However, the values of $a, b, c, d, e,$ and $f$ (the off-diagonal elements) do not influence the reflexivity of the relation and can be either 0 or 1. This highlights that while the matrix representing a reflexive relation must have 1s along its diagonal, it does not necessarily need to be an identity matrix.

Symmetric/Antisymmetric/Asymmetry Relation in Matrix

For a symmetric relation, $(a,b)\in R$ if and only if $(b,a)\in R$. In its matrix, this means $m_{ij}=m_{ji}$, or equivalently $M=M^T$. Symmetry does not require the diagonal entries to be $1$; that additional condition belongs to reflexivity.

Example

A relation $R$ on a set $X = \{1, 2, 3\}$ is symmetric if for any two elements $a$ and $b$ in $X$, whenever $(a, b) \in R$, then $(b, a)$ is also in $R$. Consider the symmetric relation $R$ defined by the pairs $R = \{(1, 1), (3, 3), (1, 2), (2, 1)\}$. The matrix $M$ representing this symmetric relation $R$ is given by: $M = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ In this matrix, the entries are symmetric about the main diagonal. The presence of $1$ at positions $(1,2)$ and $(2,1)$ illustrates the symmetric nature of the relation, as both $(1,2)$ and $(2,1)$ are included in $R$.

A reflexive relation, on the other hand, requires that each element be related to itself, leading to $1$s along the main diagonal of its matrix. In the example above, the relation is not reflexive because it does not contain $(2, 2)$.

Although both reflexive and symmetric properties concern the main diagonal, they describe different aspects of a relation:

• Reflexivity is about individual elements being self-connected, evidenced by $1$s on the diagonal.

• Symmetry involves pairs of elements and requires that if an element $a$ is related to an element $b$, then $b$ must also be related to $a$, leading to a mirrored symmetry across the diagonal.

A relation can be both reflexive and symmetric but does not need to be one to be the other. For instance, a purely symmetric relation need not include self-pairs like $(1, 1)$ unless it is also intended to be reflexive.

An antisymmetric relation on a set $X$ involves a specific condition: for any two distinct elements $\alpha$ and $b$ in $X$,if both $(a,b)$ and $(b,a)$ are in the relation $R$, then $\alpha$ must be equal to $b$. This means that if $a\neq$ $b$,it cannot be the case that both $(a,b)$ and $(b,a)$ are in $R$.In terms of matrix representation:

Example

Consider the set $X = \{1, 2, 3\}$ and define the relation $R$ on $X$ by the pairs $R = \{(1, 2), (2, 3), (3, 3)\}$. This relation is antisymmetric, which we can observe through its matrix representation. The matrix $M$ representing the relation $R$ is given by: $M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}$ In this matrix, note the following:

• The entry $m_{12} = 1$ (relation from 1 to 2), and $m_{21} = 0$ (no relation from 2 to 1), satisfying the antisymmetric condition.

• Similarly, $m_{23} = 1$ and $m_{32} = 0$.

• The diagonal entry $m_{33} = 1$ does not violate antisymmetry as self-relations do not affect antisymmetry.

Antisymmetric relations allow entries on the main diagonal (self-relations) but restrict how elements can relate symmetrically off the diagonal, ensuring that if one direction is permitted, the opposite is not unless they are the same element.

An asymmetric relation is a stronger form of an antisymmetric relation. A relation $R$ on a set $X$ is asymmetric if, for any elements $a$ and $b$ in $X$,whenever $(a,b)$ is in $R$, then $(b,a)$ cannot be in $R$. This implies that if one direction between two different elements is allowed, the opposite direction is strictly forbidden, making it impossible for both $(a,b)$ and $(b,a)$ to exist in $R$ for any $a\neq b.$

Example

Consider the set $X = \{1, 2, 3\}$ and define an asymmetric relation $R$ on $X$ by including the pairs $R = \{(1, 2), (2, 3)\}$. This relation is asymmetric as it does not contain both $(a, b)$ and $(b, a)$ for any $a$ and $b$ in $X$. The matrix $M$ representing this relation $R$ is given by: $M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$ In this matrix: - The entry $m_{12} = 1$ and $m_{21} = 0$, supporting the asymmetric nature by the absence of the reverse relation. - The entry $m_{23} = 1$ and $m_{32} = 0$, further demonstrating asymmetry.

This matrix shows no reciprocal relations between different elements, which is a defining characteristic of asymmetric relations. Note that self-relations (diagonal entries) are not present in this matrix, aligning with the strict definition of asymmetry which typically excludes self-relations as well.

Operation of Relation Matrix

We can find intersection or union of two relations easily by examining their matrices. This could be done by comparing each element with the same index one by one.

Example

Let $A = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$ and $B = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}$ be two relations.

The union $A \cup B$ is: $A \cup B = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}$

The intersection $A \cap B$ is: $A \cap B = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$

Matrix is also possible to represent composition of relations. For these relations, in particular, suppose that $R$ is a relation from $A$ to $B$ and $S$ is a relation from $B$ to $C$. Suppose that $A$, $B$, and $C$ have $m$, $n$, and $p$ elements, respectively. Let the zero-one matrices for $S \circ R$, $R$, and $S$ be $M_{S \circ R} = [t_{ij}]$, $M_R = [r_{ij}]$, and $M_S = [s_{ij}]$, respectively (these matrices have sizes $m \times p$, $m \times n$, and $n \times p$, respectively). The ordered pair $(a_i, c_j)$ belongs to $S \circ R$ if and only if there is an element $b_k$ such that $(a_i, b_k)$ belongs to $R$ and $(b_k, c_j)$ belongs to $S$. It follows that $t_{ij} = 1$ if and only if $r_{ik} = s_{kj} = 1$ for some $k$. From the definition of the Boolean product, this means that $M_{S \circ R} = M_R \otimes M_S.$

Example

$$M_R = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \quad \text{and} \quad M_S = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \\ \end{bmatrix}.$$

Solution

The matrix for $S \otimes R$ is obtained by performing the Boolean product of $M_R$ and $M_S$. This operation is similar to matrix multiplication, except that addition is replaced by the logical OR operation, and multiplication is replaced by the logical AND operation. The result is a matrix that represents the composition of the two relations: $M_{S \circ R} = M_R \otimes M_S = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}.$ Each entry in $M_{S \circ R}$ is computed by taking the logical OR of the ANDs of the corresponding row from $M_R$ and the column from $M_S$.

Example

where the matrix representing $R$ is $M_R = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix}.$

Solution

The matrix for $R^2$ is found by taking the Boolean product of $M_R$ with itself. This operation is analogous to squaring a matrix, where we use Boolean algebra for addition and multiplication: $M_{R_2} = M_{R}^{[2]} = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ \end{bmatrix}.$ The entries of $M_{R_2}$ indicate whether there is a path of length 2 between the nodes represented by the matrix indices in the relation $R$.

Representation By Digraph

The other way to visualize relation is by using Directed Graph, or Digraph.

Definition

A digraph or directed graph is an ordered pair $G = (V, A)$ comprising:

• A non-empty set $V$, whose elements are called vertices or nodes.

• A set $A$ of ordered pairs of vertices, called arcs, directed edges, arrows, or directed lines.

The directed edge $(x, y) \in A$ is said to point from the vertex $x$ to the vertex $y$. Unlike in an undirected graph, the edges in a digraph have a direction associated with them, indicated by the ordering of the vertices in the pair.

We will discuss further on graph in graph theory, now we just need to know that we will use it to visualize relation. A directed graph can be used to represent a binary relation between a set of elements. Here is an example.

Example

Let set $A = \{a,b,c\}, B = \{a,d\}$, the relation $R=\{(a,a),(a,d), (b,a),(c,a),(c,d)\}$ could be represented by the following graph.

Using Digraph is a very intuitive approach to visualize relation. In the graph, we use the element in the domain and codomain of the relation as vertex, and the relations are represented using the edges, which are also ordered pairs.

Using a graph is also easy to determine special patterns of relations such as reflexivity, symmetry, etc.

Example

Consider the relation defined from set $A=\{a,b,c\}$ to itself, $R = \{(a,a),(b,b),(c,c),(b,a)\}$. This relation could be visualized by the following graph, which is reflexive.

We see that each object has a loop for a reflexive relation.

Example

Consider the relation defined from set $A=\{a,b,c\}$ to itself, $R_1 = \{(a,b),(b,a)(a,c),(c,a)\}$, and $R_2=\{(a,a),(b,b)(c,c),(a,b),(b,c) \}$. This relation could be visualized by the following graphs.

Figure pending: R1 and R2 in Digraph

$R_1$ is symmetric because every edge between distinct objects has a matching edge in the opposite direction. $R_2$ is antisymmetric because the only pairs that occur in both directions are self-loops, although it may contain one-way edges between distinct objects.

For the cases of transitivity, it’s also quite clear in the following example.

Example

Still consider the same set $A$ and the relation $R_1 = \{(a,b), (b,c), (a,c)\}, R_2 = \{(a,a), (a,b),(b,b)\}$.

Figure pending: The original LaTeX illustration is retained in the source repository and needs a web-native asset export.

Both $R_1$ and $R_2$ are transitive. For $R_2$, transitivity follows in particular from the reflexive loops on $a$ and $b$. A relation that is reflexive, symmetric, and transitive is an equivalence relation, which we discuss next.

Exercises

Exercise

List the ordered pairs in the relations on $\{1, 2, 3, 4\}$ corresponding to these matrices (where the rows and columns correspond to the integers listed in increasing order).

$$\text{a)} \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ \end{bmatrix} \text{b)} \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ \end{bmatrix} \text{c)} \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{bmatrix}$$

Solution

1. Since the $(1,1)^{th}$ entry is a $1$, $(1,1)$ is in the relation. Since $(1,3)^{th}$ entry is a $0$, $(1,3)$ is not in the relation. Continuing in this manner, we see that the relation contains $(1,1)$, $(1,2)$, $(1,4)$, $(2,1)$, $(2,3)$, $(3,2)$, $(3,3)$, $(3,4)$, $(4,1)$, $(4,3)$, and $(4,4)$.

2. The relation contains $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(3,3)$, $(3,4)$, $(4,1)$, and $(4,4)$.

3. The relation contains $(1,2)$, $(1,4)$, $(2,1)$, $(2,3)$, $(3,2)$, $(3,4)$, $(4,1)$, and $(4,3)$.

Exercise

Represent each of these relations on $\{1, 2, 3, 4\}$ with a matrix (with the elements of this set listed in increasing order).

1. $\{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$

2. $\{(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)\}$

3. $\{(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)\}$

4. $\{(2, 4), (3, 1), (3, 2), (3, 4)\}$

Solution

The relations corresponding to these matrices (from a to d) are:

$$\begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

Exercise

How many nonzero entries does the matrix representing the relation $R$ on $A = \{1, 2, 3, ..., 1000\}$ consisting of the first 1000 positive integers have if $R$ is

1. $\{(a, b) \mid a \leq b\}$?

2. $\{(a, b) \mid a = b \pm 1\}$?

3. $\{(a, b) \mid a + b = 1000\}$?

4. $\{(a, b) \mid a + b \leq 1001\}$?

5. $\{(a, b) \mid a \neq 0\}$?

Solution

Note that the total number of entries in the matrix is $1000^2 = 1,000,000$.

1. There is a $1$ in the matrix for each pair of distinct positive integers not exceeding $1000$, namely in position $(a, b)$ where $a \leq b$, as well as $1$‘s along the diagonal. Thus the answer is the number of subsets of size $2$ from a set of $1000$ elements, plus $1000$, i.e., $C(1000, 2) + 1000 = 499500 + 1000 = 500,500$.

2. There two $1$‘s in each row of the matrix except the first and last rows, in which there is one $1$. Therefore the answer is $998 \cdot 2 + 2 = 1998$.

3. There is a $1$ in the matrix at each entry just above and to the left of the “anti-diagonal” (i.e., in positions $(1, 999), (2, 998), ..., (999, 1)$. Therefore the answer is $999$.

4. There is a $1$ in the matrix at each entry on or above (to the left of) the “anti-diagonal.” This is the same number of $1$‘s as in part (a), so the answer is again $500,500$.

5. The condition is trivially true (since $1 \leq a \leq 1000$), so all $1,000,000$ entries are $1$.

Exercise

Draw the directed graph that represents the relation $\{(a, a), (a, b), (b, c), (c, b), (c, d), (d, a), (d, b).\}$

Figure pending: The original LaTeX illustration is retained in the source repository and needs a web-native asset export.

Exercise

Let $R$ be a relation on a set $A$. Explain how to use the directed graph representing $R$ to obtain the directed graph representing the complementary relation $\overline{R}$.

Solution

For each pair $(a, b)$ of vertices (including the pairs $(a, a)$ in which the two vertices are the same), if there is an edge from $a$ to $b$, then erase it, and if there is no edge from $a$ to $b$, put add it in.

Exercise

Given the directed graphs representing two relations, how can the directed graph of the union, intersection, symmetric difference, difference, and composition of these relations be found?

Solution

We assume that the two relations are on the same set. For the union, we simply take the union of the directed graphs, i.e., take the directed graph on the same vertices and put in an edge from $i$ to $j$ whenever there is an edge from $i$ to $j$ in either of them. For intersection, we simply take the intersection of the directed graphs, i.e., take the directed graph on the same vertices and put in an edge from $i$ to $j$ whenever there are edges from $i$ to $j$ in both of them. For symmetric difference, we simply take the symmetric difference of the directed graphs, i.e., take the directed graph on the same vertices and put in an edge from $i$ to $j$ whenever there is an edge from $i$ to $j$ in one, but not both, of them. Similarly, to form the difference, we take the difference of the directed graphs, i.e., take the directed graph on the same vertices and put in an edge from $i$ to $j$ whenever there is an edge from $i$ to $j$ in the first but not the second. To form the directed graph for the composition $S \circ R$ of relations $R$ and $S$, we draw a directed graph on the same set of vertices and put in an edge from $i$ to $j$ whenever there is a vertex $k$ such that there is an edge from $i$ to $k$ in $R$, and an edge from $k$ to $j$ in $S$.

Closure of Relations

Exercises

Equivalence Relations

In mathematics, an equivalence relation is a special type of binary relation that allows us to group elements of a set into disjoint subsets called equivalence classes. The idea behind equivalence relations is to capture a meaningful notion of “sameness” or “interchangeability” among elements.

Equivalence relations are characterized by three key properties: reflexivity, symmetry, and transitivity. These properties ensure that the relation partitions the set into equivalence classes, each containing elements that are equivalent in some sense.

Equivalence

Definition

A relation on a set $A$ is called an equivalence relation if it is reflexive, symmetric, and transitive. Two elements $a$ and $b$ that are related by an equivalence relation are called equivalent. The notation $a\sim b$ is often used to denote that $a$ and $b$ are equivalent elements with respect to a particular equivalence relation.

The concept of equivalence relations is a fundamental tool in many branches of mathematics. They allow us to focus on essential characteristics that elements share, abstracting away extraneous details. Some common examples include:

• Equality of numbers

• Congruence modulo $n$ in number theory

• Similarity of triangles in geometry

• Having the same cardinality for sets

Equivalence relations provide a way to decompose a set into a collection of equivalence classes, revealing important structural insights. They are essential for understanding quotient structures, modular arithmetic, and the role of abstraction in mathematical thought.

Example

Let $m$ be an integer with $m > 1$. Show that the relation $R = \{(a, b) \mid a \equiv b \ (\mathrm{mod} \ m)\}$ is an equivalence relation on the set of integers.

Solution

Recall from Section 4.1 that $a \equiv b \ (\mathrm{mod} \ m)$ if and only if $m$ divides $a - b$. Note that $a - a = 0$ is divisible by $m$, because $0 = 0 \cdot m$. Hence, $a \equiv a \ (\mathrm{mod} \ m)$, so congruence modulo $m$ is reflexive.

Now suppose that $a \equiv b \ (\mathrm{mod} \ m)$. Then $a - b$ is divisible by $m$, so $a - b = km$, where $k$ is an integer. It follows that $b - a = (-k)m$, so $b \equiv a \ (\mathrm{mod} \ m)$. Hence, congruence modulo $m$ is symmetric.

Next, suppose that $a \equiv b \ (\mathrm{mod} \ m)$ and $b \equiv c \ (\mathrm{mod} \ m)$. Then $m$ divides both $a - b$ and $b - c$. Therefore, there are integers $k$ and $l$ with $a - b = km$ and $b - c = lm$. Adding these two equations shows that $a - c = (a - b) + (b - c) = km + lm = (k + l) m$. Thus, $a \equiv c \ (\mathrm{mod} \ m)$. Therefore, congruence modulo $m$ is transitive.

It follows that congruence modulo $m$ is an equivalence relation.

Example

Let $A$ be a non-empty set, and define a relation $\sim$ on the power set $\mathcal{P}(A)$ (the set of all subsets of $A$) as follows: for any subsets $X, Y \subseteq A$, $X \sim Y \iff |X| = |Y|$ where $|X|$ denotes the cardinality (number of elements) of the set $X$. In other words, two subsets are related by $\sim$ if and only if they have the same number of elements.

Solution

We can show that the relation $\sim$ defined above is an equivalence relation on $\mathcal{P}(A)$:

1. Reflexivity: For any subset $X \subseteq A$, we have $|X| = |X|$, so $X \sim X$.

2. Symmetry: If $X \sim Y$, then $|X| = |Y|$. Since equality of cardinalities is symmetric, we also have $|Y| = |X|$, so $Y \sim X$.

3. Transitivity: If $X \sim Y$ and $Y \sim Z$, then $|X| = |Y|$ and $|Y| = |Z|$. By the transitivity of equality, we have $|X| = |Z|$, so $X \sim Z$.

The equivalence classes under this relation are called cardinality classes. For a subset $X \subseteq A$, its cardinality class $[X]$ consists of all subsets of $A$ that have the same cardinality as $X$:

$[X] = {Y \subseteq A \mid |Y| = |X|}$

In other words, the cardinality classes partition $\mathcal{P}(A)$ into disjoint subsets based on the number of elements in each subset. For example, if $A = {1, 2, 3}$, then the cardinality classes are:

• $[\emptyset] = { \emptyset }$ (subsets with 0 elements)

• $[{1}] = {{1}, {2}, {3}}$ (subsets with 1 element)

• $[{1, 2}] = {{1, 2}, {1, 3}, {2, 3}}$ (subsets with 2 elements)

• $[A] = {A}$ (subsets with 3 elements)

This equivalence relation captures the idea that two sets are “equivalent” if they have the same cardinality, regardless of their specific elements. The study of cardinality and the relationships between sets of different sizes is a fundamental aspect of set theory and plays a crucial role in the development of modern mathematics, including the theory of infinite sets and the foundations of mathematics.

Example

Let $R$ be the relation on the set of real numbers such that $xRy$ if and only if $x$ and $y$ are real numbers that differ by less than 1, that is, $|x - y| < 1$. Show that $R$ is not an equivalence relation.

Solution

$R$ is reflexive because $|x - x| = 0 < 1$ whenever $x \in \mathbb{R}$. $R$ is symmetric, for if $xRy$, where $x$ and $y$ are real numbers, then $|x - y| < 1$, which tells us that $|y - x| = |x - y| < 1$, so that $yRx$. However, $R$ is not an equivalence relation because it is not transitive. Take $x = 2.8$, $y = 1.9$, and $z = 1.1$, so that $|x - y| = |2.8 - 1.9| = 0.9 < 1$, $|y - z| = |1.9 - 1.1| = 0.8 < 1$, but $|x - z| = |2.8 - 1.1| = 1.7 > 1$. That is, $2.8R1.9$, $1.9R1.1$, but not $2.8R1.1$.

Equivalence Classes

We can dig deeper into equivalence by partitioning the set where the relation is built upon with respect to a member of the subset. We call this a Equivalence Class.

Definition

Let $R$ be an equivalence relation on a set A. The set of all elements that are related to an element $a$ of $A$ is called the $equivalence$ class of $a$. The equivalence class of $a$ with respect to $R$ is denoted by $[a]_R$. When only one relation is under consideration, we can delete the subscript $R$ and write $[a]$ for this equivalence class.

Remark

In set notation we have $[a]_R = \{ (a,s) \in R\}.$ For some member $e\in [a]_R$, we call $e$ a representative of the equivalence class.

Example

What is the equivalence class of an integer for the equivalence relation $a = |b|$?

Solution

Since $a = b \text{ or } a = -b$, so $[a] = \{-a,a\}$, which holds for all integer, including 0. We have $[3] = \{ -3, 3\}$, etc.

Example

What are the equivalence classes of 0 and 1 for congruence modulo 2?

Solution

The equivalence class of 0 contains all integers $a$ such that $a \equiv 0 \pmod{4}$. The integers in this class are those divisible by 4. Hence, the equivalence class of 0 for this relation is $[0] = \{ \ldots, -8, -4, 0, 4, 8, \ldots \}.$

The equivalence class of 1 contains all the integers $a$ such that $a \equiv 1 \pmod{4}$. The integers in this class are those that have a remainder of 1 when divided by 4. Hence, the equivalence class of 1 for this relation is $[1] = \{ \ldots, -7, -3, 1, 5, 9, \ldots \}.$

This notion actually allows us to further abstract to congruence classes modulo $m$.

Definition

Let $m$ be a positive integer. The congruence class of an integer $a$ modulo $m$, denoted by $[a]_m$, is the set of all integers $b$ such that $b \equiv a \ (\mathrm{mod} \ m)$, which means that $m$ divides $b - a$. Formally, the congruence class $[a]_m$ is defined as: $[a]_m = \{ b \in \mathbb{Z} \ | \ b \equiv a \ (\mathrm{mod} \ m) \} = \{ b \in \mathbb{Z} \ | \ \exists k \in \mathbb{Z}, \ b = a + km \}.$

Here are some other examples on equivalence class.

Example

Find the equivalence class for $\frac{1}{2}$ under the relation of fraction simplification.

Solution

The equivalence class of $\frac{1}{2}$ consists of all fractions that simplify to $\frac{1}{2}$, which includes all rational numbers where the numerator is half the denominator. Hence, the equivalence class is: $[1/2] = \left\{ \frac{2}{4}, \frac{3}{6}, \frac{4}{8}, \frac{5}{10}, \ldots \right\}$

Example

Find the equivalence class for the string “cat” under the relation of having the same length.

Solution

The equivalence class of the string “cat” consists of all strings of length 3. Examples include: $[\text{"cat"}] = \{ \text{"dog"}, \text{"pen"}, \text{"sun"}, \text{"mom"}, \ldots \}$

Congruence Class can be further interpreted by introducing partition of set. Recall (in definition def

) that the partition of a set are a possible combination of mutually disjoint subsets of a set. Suppose we have some set $R$, than we can make form some three-member partition $(P_1\cup P_2\cup P_3) = R$, where $P_1,P_2,P_3,\subseteq R$. Also we have $|R| = |P_1|+|P_2|+|P_3|$. But notice that $P_i\cap P_j, i,j \in\{1,2,3\}$ is $\emptyset$.

Now let’s relate this to congruence class.

Theorem

Let $R$ be an equivalence relation on a set $A$. These statements for elements $a$ and $b$ of $A$ are equivalent:

$(i):aRb\quad(ii):[a]=[b]\quad(iii):[a]\cap[b]\neq\emptyset$

Proof

We first show that (i) implies (ii). Assume that $aRb$. We will prove that $[a] = [b]$ by showing $[a] \subseteq [b]$ and $[b] \subseteq [a]$. Suppose $c \in [a]$, where $c$ is any arbitrary member of $[a]$. Then $aRc$. Because $aRb$ and $R$ is symmetric, we know that $bRa$. Furthermore, because $R$ is transitive and $bRa$ and $aRc$, it follows that $bRc$. Hence, $c \in [b]$. This shows that $[a] \subseteq [b]$, since all elements of $[a]$ is also an element of $[b]$. The proof that $[b] \subseteq [a]$ is similar.

Second, we will show that (ii) implies (iii). Assume that $[a] = [b]$. It follows that $[a] \cap [b] \neq \emptyset$ because $[a]$ is nonempty (because $a \in [a]$ since $R$ is reflexive).

Next, we will show that (iii) implies (i). Suppose that $[a] \cap [b] \neq \emptyset$. Then there is an element $c$ with $c \in [a]$ and $c \in [b]$. In other words, $aRc$ and $bRc$. By the symmetric property, $cRb$. Then by transitivity, because $aRc$ and $cRb$, we have $aRb$.

Because (i) implies (ii), (ii) implies (iii), and (iii) implies (i), the three statements, (i), (ii), and (iii), are equivalent.

Let $R$ be an equivalence relation on a set $A$. The union of the equivalence classes is the whole set $A$, because an element a of $A$ is in its own equivalence class, and there is no intersection between equivalence class of different elements. $\bigcup_{a\in A}[a]_R=A.$ This is because from theorem one we have

Lemma

If $[a]_R \neq [b]_R$, then $[a]_R\cap[b]_R=\emptyset.$

This is because when $[a]_R = [b]_R$, the intersection cannot be empty.

Lemma

The partition of a set S exists if and only if the family of set index by $i \in I$ with respect to subsets $A_i$, $A_i \neq \emptyset, \forall i \in I$, and $A_i\cap A_j = \emptyset$ when $i\neq j$. And we have S as a family of set index by $i$ $\bigcup_{i \in I}A_i = S.$

Example

Let $A = \mathbb{Z}$, the set of all integers, and let $R$ be the equivalence relation of congruence modulo $3$. Determine if the following statements are true:

1. $1R4$

2. $[1] = [4]$

3. $[1] \cap [4] \neq \emptyset$

Solution

1. $1R4$ is true because $4 \equiv 1 \mod 3$.

2. $[1] = [4]$ is true because both $1$ and $4$ have the same remainder when divided by $3$, which means they are in the same equivalence class modulo $3$.

3. $[1] \cap [4] \neq \emptyset$ is true because $[1]$ contains $4$ since $4 \equiv 1 \mod 3$, hence $4$ is in both $[1]$ and $[4]$.

As all three statements are true, the statements (i), (ii), and (iii) are equivalent for the given equivalence relation.

Exercises

Exercise

Determine the equivalence class of $2$ under the relation of congruence modulo $5$.

Solution

The equivalence class of $2$ modulo $5$, denoted $[2]_5$, consists of all integers that leave a remainder of $2$ when divided by $5$. This can be expressed as: $[2]_5 = \{ \ldots, -8, -3, 2, 7, 12, \ldots \}$ where each element is of the form $2 + 5k$ for some integer $k$.

Exercise

Let $S$ be the equivalence relation on $\mathcal{P}(\{1, 2, 3, 4\})$ defined by $X \sim Y \text{ if and only if } |X \cup \{2\}| = |Y \cup \{2\}|.$

Write down the equivalence classes of $S$.

Solution

To find the equivalence classes of the relation $S$, we need to analyze how the sets $X \cup \{2\}$ and $Y \cup \{2\}$ affect the cardinality and thus the equivalence.

Consider the power set $\mathcal{P}(\{1, 2, 3, 4\})$, which includes all subsets of $\{1, 2, 3, 4\}$:

$$\begin{aligned} \mathcal{P}(\{1, 2, 3, 4\}) = & \{\emptyset, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \\ & \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 3, 4\}\} \end{aligned}$$

We need to group these sets into equivalence classes based on the criterion $|X \cup \{2\}| = |Y \cup \{2\}|$.

1. $\{\emptyset, \{2\}\}$

• $\emptyset \cup \{2\} = \{2\}$, $|\emptyset \cup \{2\}| = 1$

• $\{2\} \cup \{2\} = \{2\}$, $|\{2\} \cup \{2\}| = 1$

2. $\{\{1\}, \{3\}, \{4\}, \{1, 2\}, \{2, 3\}, \{2, 4\}\}$

• $\{1\} \cup \{2\} = \{1, 2\}$, $|\{1\} \cup \{2\}| = 2$

• $\{3\} \cup \{2\} = \{2, 3\}$, $|\{3\} \cup \{2\}| = 2$

• $\{4\} \cup \{2\} = \{2, 4\}$, $|\{4\} \cup \{2\}| = 2$

• $\{1, 2\} \cup \{2\} = \{1, 2\}$, $|\{1, 2\} \cup \{2\}| = 2$

• $\{2, 3\} \cup \{2\} = \{2, 3\}$, $|\{2, 3\} \cup \{2\}| = 2$

• $\{2, 4\} \cup \{2\} = \{2, 4\}$, $|\{2, 4\} \cup \{2\}| = 2$

3. $\{\{1, 3\}, \{1, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{2, 3, 4\}\}$

• $\{1, 3\} \cup \{2\} = \{1, 2, 3\}$, $|\{1, 3\} \cup \{2\}| = 3$

• $\{1, 4\} \cup \{2\} = \{1, 2, 4\}$, $|\{1, 4\} \cup \{2\}| = 3$

• $\{3, 4\} \cup \{2\} = \{2, 3, 4\}$, $|\{3, 4\} \cup \{2\}| = 3$

• $\{1, 2, 3\} \cup \{2\} = \{1, 2, 3\}$, $|\{1, 2, 3\} \cup \{2\}| = 3$

• $\{1, 2, 4\} \cup \{2\} = \{1, 2, 4\}$, $|\{1, 2, 4\} \cup \{2\}| = 3$

• $\{2, 3, 4\} \cup \{2\} = \{2, 3, 4\}$, $|\{2, 3, 4\} \cup \{2\}| = 3$

4. $\{\{1, 3, 4\}, \{1, 2, 3, 4\}\}$

• $\{1, 3, 4\} \cup \{2\} = \{1, 2, 3, 4\}$, $|\{1, 3, 4\} \cup \{2\}| = 4$

• $\{1, 2, 3, 4\} \cup \{2\} = \{1, 2, 3, 4\}$, $|\{1, 2, 3, 4\} \cup \{2\}| = 4$

Therefore, the equivalence classes are: $\begin{aligned} &\{\emptyset, \{2\}\}, \\ &\{\{1\}, \{3\}, \{4\}, \{1, 2\}, \{2, 3\}, \{2, 4\}\}, \\ &\{\{1, 3\}, \{1, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{2, 3, 4\}\}, \\ &\{\{1, 3, 4\}, \{1, 2, 3, 4\}\}. \end{aligned}$

Exercise

Let $A = \mathbb{Z}$, and define $R$ on $A$ by $xRy$ if and only if $x - y$ is even. Determine if the following statements are true for $a = 2$ and $b = 5$:

1. $aRb$

2. $[2] = [5]$

3. $[2] \cap [5] \neq \emptyset$

Solution

1. $aRb$ is false because $2 - 5$ is odd.

2. $[2] = [5]$ is false because $2$ is in the equivalence class of even remainders while $5$ is in the class of odd remainders.

3. $[2] \cap [5] \neq \emptyset$ is false because $[2]$ contains all even numbers and $[5]$ contains all odd numbers, so they have no elements in common.

In this case, statements (i), (ii), and (iii) are not equivalent because the relation $R$ is not defined as congruence modulo some number but rather by the parity of the difference between elements.

No that we can get partition of a set from a equivalence relation, can we inverse this process? That is, define a equivalence relation with some given set partitions? The answer is yes.

To see this, assume that $\{A_i \mid i \in I\}$ is a partition on $S$. Let $R$ be the relation on $S$ consisting of the pairs $(x, y)$, where $x$ and $y$ belong to the same subset $A_i$, in the partition. To show that $R$ is an equivalence relation we must show that $R$ is reflexive, symmetric, and transitive.

We see that $(a, a) \in R$ for every $a \in S$, because $a$ is in the same subset of $S$ as itself. Hence, $R$ is reflexive. If $(a, b) \in R$, then $b$ and $a$ are in the same subset of $S$ in the partition, so that $(b, a) \in R$ as well. Hence, $R$ is symmetric. If $(a, b) \in R$ and $(b, c) \in R$, then $a$ and $b$ are in the same subset $X$ of $S$ in the partition, and $b$ and $c$ are in the same subset $Y$ of $S$ of the partition. Because the subsets of $S$ in the partition are disjoint and $b$ belongs to $X$ and $Y$, it follows that $X = Y$. Consequently, $a$ and $c$ belong to the same subset of $S$ in the partition, so $(a, c) \in R$. Thus, $R$ is transitive.

It follows that $R$ is an equivalence relation. The equivalence classes of $R$ consist of subsets of $S$ containing related elements, and by the definition of $R$, these are the subsets of $S$ in the partition. The theorem summarizes the connections we have established between equivalence relations and partitions.

Theorem

Let $R$ be an equivalence relation on a set $S$. Then the equivalence classes of $R$ form a partition of $S$. Conversely, given a partition $\{A_i \mid i \in I\}$ of the set $S$, there is an equivalence relation $R$ that has the sets $A_i, i \in I$, as its equivalence classes.

Example

For example, consider the set $S = \{1, 2, 3, 4, 5, 6\}$.

One possible equivalence relation $R$ on $S$ is “congruence modulo 3”. This relation partitions $S$ into the equivalence classes $[1] = \{1, 4\}$, $[2] = \{2, 5\}$, and $[3] = \{3, 6\}$.

Conversely, consider a partition of $S$ into subsets $A_1 = \{1, 2\}$, $A_2 = \{3, 4\}$, and $A_3 = \{5, 6\}$. The equivalence relation $R$ induced by this partition is such that two numbers are related if and only if they are in the same subset $A_i$.

Order Relations

Another important family is formed by order relations, including partial, total, and well orders. We begin with the most general notion, the partial order, and then specialize it.

Partial, Total, and Well Ordering

Definition

A relation $R$ on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set $S$ together with a partial ordering $R$ is called a partial ordered set, or poset, and is denoted by $(S,R)$. Members of S are called elements of the poset.

Remark

The reason why partial order relation has a specific notation for poset is because that order relation is usually defined on the same set(for the domain and codomain). For equivalence relation, however, we see more relation between different sets.

The most common partial order relation is “greater than or equal to”, “is subset to”, and “divides”.

Example

Show that the greater than or equal to relation $\geq$ is a partial ordering on the set of integers.

Solution: Because $a \geq a$ for every integer $a$, $\geq$ is reflexive. If $a \geq b$ and $b \geq a$, then $a = b$. Hence, $\geq$ is antisymmetric. Finally, $\geq$ is transitive because $a \geq b$ and $b \geq c$ imply that $a \geq c$. It follows that $\geq$ is a partial ordering on the set of integers and $(\mathbb{Z}, \geq)$ is a poset.

Example

The divisibility relation $|$ is a partial ordering on the set of positive integers, because it is reflexive, antisymmetric, and transitive, as was shown in Section 9.1. We see that $(\mathbb{Z}^+, |)$ is a poset.

Example

Show that the inclusion relation $\subseteq$ is a partial ordering on the power set of a set $S$.

Solution: Because $A \subseteq A$ whenever $A$ is a subset of $S$, $\subseteq$ is reflexive. It is antisymmetric because $A \subseteq B$ and $B \subseteq A$ imply that $A = B$. Finally, $\subseteq$ is transitive, because $A \subseteq B$ and $B \subseteq C$ imply that $A \subseteq C$. Hence, $\subseteq$ is a partial ordering on $P(S)$, and $(P(S), \subseteq)$ is a poset.

For convenience of representation, we need a symbol to define the operator for an arbitrary partial ordering.

Notation

$\preccurlyeq$ is used to define any arbitrary partial order relation $a \preccurlyeq b$ on set $S$. Alternatively, we also have $a \prec b$ to denote that $a\preccurlyeq b$ but $a \neq b$.

With this, we can define comparability of the relation. This helps us to distinguish different types of special partial orderings.

Definition

The elements $a$ and $b$ of a poset (S, $\preccurlyeq)$ are called comparable if either $a\preccurlyeq b$ or $b\preccurlyeq a$. When $a$ and $b$ are elements of S such that neither $a\preccurlyeq b$ nor $b\preccurlyeq a,a$ and $b$ are called incomparable.

Example

In the poset $(\mathbb{Z}^+ ,\mid)$, are 3 and 9 comparable? Also consider 4 and 5.

Solution

3 and 9 are obviously comparable, since even though $9 \nmid 3$, we still have $3 \mid 9$. So 3 and 9 are comparable. While $4\nmid 5$ and $5\nmid 4$, so they are not comparable.

We see that for divisibility, there are cases that the relation is not comparable among the elements that are involved here. Actually this is why we call it partial order, because there are cases that things cannot be compared or cannot build relation. If we can have a very special partial ordering on $S$ that is comparable for every member of the set, we call it a total ordering or total order relation.

Definition

If $(S, \preccurlyeq)$ is a poset and every two elements of $S$ are comparable, $S$ is called a totally ordered or linearly ordered set, and $\preccurlyeq$ is called a total order or a linear order. A totally ordered set is also called a chain.

Total ordering is also very quite familiar to us, actually, the $\leq$ relation we just mentioned is also a total order relation, and so as $\geq$.

Here are some other examples.

Example

The set of words in a dictionary with the alphabetical order is a totally ordered set because any two words can be compared based on lexicographic order.

Example

The set of points on a line with a defined direction is a totally ordered set, where any two points can be compared based on their position relative to each other along the line.

So we know that total orderings are special partial orderings. Now, can we manage to find a kind of special relation with respect to total ordering? The answer is yes, and we have actually known this relation, as it is the foundation of the principal of mathematical induction (theorem principle/induc).

Definition

The poset $(S, \preccurlyeq)$ is a well-ordered set if $\preccurlyeq$ is total ordering and every nonempty subset of $S$ has a least element.

Here are some example of well-ordering.

Example

The set of natural numbers $\mathbb{N}$ with the usual order $\leq$ is not only a totally ordered set but also a well-ordered set because every non-empty subset of $\mathbb{N}$ has a smallest element.

Example

Consider the set $S = \{\frac{1}{n} \mid n \in \mathbb{N}\}$. The set $S$ with the order $\leq$ is a well-ordered set because for any non-empty subset of $S$, the element with the largest $n$ (which exists because $\mathbb{N}$ is well-ordered) will be the least element of that subset.

Example

The set of positive integers up to 100, $\{1, 2, \ldots, 100\}$, is well-ordered by the usual $\leq$ relation. Any non-empty subset has a minimum element since it is a finite subset of the well-ordered set $\mathbb{N}$.

Well ordering secures that each step we made with mathematical induction is correct, since the least element allows us to define a solid base case, so that the rest of the statement could be proved one by one by applying our hypothesis, so that the inductive step could be proven. This could be encapsulated by the following theorem.

Theorem

Suppose that $S$ is a well-ordered set. Then $P(x)$ is true for all $x \in S$, if

Inductive Step: For every $y \in S$, if $P(x)$ is true for all $x \in S$ with $x < y$, then $P(y)$ is true.

Proof

Suppose it is not the case that $P(x)$ is true for all $x \in S$. Then there is an element $y \in S$ such that $P(y)$ is false. Consequently, the set $A = \{ x \in S \mid P(x) \text{ is false} \}$ is nonempty. Because $S$ is well-ordered, $A$ has a least element $a$. By the choice of $a$ as a least element of $A$, we know that $P(x)$ is true for all $x \in S$ with $x < a$. This implies by the inductive step $P(a)$ is true. This contradiction shows that $P(x)$ must be true for all $x \in S$.

Remark

We do not need a basis step in a proof using the principle of well-ordered induction because if $x_0$ is the least element of a well-ordered set, the inductive step tells us that $P(x_0)$ is true. This follows because there are no elements $x \in S$ with $x < x_0$, so we know (using a vacuous proof) that $P(x)$ is true for all $x \in S$ with $x < x_0$.

Lexicographic Order

In a dictionary, all words are ordered in alphabetical order by the first letter that is different from the other previous words. For example, we have this array of string in alphabetical order: [“a”, “abnormal”, “acknowledge”, “acquire”…]. We can conceptualize this ordering in mathematics with partial order relation, calling lexicographic order.

The concept of lexicographic ordering can be extended beyond strings and applied to the Cartesian product of two posets. We formalize this concept as follows:

Definition

Given two posets $(A_1, \preccurlyeq_1)$ and $(A_2, \preccurlyeq_2)$, the lexicographic ordering $\preccurlyeq$ on $A_1 \times A_2$ compares first coordinates, and compares second coordinates only when the first coordinates are equal. Its strict part is

$$(a_1,a_2)\prec(b_1,b_2)\quad\Longleftrightarrow\quad a_1\prec_1 b_1\ \text{or}\ (a_1=b_1\ \text{and}\ a_2\prec_2 b_2).$$

We achieve a partial ordering $\preccurlyeq$ by combining this lexicographic ordering with equality. Here is how we verify it.

Proof

For reflexivity, every pair $(a_1,a_2)$ is related to itself because $a_1=a_1$ and $a_2\preccurlyeq_2 a_2$.

For antisymmetry, suppose both $(a_1,a_2)\preccurlyeq(b_1,b_2)$ and $(b_1,b_2)\preccurlyeq(a_1,a_2)$. If $a_1\neq b_1$, the strict first-coordinate alternatives would point in opposite directions, which is impossible. Hence $a_1=b_1$. The definition then reduces to $a_2\preccurlyeq_2 b_2$ and $b_2\preccurlyeq_2 a_2$, so $a_2=b_2$ by antisymmetry of $\preccurlyeq_2$.

For transitivity, if the first coordinates are strictly ordered, transitivity of $\preccurlyeq_1$ gives the required first-coordinate comparison. If the first coordinates are equal, the comparison is decided by the second coordinates, where transitivity of $\preccurlyeq_2$ applies. Thus the lexicographic relation is a partial order. It is total when both component orders are total.

Example

Consider two posets, $(A_1, \leq_1)$ where $A_1 = \{1, 2\}$ with the usual less than or equal relation, and $(A_2, \leq_2)$ where $A_2 = \{a, b\}$ with $a \leq_2 b$. The lexicographic order $\leq$ on $A_1 \times A_2$ is given as follows:

For any two elements $(a_1, a_2), (b_1, b_2) \in A_1 \times A_2$, we say that $(a_1, a_2) \leq (b_1, b_2)$ if:

1. $a_1 <_1 b_1$, or

2. $a_1 = b_1$ and $a_2 \leq_2 b_2$.

For example, $(1, a) \leq (2, a)$ because $1 <_1 2$, and $(2, a) \leq (2, b)$ because $2 = 2$ and $a \leq_2 b$. Thus, the pair $(1, a)$ is considered less than $(2, b)$ in the lexicographic ordering because the first element of the first pair (1) is less than the first element of the second pair (2), even though we do not compare the second elements in this case.

Hasse Diagram

Maximal and Minimal Elements

Lattices

Topological Sorting

Exercises

The following exercises are on lexicographic ordering.

Exercise

Do some tricks to the result of the proof in definition lexord to make it a well order relation.

Solution

This could be solved without a second thought that we can make $A_1,A_2$ any sets with smallest element, such as $\Z_{1}$, all integers greater than or equal 1.

Exercise

Let $R$ be a binary relation on $\mathbb{Z}$ defined by $xRy \text{ if and only if } x < y \text{ or } x \equiv y \pmod{2}.$

Is $R$ reflexive? Is $R$ symmetric? Is $R$ antisymmetric? Is $R$ transitive?

Fully justify each answer.

Solution

Let’s analyze the properties of the relation $R$.

• Reflexive: A relation $R$ on a set $A$ is reflexive if every element is related to itself, i.e., $aRa$ for all $a \in A$.

  For any integer $x \in \mathbb{Z}$, we have $x \equiv x \pmod{2}$. Hence, $xRx$ holds for all $x \in \mathbb{Z}$.

  Therefore, $R$ is reflexive.

• Symmetric: A relation $R$ on a set $A$ is symmetric if $aRb$ implies $bRa$ for all $a, b \in A$.

  Consider the pair $(2, 3)$. We have $2R3$ because $2 < 3$. However, $3 \not R 2$ because $3 > 2$ and $3 \not\equiv 2 \pmod{2}$.

  Therefore, $R$ is not symmetric.

• Antisymmetric: A relation $R$ on a set $A$ is antisymmetric if $aRb$ and $bRa$ imply $a = b$ for all $a, b \in A$.

  Consider the pair $(2, 4)$. We have $2R4$ because $2 < 4$, and $4R2$ because $4 \equiv 2 \pmod{2}$. However, $2 \neq 4$.

  Therefore, $R$ is not antisymmetric.

• Transitive: A relation $R$ on a set $A$ is transitive if $aRb$ and $bRc$ imply $aRc$ for all $a, b, c \in A$.

  Consider the elements $2$, $3$, and $1$. We have $2R3$ because $2 < 3$, and $3R1$ because $3 \equiv 1 \pmod{2}$. However, $2 \not R 1$ because $2 \not< 1$ and $2 \not\equiv 1 \pmod{2}$.

  Therefore, $R$ is not transitive.

Exercise

Explain why the conjunction of a partial order relation and an equivalence relation leads to the previous result.

Solution

A partial order relation is a binary relation that is reflexive, antisymmetric, and transitive. An equivalence relation is a binary relation that is reflexive, symmetric, and transitive.

When we combine a partial order relation with an equivalence relation, the resulting relation can still be reflexive because both component relations are reflexive. However, the antisymmetry of the partial order can conflict with the symmetry of the equivalence relation, leading to a relation that is neither antisymmetric nor symmetric. Furthermore, the transitivity of the partial order might not hold if the conditions of the equivalence relation introduce exceptions, which can break the transitivity in specific cases.

In this particular example: - The reflexive property is preserved because both conditions $x < y$ and $x \equiv y \pmod{2}$ ensure that $xRx$. - The symmetry is broken because $x < y$ does not imply $y < x$. - The antisymmetry is violated when equivalence modulo 2 ($x \equiv y \pmod{2}$) holds for distinct $x$ and $y$. - The transitivity is disrupted when combining the partial order ($x < y$) with equivalence modulo 2, as seen in the counterexample with $2, 3$, and $1$.

Thus, the combined relation $R$ does not retain all properties of partial orders and equivalence relations.

$n$-ary Relations

Exercises