Properties of Relations

Relations on Sets

The Inverse of a Relation

Directed Graph of a Relation

When a relation $R$ is defined on a set $A$, the arrow diagram of the relation can be defined so it becomes a directed graph. Instead of representing $A$ as two separate sets of points, represent $A$ only once, and draw an arrow from each point of $A$ to each related point.

$N$-ary Relations and Relational Databases

A special group of relations, called $n$-ary relations, form the mathematical foundation for relational database theory. Just as a binary relation is a subset of a Cartesian product of two sets, an $n$-ary relation is a subset of a Cartesian product of $n$ sets.

The following is a radically simplified version of a database that might be used in a hospital.

Let $A_1$ bet a set of positive integers, $A_2$ a set of alphabetic character strings, $A_3$ a set of numeric character strings, and $A_4$ a set of alphabetic character strings.

Define a quartenary relation $R$ on $A_1 \times A_2 \times A_3 \times A_4$ as follows:

At a particular hospital, this relation might contain the following 4-tuples:

• (011985, John Schmidt, 020719, asthma)
• (574329, Tak Kurosawa, 011419, pneumonia)
• (466581, Mary Lazars, 010319, appendicitis

In discussions of relational databases, the $n$-tuples are normally thought of as being written in tables. Each row of the table corresponds to one $n$-tuple, and the header for each column gives the descriptive attribute for the elements in the column.

For example, in the database language SQL, if the above database is denoted $S$, the result of the query:

SELECT Patient_ID#, Name
FROM S
WHERE Admission_Date = 010319

Is obtained by taking the intersection of the set $A_1 \times A_2 \times \{010319\} \times A_4$ with the database and then projecting onto the first two coordinates.

Reflexivity, Symmetry and Transitivity

Now consider what it means for a relation not to have one of the properties defined previously.

1. $R$ is not reflexive: there is an element $x$ in $A$, such that $x \not R x$
2. $R$ is not symmetric: there are elements $x$ and $y$ in $A$, such that $x R y$ but $y \not x$.
3. $R$ is not transitive: there are elements $x$, $y$ and $z$ in $A$, such that $x R y$ and $y R z$ but $x \not z$.

So you can show that a relation does not have one of the properties by finding a counterexample.

Properties of Relations on Infinite Sets

Suppose a relation $R$ is defined on an infinite set $A$. To prove the relation is reflexive, symmetric, or transitive use the definitions of $A$ and $R$. For instance, for the symmetry on the equality relation on the set of real numbers:

Sometimes a property is “universally false” in the sense that it is false for every element of its domain. It follows immediately, of course, that the property is false for each particular element of the domain and hence counterexamples abound. In such a case, it may seem more natural to prove the universal falseness of the property rather than to give a single counterexample.

The Transitive Closure of a Relation

Generally speaking, a relation fails to be transitive because it fails to contain certain ordered pairs. For example, if $(1, 3)$ and $(3, 4)$ are in a relation $R$, then the pair $(1, 4)$ must be in $R$ if $R$ is to be transitive.

Roughly speaking, the relation obtained by adding the least number of ordered pairs to ensure transitivity is called the transitive closure of the relation. More precisely, the transitive closure of a relation is the smallest transitive relation that contains the relation.

Given a relation $R$ on a set $A$ whose directed graph is:

Then the directed graph for the transitive closure $R^{t}$ would be:

Equivalence Relations

The idea of grouping together things that “look different but are really the same” is the central idea of equivalence relations.

The Relation Induced by a Partition

Proof that $R$ is reflextive: Suppose $x \in A$. Since $A_1, A_2, \cdots, A_n$ is a partition of $A$, it follows that $x \in A_i$ for some $i$, and so the statement:

There is a set $A_i$ of the partition such that $x \in A_i$ and $x \in A_i$

is true. Thus, by definition of $R$, $x R x$.

Proof that $R$ is symmetric: Suppose that $x$ and $y$ are elements of $A$ such that $x R y$. Then

There is a subset $A_i$ of the partition such that $x \in A_i$ and $y \in A_i$

by definition of $R$. It follows that the statement

There is a subset $A_i$ of the partition such taht $y \in A_i$ and $x \in A_i$

is also true. Hence, by definition of $R$, $y R x$.

Proof that $R$ is transitive: Suppose $x$, $y$ and $z$ are in $A$ and $x R y$ and $y R z$. By definition of $R$, there are subsets $A_i$ and $A_j$ of the partition such that:

Suppose $A_i \neq A_j$. Then $A_i \cap A_j = \emptyset$ since $\{A_1, A_2 \cdots, A_n\}$ is a partition of $A$. But $y$ is in $A_i$ and $y$ is in $A_j$ also. Hence $A_i \cap A_j \neq \emptyset$. Thus $A_i = A_j$. It follows that $x, y$ and $z$ are all in $A_i$, and so, in particular

Thus $x R z$ by definition of $R$.

Equivalence Relations

When several equivalence relations on a set are under discussion, the notation $[a]_R$ may be used to denote the equivalence class of $a$ for the relation $R$.

Proof that $[a] \subseteq [b]$. Let $x \in [a]$. Then

by definition of class. But

by hypothesis. Thus, by transitivity of $R$

Hence

by definition of class

Proof that $[b] \subseteq [a]$. Let $x \in [b]$. Then

by definition of class. But

by hypothesis. Since $R$ is symmetric

Thus, by transitivity of $R$, given $x R b$ and $b R a$

Hence

by definition of class

Since $[a] \subseteq [b]$ and $[a] \subseteq [b]$, it follows that $[a] = [b]$.

The previous statement has the form:

We will prove the logically equivalent statement:

That is, we will prove:

If $A$ is a set, $R$ is an equivalence relation on $A$, $a$ and $b$ are elements of $A$ and $[a] \cap [b] = \emptyset$, then $[a] = [b]$.

Proof. Suppose $A$ is a set, $R$ is an equivalence relation on $A$, $a$ and $b$ are elements of $A$, and

Since $[a] \cap [b] \neq \emptyset$, there exists an element $x$ in $A$ such that $x \in [a] \cap [b]$. By definition of intersection

and so

by definition of class. Since $R$ is symmetric and $x R a$, then $a R x$. But $R$ is also transitive, and so, since $a R x$ and $x R b$,

Now $a$ and $b$ satisfy the hypothesis of the previous lemma, hence:

Proof Suppose $A$ is a set and $R$ is an equivalence relation on $A$. For notational simplicity, we assume that $R$ has only a finite number of distinct equivalence classes, which we denote

where $n$ is a positive integer (when the number of classes is infinite, the proof is identical except for notation).

Proof that $A = A_1 \cup A_2 \cup \cdots \cup A_n$

To show that $A \subset A_1 \cup A_2 \cup \cdots \cup A_n$ suppose $x$ is any element of $A$.

• By reflexivity of $R$, $x R x$. This implies that $x \in [x]$ by defintion of class.
• Since $x$ is in some equivalence class, it must be in one of the distinct equivalence classes $A_1, A_2, \cdots, A_n$.
• Thus $x \in A_i$ for some index $i$, and hence $x \in A_1 \cup A_2 \cup \cdots \cup A_n$ by definition of union.

To show that $A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A$ suppose $x \in A_1 \cup A_2 \cup \cdots \cup A_n$.

• Then $x \in A_i$ for some $i = 1, 2, \cdots, n$ by definition of union.
• Now each $A_i$ is an equivalence class of $R$, and equivalence classes are subsets of $A$. Hence $A_i \subseteq A$ and so $x \in A$.

Since $A \subseteq A_1 \cup A_2 \cup \cdots \cup A_n$ and $A_1 \cup A_2 \cup \cdots \cup A_n \subseteq A$, then by definition of set equality $A = A_1 \cup A_2 \cup \cdots \cup A_n$.

Proof that the distinct classes of $R$ are mutually disjoint. Suppose that $A_i$ and $A_j$ are any two distinct equivalence classes of $R$. Since $A_i$ and $A_j$ are distinct, then $A_i \neq A_j$. And since $A_i$ and $A_j$ are equivalence classes of $R$, there must exist elements $a$ and $b$ in $A$ such that $A_i = [a]$ and $A_j = [b]$. By the previous lemma

Now $[a] \neq [b]$ because $A_i \neq A_j$ and hence $[a] \cap [b] = \emptyset$. Thus $A_i \cap A_j = \emptyset$, and so $A_i$ and $A_j$ are disjoint.

Note that if $a$ is any element of an equivalence class $S$, then $S = [a]$. Hence any element of an equivalence class is a representative of that class.

Congruence Modulo $n$

Modular Arithmetic with Applications to Cryptography

Cryptography is the study of methods for sending secret messages. It involves encryption, in which a message, called plaintext, is converted into a form, called ciphertext, that is sent over a channel possibly open to view by outside parties. The receiver of the ciphertext uses decryption to convert the ciphertext back into plaintext.

With public-key cryptography, a potential recipient of encrypted messages openly distributes a public key containing the encryption information. However, knowledge of the public key provides virtually no clue about how messages are decrypted.

The first public-key cryptography system was developed in 1976–1977 by three mathematician/computer scientists working at M.I.T.: Ronald Rivest, Adi Shamir, and Leonard Adleman. In their honor it is called the RSA cipher.

Properties of Congruence Modulo $n$

Proof We will show that $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (4) \Rightarrow (5) \Rightarrow (1)$. It will follow by the transitivity of if-then that all five statements are equivalent.

Let $a, b$ and $n$ be any integers with $n > 1$.

Proof that $(1) \Rightarrow (2)$: Suppose $n | (a - b)$. By definition of congruence modulo $n$, we can immediately conclude that $a \equiv b (\text{ mod } n)$.

Proof that $(2) \Rightarrow (3)$: Suppose $ a \equiv b (\text{ mod } n)$. By definition of congruence modulo $n$, $n | (a - b)$. Thus, by definition of divisibility $a - b = kn$ for some integer $k$ and thus $a = kn + b$.

Proof that $(3) \Rightarrow (4)$: Suppose that $a = b + kn$ for some integer $k$. Use the quotient remainder theorem to divide $a$ by $n$ to obtain

where $q$ and $r$ are integers and $0 \neq r < n$. Substituting $b + kn$ for $a$

Now since $0 \leq r < n$, the uniqueness property of the quotient-remainder theorem guarantees that $r$ is also the remainder obtained when $b$ is divided by $n$. Thus $a$ and $b$ have the same remainder when divided by $n$.

Proof that $(4) \Rightarrow (5)$: Suppose that $a$ and $b$ have the same remainder when divided by $n$. It follows immediately from the definition of the $\text{ mod }$ function that $a \text{ mod } n = b \text{ mod } n$.

Proof that $(5) \Rightarrow (1)$: Suppose that $a \text{ mod } n = b \text{ mod } n$. By definition of the $\text{mod }$ function, $a$ and $b$ have the same remainder when divided by $n$. Thus, by the quotient remainder theorem, we can write

where $q_1, q_2$ and $r$ are integers and $0 \neq r < n$.

It follows that

Therefore, since $q_1 - q_2$ is an integer, $n | (a - b)$.

Proof. Suppose $n$ is an integer with $n > 1$. We must show that the congruence modulo $n$ is reflexive, symmetric and transitive.

Proof of reflexivity: Suppose that $a$ is any integer, we must show that $a \equiv a \text{ mod n}$. By definition of congruence modulo $n$ this means $n | (a - a)$, that is $(a - a) = nq \Leftrightarrow 0 = n 0$. Thus $a \equiv a \text{ mod } n$.

Proof of symmetry: Suppose $a$ and $b$ are any two integers such that $a \equiv b \text{ mod } n$, we must show $b \equiv a \text{ mod }n$. By definition of congrunce modulo $n$

If we multiply on both sides by $-1$

And, by definition of congrunce modulo $n$ $b \equiv a \text{ mod } n$.

Proof of transitivity: Let $a, b, c \in \mathbb{R}$ such that $a \equiv b \text{ mod } n$ and $b \equiv c \text{ mod } n$. We must show that $a \equiv c \text{mod } n$. By definition of congruence modulo $n$

and

If we solve the first expression for $b$

And substitute $b$ on the second expression

Thus $n | (a - c)$ and $a \equiv c \text{ mod } n$ by definition.

Modular Arithmetic

The most practical use of modular arithmetic is to reduce computations involving large integers to computations involving smaller ones.

Extending the Euclidean Algorithm

Proof Given integers $a$ and $b$, not both zero, and given $d = \text{gcd}(a, b)$, let

Note that $S$ is a nonempty set because:

1. If $a > 0$, then $1 \cdot a + 0 \cdot b \in S$,
2. if $a < 0$, then $(- 1) \cdot a + 0 \cdot b \in S$ and
3. if $a = 0$ then , by assumption, $b \neq 0$ and hence $0 \cdot a + 1 \cdot b \in S$ or $0 \cdot a + (-1) \cdot b \in S$.

Because $S$ is a nonempty subset of positive integers, by the Well-Ordering Principle for the Integers there is a least element $c$ in $S$, By definiton of $S$

We will show that $c \geq d$ and $c \leq d$, therefore $c = d$.

Proof that $c \geq d$:

Because $d = \text{gcd}(a, b)$, by defintion of greatest common divisor, $d | a$ and $d | b$. Hence $a = dx$ and $b = dy$ for some integers $x$ and $y$. Then

Thus, by definition $d | c$ and $c \geq d$.

Proof that $c \leq d$:

Apply the quotient-remainder theorem to the divition of $a$ by $c$ to obtain

Thus for some integers $q$ and $r$ with $0 \leq r < c$

Now $c = as + bt$. Therefore, by substitution

Thus $r$ is a linear combination of $a$ and $b$. If $r > 0$, then $r$ would be in $S$ and so $r$ would be a smaller element of $S$ than $c$, which would contradict the fact that $c$ is the least element of $S$. Hnece $r = =$. Thus

and therefor $c | a$.

An almost identical argument establishes that $c | b$.

Because $c | a$ and $c | b$, $c$ is a common divisor of $a$ and $b$. Hence $c \leq \text{gcd}(a, b) = d$.

We conclude that $c = d$. It follows that $d$, the greatest common divisor of $a$ and $b$, is equal to $as + bt$.

Finding an Inverse Modulo $n$

Proof. Suppose $a$ and $n$ are integers and $\text{gcd}(a, n) = 1$. Then by the previous corollary, there exist integers $s$ and $t$ such that

Thus, by defintion of congrunce modulo $n$

RSA Cryptography

At this point we have developed enough number theory to explain how to encrypt and decrypt messages using the RSA cipher. The effectiveness of the system is based on the fact that although modern computer algorithms make it quite easy to find two distinct large integers $p$ and $q$ that are virtually certain to be prime.

Suppose Alice decides to set up an RSA cipher. She chooses two prime numbers—say, $p = 5$ and $q = 11$—and computes $pq = 55$. She then chooses a positive integer e that is relatively prime to $(p - 1)(q - 1)$. In this case, $(p - 1)(q - 1) = 40$, so she may take $e = 3$ because $3$ is relatively prime to $40$. (In practice, taking $e$ to be small could compromise the secrecy of the cipher, so she would take a larger number than $3$).

The number pair $(pq, e)$ is Alice’s public key, which she may distribute widely. Let us suppose that she encodes letters of the alphabet in a similar way as was done for the Caesar cipher:

Someone who wants to send Alice a message breaks the message into blocks, each consisting of a single letter, and finds the numeric equivalent for each block. The plaintext, $M$, in a block is converted into ciphertext, $C$, according to the following formula:

Note that because $(pq, e)$ is the public key, anyone who has it and knows modular arithmetic can encrypt a message to send to Alice.

To decrypt the message, the decryption key must be computed. It is a number $d$ that is a positive inverse to e modulo $(p - 1)(q - 1)$. The plaintext $M$ is obtained from the ciphertext $C$ by the formula

Note that because $M + kpq \equiv M (\text{ mod } pq)$, $M$ must be taken to be less than $pq$, as in the above example, in order for the decryption to be guaranteed to produce the original message. But because $p$ and $q$ are normally taken to be so large, this requirement does not cause problems.

Proof. Suppose $a, b$ and $c$ are integers $\text{gcd}(a, c) = 1$ and $a | bc$. Then, there exist integers $s$ and $t$ such that

Multiply both sides of this equation by $b$ to obtain

Since $a | bc$, by defition of divisibility there exists an integer $k$ such that

Substituting

Thus $a | b$ by defintion of divisibility.

Proof. Suppose $a, b, c$ and $n$ are any integers $\text{gcd}(c, n) = 1$, and $ac \equiv bc (\text{ mod } n)$. By definition of congruence modulo $n$

And since

Then

Because $\text{gcd}(c, 1) = 1$, we may apply Euclid’s lemma to obtain

and so, by defintion of congruence modulo $n$

Fermat’s Little Theorem

Proof. Suppose $p$ is any prime number and $a$ is any integer such that $p \not | a$. Note that $a \neq 0$ because otherwise $p$ would divide $a$. Consider the set of integers

We claim that no two elements of $S$ are congruent modulo $p$. For suppose $sa \equiv ra (\text{ mod } p)$ for some integers $s$ and $r$ with $1 \neq r < s \leq p - 1$. The by definiton of congruence modulo $p$

But, by our hypothesis $p \not | a$, and because $p$ is prime $\text{gcd}(a, p) = 1$. Thus by Euclid’s lemma $p | (s - r)$, but this is impossible because $0 < s - r < p$.

Consider the function $F$ from $S$ to the set $T = \{1, 2, 3, \cdots, (p - 1)\}$ that sends each element of $S$ to its residue modulo $p$. Then $F$ is one-to-one because not two elements of $S$ re congruent modulo $p$. We state that $F$ is also onto because if a function from one finite set to another is one-to-one, then it is also onto.

Hence $F$ is onto, and so the $p - 1$ residues of the $p - 1$ elements of $S$ are exactly the numbers $1, 2, 3, \cdots, (p - 1)$. It follows that

or equivalently

Now because $p$ is prime, $p$ and $(p - 1)!$ are relatively prime. Thus, by the cancellation theorem for modular congruence

Why does the RSA Cipher Work?

The formula

is supposed to produce the original plaintext message, $M$, when the encrypted message is $C$. Recall that we require:

• $M < pq$ and we know
• $C = M^e \text{ mod } pq$

By substitution

Because if $a \equiv c \text{ mod }(n)$ then $a^m \equiv c^m \text{ mod } n$, let $a = M^e \text{ mod }(pq)$, $c = M^e$ and $d = m$. Then, given

It follows that

Thus, substituting back $M^e \text{ mod } (pq)$ by $C$:

Substituting back $C^d \text{ mod }(pq)$ by $M$:

and because $M < pq$ we can state that $M$ is equal to the residue of dividing $M^{ed}$ by $pq$:

Therefore, to prove the correctness of the RSA cipher we have to show that

by proving

Recall that $d$ was chosen to be a positive inverse for $e$ modulo $(p - 1)(q - 1)$, which exists because $\text{gcd}(e, (p - 1)(q - 1)) = 1$ as we defined $e$ to be a relative prime with respect to $(p - 1)(q - 1)$. In other words, by definition of positive inverse

or equivalently

Therefore

If $p \not | M$, then by Fermat’s Little Theorem, $M^{p - 1} \equiv 1 (\text{ mod } p)$ and so

Given $1^{x} = 1, \forall x \in \mathbb{R}$

Similarly if $q \not | M$, then by Fermat’s Little Theorem, $M^{q - 1} \equiv 1 (\text{ mod } q)$ and so

Thus if $M$ is relatively prime to $pq$,

and

If $M$ is not relatively prime to $pq$, then either $p | M$ or $q | M$.

1. If $p | M$, then $M^{ed} \equiv 0 \equiv M (\text{ mod } p)$
2. If $q | M$, then $M^{ed} \equiv 0 \equiv M (\text{ mod } q)$

Thus, in all cases:

By the definition of congruence of the modulo:

And by defintiion of divisibility

By substitution

Since $q$ and $p$ are distinct prime numbers, Euclid’s lemma gives

Thus, by definition of divisibility

By substitution

Where $u$ is an integer, and so, by defintion of divisibility

By defitnion of congruence of the modulo

Or equivalently

Because $M < pq$, we know that $M$ is equal to the residue of dividing $M^{e}$ by $pq$, that is

And thus, the RSA cipher gives the correct result.

Partial Order Relations

Antisymmetry

By taking the negation of the definition, you can see that a relation $R$ is not antisymmetric if, and only if:

Partial Order Relations

Two fundamental partial order relations are the less than or equal to relation on a set of real numbers and the subset relation on a set of sets.

Lexicographic Order

To figure out which of two words comes first in an English dictionary, you compare their letters one by one from left to right. If all letters have been the same to a certain point and one word runs out of letters, that word comes first in the dictionary.

If all letters up to a certain point are the same and the next letters differ, then the word whose next letter is located earlier in the alphabet comes first in the dictionary. This is the core idea of a lexicographic order.

Hasse Diagrams

A Hasse diagram (after Helmut Hasse, a twentieth-century German number theorist), allows us to define a partial order relation defined on a finite set as a graph.

To obtain a Hasse diagram, proceed as follows:

Start with a directed graph of the relation, placing vertices on the page so that all arrows point upward. Then eliminate:

1. the loops at all the vertices,
2. all arrows whose existence is implied by the transitive property, and
3. the direction indicators on the arrows.

For this relation, the Hasse diagram is as follows:

To recover the directed graph of a relation from the Hasse diagram, just reverse the instructions given previously, using the knowledge that the original directed graph was sketched so that all arrows pointed upward

1. Reinsert the direction markers on the arrows making all arrows point upward.
2. Add loops at each vertex.
3. For each sequence of arrows from one point to a second and from that second point to a third, add an arrow from the first point to the third.

Partially and Totally Ordered Sets

The length of a chain is one less than the number of elements in the chain.

Note that every finite subset of a totally ordered set has both a least element and a greatest element, as every pair of elements are comparable.

Also, a set that is partially ordered with respect to a relation can have at most one greatest element and one least element.

Finally, a greatest element is maximal, but a maximal element need not be a greatest element. Similarly, a least element is minimal, whilst a minimal element need not be a least element. These concepts are a generalization of maximum/minimum absolute/local values of a function.