Set Relations

Maggie Schildt

14 Set Relations

We have already introduced most common relations in the previous section on logic, where we studied the different symbols and their usage as they related to true and false statements including =, $\neq, \neg, \vee, \wedge, \cap, \cup, \rightarrow, \leq,$ and $\geq$ . In sets we also looked at the subset and proper subset of sets, denoted $\subseteq$ and $\subset$ , respectively. In this section we will discuss some formal definitions and classifications of relations [38].

Definition.

Let $A$ and $B$ be sets. A relation $R$ from $A$ to $B$ is a subset of $A\times B$ . Given an ordered pair $(x, y)$ in $A\times B$ , $x$ is related to $y$ by $R$ , written $xRy$ , if, and only if, $(x, y)$ is in $R$ . The set $A$ is called the domain of $R$ and set $B$ is called its co-domain.

We can also tie in logic since every relation has a true or false value to it as well since $xRy$ is considered a statement. To have this make more sense, consider that $R$ is a relation, which we already know, but it should be noted that this means that examples of $R$ can be $\cup$ , $\wedge$ , $\rightarrow$ . Thus, we can say that every time we have looked at an example with multiple sets or logical propositions we are looking at relations with $R$ defined as a union, intersection, “if, then” statements, etc.

Now $R$ has properties that allow us to classify each relation [38].

Definition.

Let $R$ be a relation on a set $A$ .

$R$ is reflexive if, and only if, for all $x\in A$ , $xRx$ .
$R$ is symmetric if, and only if, for all $x,y\in A$ , if $xRy$ then $yRx$ .
$R$ is transitive if, and only if, for all $x,y,z\in A$ , if $xRy$ and $yRz$ then $xRz$ .

If we want to classify a relation $R$ as reflexive then for every element $x$ in the set $A$ , $x$ must relate to itself. If we want to classify a relation $R$ as symmetric then for every element $x$ and $y$ in the set $A$ , if $x$ is to relate to $y$ then $y$ must relate to $x$ .

Finally, in order for us to classify $R$ as transitive if elements $x$ , $y$ , and $z$ are all within set $A$ and $x$ relates to $y$ the same way $y$ relates to $z$ then $x$ should relate to $z$ the same as well.

It should be noted that a relation does not need to meet all three classifications to be a relation. There is a kind of relation that does require all three to be met, which we will address later on.

Now there are opposing classifications for relations as well.

Definition.

Let $R$ be a relation on set $A$ .

$R$ is irreflexive if there is no element $x\in A$ such that $xRx$ .
$R$ is antisymmetric if for all $x,y\in A$ , $xRy$ and $yRx$ implies $x=y$ .

Now that we have established the characterizations for relations, consider the relation classifications using different orders of the characterizations.

12.1 Ordering Relations

We can consider some classifications for types of relations using different orders of relation characterization.

Definition. Partial Order

Let $R$ be a binary relation on $A$ , $R$ is a partial order relation if it is reflexive, anti-symmetric, and transitive.

In Bridge to Abstract Mathematics we use a diagram known as the Hasse Diagram to display partial orders. An example of a partial order using a Hasse Diagram can be see below.

Let us look at an example for proving a partial order relation below.

Example:

Prove that if $R$ is a partial order on a set $A$ , then $R^{-1}$ , the inverse of $R$ , is also a partial order on $A$ [20].

Reflexive: Since $R$ is a partial order let $x\in A$ such that ( $x,x$ ) $\in R$ and $xRx$ . Then ( $x,x$ ) $\in R^{-1}$ such that $xR^{-1}x$ . We can thus conclude that $R^{-1}$ is reflexive on $A$ .

Anti-symmetric: As well since $R$ is a partial order let $x,y\in A$ such that $x,y\in R$ , so $xRy$ and $yRx$ , $x=y$ . Therefore $x,y\in R^{-1}$ such that $yR^{-1}x$ and $xR^{-1}y$ , thus $x=y$ . We can conclude that $R^{-1}$ is anti-symmetric.

Transitive: Finally since $R$ is a partial order let $x,y,z\in A$ such that $x,y,z\in R$ so $xRy$ , $yRz$ , and $xRz$ . Therefore $x,y,z\in R^{-1}$ such that $yR^{-1}x$ , $zR^{-1}y$ and thus $zR^{-1}x$ . We can thus conclude that $R^{-1}$ is transitive.

