Discrete Mathematics for Computer Science

Subsection 10.3.1 Individual Properties

Consider the set \(B = \{1, 2, 3, 4, 6, 12, 36, 48\}\) and the relations “divides” and \(\leq \) on \(B\text{.}\) We notice that these two relations on \(B\) have three properties in common:

• Every element in \(B\) divides itself and is less than or equal to itself. This is called the reflexive property.

• If we search for two elements from \(B\) where the first divides the second and the second divides the first, then we are forced to choose the two numbers to be the same. In other words, no two different numbers are related in both directions. The reader can verify that a similar fact is true for the relation \(\leq \) on \(B\text{.}\) This is called the antisymmetric property.

• Next if we choose three values (not necessarily distinct) from \(B\) such that the first divides the second and the second divides the third, then we always find that the first number divides the third. Again, the same is true if we replace “divides” with “is less than or equal to.” This is called the transitive property.

Relations that satisfy these properties are of special interest to us. Formal definitions of the properties follow.

An equivalent condition for antisymmetry is that if \(a R b\) and \(b R a\) then \(a = b\text{.}\) You are encouraged to convince yourself that this is true. This condition is often more convenient to prove than the definition, even though the definition is probably easier to understand.

A word of warning about antisymmetry: Students frequently find it difficult to understand this definition. Keep in mind that this term is defined through an “If...then...” statement. The question that you must ask is: Is it true that whenever there are elements \(a\) and \(b\) from \(A\) where \(a R b\) and \(a \neq b\text{,}\) it follows that \(b\) is not related to \(a\text{?}\) If so, then the relation is antisymmetric.

Another way to determine whether a relation is antisymmetric is to examine (or imagine) its digraph. The relation is not antisymmetric if there exists a pair of vertices that are connected by edges in both directions.

Subsection 10.3.2 Partial Orderings

Not all relations have all three of the properties discussed above, but those that do are a special type of relation.

Figure 10.2.6 is helpful insofar as it reminds us that each set is a subset of itself and shows us at a glance the relationship between the various subsets in \(\mathcal{P} (\{1,2\})\text{.}\) However, when a relation is a partial ordering, we can streamline a graph like this one. The streamlined form of a graph is called a Hasse diagram or ordering diagram. A Hasse diagram takes into account the following facts.

• By the reflexive property, each vertex must be related to itself, so the arrows from a vertex to itself (called “self-loops”) are not drawn in a Hasse diagram. They are simply assumed.
• By the antisymmetry property, connections between two distinct elements in a directed graph can only go one way, if at all. When there is a connection, we agree to always place the second element above the first (as we do above with the connection from \(\{1\}\) to \(\{1,2\}\)). For this reason, we can just draw a connection without an arrow, just a line.
• By the transitive property, if there are edges connecting one element up to a second element and the second element up to a third element, then there will be a direct connection from the first to the third. We see this in Figure 10.2.6 with \(\emptyset\) connected to \(\{1\}\)\(\)and then \(\{1\}\) connected to \(\{1,2\}\text{.}\) Notice the edge connecting \(\emptyset\) to \(\{1,2\}\text{.}\) Whenever we identify this situation, remove the connection from the first to the third in a Hasse diagram and simply observe that an upward path of any length implies that the lower element is related to the upper one.

Using these observations as a guide, we can draw a Hasse diagram for \(\subseteq\) on \(\{1,2\}\) as in Figure 10.3.6.

Consider the partial ordering relation \(R\) whose Hasse diagram is Figure 10.3.8.

How do we read this diagram? What is \(A\text{?}\) What is \(R\text{?}\) What does the digraph of \(R\) look like? Certainly \(A = \{1,2,3,4,5\}\) and \(1 R 2\text{,}\) \(3 R 4\text{,}\) \(1 R 4\text{,}\) \(1 R 5\text{,}\) etc., Notice that \(1 R 5\) is implied by the fact that there is a path of length three upward from 1 to 5. This follows from the edges that are shown and the transitive property that is presumed in a poset. Since \(1 R 3\) and \(3 R 4\text{,}\) we know that \(1 R 4\text{.}\) We then combine \(1 R 4\) with \(4 R 5\) to infer \(1 R 5\text{.}\) Without going into details why, here is a complete list of pairs defined by \(R\text{.}\)

\begin{equation*} R = \{(1,1),(2,2),(3,3),(4,4),(5,5),(1,3),\\ (1,4),(1,5),(1,2),(3,4),(3,5),(4,5),(2,5)\} \end{equation*}

A digraph for \(R\) is Figure 10.3.9. It is certainly more complicated to read and difficult to draw than the Hasse diagram.

A classic example of a partial ordering relation is \(\leq \) on the real numbers, \(\mathbb{R}\text{.}\) Indeed, when graphing partial ordering relations, it is natural to “plot” the elements from the given poset starting with the “least” element to the “greatest” and to use terms like “least,” “greatest,” etc. Because of this the reader should be forewarned that some texts use the symbol \(\leq\) for arbitrary partial orderings. This can be quite confusing for the novice, so we continue to use generic letters \(R\text{,}\) \(R\text{,}\) etc.

Subsection 10.3.3 Equivalence Relations

Another common property of relations is symmetry.

Consider the relation of equality defined on any set \(A\text{.}\) Certainly \(a = b\) implies that \(b = a\) so equality is a symmetric relation on \(A\text{.}\)

Surprisingly, equality is also an antisymmetric relation on \(A\text{.}\) This is due to the fact that the condition that defines the antisymmetry property, \(a = b\) and \(a \neq b\text{,}\) is a contradiction. Remember, a conditional proposition is always true when the condition is false. So a relation can be both symmetric and antisymmetric on a set! Again recall that these terms are not negatives of one other. That said, there are very few important relations other than equality that are both symmetric and antisymmetric.

The classic example of an equivalence relation is equality on a set \(A\text{.}\) In fact, the term equivalence relation is used because those relations which satisfy the definition behave quite like the equality relation. Here is another important equivalence relation.

Our next example involves the following fundamental relations on the set of integers.

We observe the following about congruence modulo \(m\text{:}\)

• This relation is reflexive, for if \(a \in \mathbb{Z} \text{,}\) \(m \mid (a-a) \Rightarrow a\equiv_ma \text{.}\)

• This relation is symmetric. We can prove this through the following chain of implications.

  \begin{equation*} \begin{split} a \equiv_m b &\Rightarrow m \mid (a-b)\\ & \Rightarrow \textrm{For some } k \in \mathbb{Z}, a-b = m k \\ & \Rightarrow b-a = m (-k)\\ & \Rightarrow m \mid (b-a)\\ & \Rightarrow b \equiv_m a \end{split}\text{.} \end{equation*}

• Finally, this relation is transitive. We leave it to the reader to prove that if \(a \equiv _mb \) and \(b\equiv _mc\text{,}\) then \(a \equiv _mc\text{.}\)

Frequently, you will see the equivalent notation \(a \equiv b (\textrm{mod } m)\) for congruence modulo \(m\text{.}\)

Consider the relation s described by the digraph in Figure 10.3.15. This was created by randomly selecting whether or not two elements from \(\{a,b,c\}\) were related or not. Convince yourself that the following are true:

• This relation is not reflexive.

• It is not antisymmetric.

• Also, it is not symmetric.

• It is not transitive.

• Is \(R\) an equivalence relation or a partial ordering?

Not every random choice of a relation will be so totally negative, but as the underlying set increases, the likelihood any of the properties are true begins to vanish.