Thus by the definition of partial orders $R^{-1}$ is a partial order on $A$ if $R$ is a partial order on $A$ .

Continuing on to another ordering relation, Total Order or Linear Order. Before we can introduce this order we need to briefly define the Trichotomy law, also called comparability [39].

Definition. Trichotomy Law

For arbitrary real numbers $x$ and $y$ , exactly one of the relations $x<y$ , $x>y$ , or $x=y$ holds.

With the trichotomy law essentially tells us that for two real, arbitrary number $x$ and $y$ either $x>y$ , $y>x$ , or $x=y$ . At no time can $x$ and $y$ have more than one of these relations. This means if $x=y$ then $x\ngtr y$ and $y\ngtr x$ , if $x>y$ then $x\neq y$ and $y\ngtr x$ , and if $y>x$ then $x\neq y$ and $x\ngtr y$ .

Now that we have established this law we will continue to the formal definition for a Linear Order [39].

Definition. Linear Order

Let $R$ be a binary relation on set $A$ , $R$ is linear, or total order relation if it is a partial order, and for every $x,y\in A$ $xRy$ or $yRx$ .

The linear order is meant to help mathematicians easily distinguish sets that are partial orders, which we defined previously, and for which every pair of elements $x$ and $y$ in the set either have the relation $xRy$ or $yRx$ but not both. The last order we will cover is the quasi order [4].

Definition. Quasi Order

Let $R$ be a binary relation on $A$ , $R$ is a Quasi Order relation if it is irreflexive and transitive.

Again, we have an order that allows us to distinguish sets that only fulfill the irreflexive and transitive properties, which we previously defined. Examples of quasi ordering are proper subsets, where $x$ can be a proper subset of another proper subset but for which $x$ cannot be a proper subset of itself. Another example involves less-than relation which is utilized similarly for values of $x$ instead of using set relations for a set $x$ . Let us now move on to one of the most used and most important ordered relations in abstract mathematics, the Equivalence Relation.

12.2 Equivalence Relations

Now we discussed, earlier, that relations do not need to be reflexive, symmetric, and transitive in order to be a relation. There is one kind of relation that does require all three classifications to be met though, the equivalence relation [38].

Definition.

Let $A$ be a set and $R$ a relation on $A$ , $R$ is an equivalence relation if, and only if, $R$ is reflexive, symmetric, and transitive.

Now consider some proofs for finding equivalence relations.

Example:

Prove relation $R$ on $\mathbb{Z}$ , defined by $xRy$ if $x^{2}+ y^{2}$ is even [20].

Proof:

Reflexive: If $x\in \mathbb{Z}$ then $x^{2}+x^{2}=2x^{2}$ . By definition of even numbers, $x^{2}+x^{2}$ and we can conclude that R is reflexive.
Symmetric: If $x,y\in \mathbb{Z}$ such that $xRy$ then $x^{2}+y^{2}$ is even. By the commutative law for integers we can also conclude that $y^{2}+x^{2}$ is even. Thus $xRy$ and $yRx$ so $R$ is symmetric.
Transitive: For $x,y,z\in \mathbb{Z}$ , if $xVy$ then $x^{2}+y^{2}$ is even and if $yRz$ then $y^{2}+z^{2}$ is even. We can also find that since $x^{2}+y^{2}$ is even and $y^{2}+z^{2}$ is even then the sum of the two is also even which gives us:

$\begin{equation*} \begin{split} (x^{2}+y^{2})+(y^{2}+z^{2})=x^{2}+z^{2}-2y^{2} \end{split} \end{equation*}$

If we subtract the even value $2y^{2}$

$\begin{equation*} x^{2}+z^{2}-2y^{2}-2y^{2} \end{equation*}$

An even minus an even is still even thus we can draw the conclusion that $x^{2}+z^{2}$ is even so $xRz$ , thus $R$ is transitive.

Since $R$ is reflexive, symmetric, and transitive then by definition of equivalence relations $R$ is an equivalence relation.

This concludes our section on relations. In the next section we will continue discussing relation use but as it applies to functions and the classification of functions.

14 Set Relations

License

Share This Book