• e.g. if we use $A=\{1,2,3,4\}$ and $B=\{a,b,c\}$, we could define a relation $R=\{(1,a),(1,c),(2,b),(3,b)\}$.
• Then we would say that $(1,c)$ has this relation, of that $1$ is related to $c$ by $R$.
• It is also common to write “$1 \mathop{R}c$” to indicate that two elements are related, or “$2 \mathop{\not R}c$” to indicate that they aren't.

• The set of values in the relation are $\{(i,j)\mid i,j\in \mathbf{R}, i<j\}\subseteq \mathbf{R}\times \mathbf{R}$.
• The $1< 2$ and $2\not < 1$ notation makes a lot more sense for the $<$ symbol.
• For consistency, we would also have to allow ourselves to write this, even though it looks insane: $$(\text{<}) = \{(i,j)\mid i,j\in \mathbf{R}, i<j\}$$
• I'd probably rather make up some notation like $R_{<} = \{\cdots\}$ if necessary.

• A function is a relation where we're only allowed to have one “result”.
• A relation $R$ is a function if $(a,b_1),(a,b_2)\in R$ implies $b_1=b_2$.
• For a function $f:A\rightarrow B$, we could define it as a relation $f = \{(a,b)\mid a\in A, b=f(a)\}$.

• Call this “a relation on the set $A$”.
• e.g. less-than is a relation on $\mathbf{R}$.

• We defined it as $a\mid b$ if there is an integer $c$ such that $b=ac$.
• Or we could now think of the set $\{(a,b)\mid a,b\in\mathbf{Z}, b=ac\text{ for an integer }c\}$.

• Relations that have some particular properties are common, and can be more useful.
• We're generally concerned about relations on a particular set here: from a set to itself.

• That is, every element is related to itself.
• For example $\le$ is reflexive, but $<$ is not.
• The relation “divides” is reflexive since every integer divides itself.
• A relations is irreflexive if $(a,a)\not\in R$ for all $a\in A$.
• The relation $<$ is irreflexive.

• A relation is antisymmetric if $(a,b)\in R$ and $(b,a)\in R$ only when $a=b$.
• For example, $<$, $\le$, and divisibility are all antisymmetric.
• The “equals” ($=$) relation is symmetric.
• Congruence modulo $k$ is symmetric. That is, $a$ and $b$ are related iff $a\equiv b\text{ (mod }k\text{)}$ is symmetric.
• Some relations are neither symmetric nor antisymmetric: the relation $\{(1,1),(1,2)\}$ is neither.
• … it's also neither reflexive nor irreflexive.

• $\le$ and $<$ are both transitive.
• So is divisibility: if $a\mid b$ and $b\mid c$ then there are integers so that $b=db$ and $c=eb$ so $c=(de)a$ and $a\mid c$.
• A relation that isn't transitive: $a\mathop{R}b$ iff $b=a+1$. Then $2\mathop{R}3$ and $3\mathop{R}4$ but $2\mathop{\not R}3$
• Inequality ($\ne$) isn't transitive: $4\ne 5$ and $5\ne 4$ but $4=4$.

• $R$ is definitely not reflexive. It's probably irreflexive since no airline would fly from a city and back (without stopping). [Unless you count sightseeing flights or something.]
• $R$ is symmetric: if there's a flight from Shanghai to Vancouver, then there's a flight from Vancouver to Shanghai. [Right? I don't know of any counterexamples.]
• $R$ is not transitive: there is a flight from Hangzhou to Beijing and Beijing to Vancouver, but none from Hangzhou to Vancouver.

• There are $2^{n^2}$ relations on $A$ since there are $n^2$ elements of $A\times A$, and any subset is a relation.
• How many are reflexive?
  • Of the $n^2$ elements of $A\times A$, we must take the $n$ values $(a,a)$ in the subset. The others can be chosen freely.
  • So, $2^{n^2-n}$.
• How many are symmetric?
  • If we can decide on an order for the $n$ elements, we can choose the “smaller” elements first (like $(a,b)$) and that implies the other order must also be included (like $(b,a)$).
  • So, how many pairs $(a,b)$ can we choose where $a\le b$? There are $n(n+1)/2$. We choose from those, then since the relation is symmetric, we know we must include/exclude $(b,a)$.
  • So, $2^{n(n+1)/2}$ relations.
• How many are transitive?
  • No known formula. (A006905)

• $R_{\le}\cap R_{\ge}$ is the equality relation, $R_{=}$.
• $R_{<}\cup R_{>}$ is the inequality relation, $R_{\ne}$.
• $R_{\le}-R_{=}=R_{<}$.

• That is, we we have two relations $R_1\subseteq A\times B$ and $R_2\subseteq B\times C$, then we can define $A\circ B$ with elements $(a,c)$ where there is a $b\in B$ such that $(a,b)\in R_1$ and $(b,c)\in R_2$.

• If we compose it with “greater than or equal” over the integers, $R\circ R_{\ge}$, we get $R_{>}$ since $m\ge n$ iff $m+1 > n$ for integers $m,n$.
• If we compose it with itself, $R\circ R$, we get “plus two”: $a\mathop{(R\circ R)}b$ iff $b=a+2$.

• We can define $R^n$ as $R^1=R$ and $R^{n+1}=R^n\circ R$.
• So $R^3=(R\circ R)\circ R$ and $R^4=((R\circ R)\circ R)\circ R$.

• $R^2$ is the cities you can get to in exactly two flights. So, $(\text{Hangzhou},\text{Vancouver})\in R^2$ (or we could write $\text{Hangzhou} \mathop{R^2} \text{Vancouver}$, but that's awkward).
• $(\text{Hangzhou},\text{Shanghai})\in R^2$ since $(\text{Hangzhou},\text{Beijing}),(\text{Beijing},\text{Shanghai})\in R^2$. We haven't said anything about needing two flights.
• $R^2-R$ is the relation where you must take two flights (there is no direct route).
• $R\cup R^2 \cup R^3\cup\cdots$ are cities that you can fly between, taking any number of flights.

Theorem: A relation on a set is transitive if and only if $R^n\subseteq R$ for all $n\ge 1$.

Proof: First assume that $R^n\subseteq R$ for all $n\ge 1$ (to show the “if” part). If we have $(a,b),(b,c)\in R$ then $(a,c)\in R^2$. From the assumption, $(a,c)\in R$, so $R$ is transitive.

Now assume that $R$ is transitive. For $n=1$, $R^1\subseteq R$ by definition. We can show that $R^n\subseteq R$ for larger $n$ by induction.

Assume for induction that $R^n\subseteq R$. If we have an element $(a,b)\in R^{n+1}=R^n\circ R$ then there is a $c$ such that $(a,c)\in R^{n}\subseteq R$ and $(c,b)\in R$. Since $R$ is transitive and we have two elements of $R$, we know that $(a,b)\in R$. Thus $R^{n+1}\subseteq R$.

By induction, $R^{n}\subseteq R$ for all $n$.∎

• For example, the inverse of “less than” is “greater than”, since $a<b$ iff $b>a$.

Theorem: A relation is symmetric iff $R=R^{-1}$.

Proof: First consider a symmetric relation $R$ and any $(a,b)\in R$. Since $R$ is symmetric, we know that $(b,a)\in R$. Thus, we have $R\subseteq R^{-1}$.

Now take any $(a,b)\in R^{-1}$. By definition, $(b,a)\in R$ and by symmetry, $(a,b)\in R$. So, $R^{-1}\subseteq R$ and we have $R=R^{-1}$.

Finally, suppose $R=R^{-1}$. For any $(a,b)\in R$, we know $(b,a)\in R^{-1}=R$. So, $R$ is symmetric.∎

• We just remove the restriction that a value must map onto a unique image.

• We could have defined a predicate $P(a,b)$ to be true iff $a<b$.
• Or we could define a relation that contains all $(a,b)$ where $a<b$.
• The predicates could be combined with logical operators ($\vee,\wedge,\ldots$), and the relations with set operators ($\cup,\cap,\ldots$).
• The results are fundamentally the same, but one or the other might be easier notation to work with.
• In particular, things like “less than” are usually thought of as relations, so there are plenty of theorems you'll find using that notation.

• That is, functions in a programming language that return true or false.
• e.g. a Java method:

  public boolean lessthan(int a, int b) {
    return a<b;
  }

• e.g. in Haskell you can actually define a new operator that works like a relation:

  (<) :: Int -> Int -> Bool
  (<) a b = not (a>b)
  5 < 6                  -- uses the above code to get a result

• We can represent this as an $m\times n$ matrix, which we'll usually refer to as $\mathbf{M}_R$.
• The $i,j$ entry of the matrix will be 1 if $(a_i,b_j)\in R$ and 0 otherwise.
• This gives us an efficient way to represent arbitrary relations in a computer: we need $mn$ bits to store everything we need.

• The order doesn't matter, as long as we pick one and stay with it.

• So, it is a mirror image across the diagonal.
• In other words, it will be its own transpose: $\mathbf{M}_R=(\mathbf{M}_R)^t$.

• Recall that $R\circ S$ has elements $(a,c)$ where there is a $b$ such that $(a,b)\in R$ and $(b,c)\in S$.
• So, element $(i,j)$ of the matrix $\mathbf{M}_{R\circ S}$ will be one when there is a $k$ where $(i,k)$ and $(k,j)$ are both one.
• That is, when $(a_{i1}\wedge a_{1j})\vee (a_{i2}\wedge a_{2j})\vee\cdots \vee (a_{in}\wedge a_{nj})$.
• The textbook uses the notation $\mathbf{M}_{R\circ S}=\mathbf{M}_{R}\odot \mathbf{M}_{S}$ for this operation.

• We can tell that the relation isn't reflexive: the $2,2$ entry is missing.
• It is symmetric: transposing it would not change it.
• The relation $R^2$ has the matrix $$\mathbf{M}_{R^2}=\begin{bmatrix}1&1&1&0 \\ 1&1&1&0 \\ 1&1&1&0 \\ 0&0&0&1 \end{bmatrix}$$
• That is also the same as $\mathbf{M}_{R^3}$, $\mathbf{M}_{R^4}$, …

• If we have vertices $a$ and $b$, then an edge that connects $a$ to $b$ is $(a,b)$.
• The edges have a direction: $(a,b)\ne(b,a)$.
• That's why it's a directed graph.

• Each dot is a vertex.
• Each arrow is an edge.

• Vertices represent the elements of the set(s).
• Edges represent the elements of the relation.
• The above digraph is the same relation as the matrix example: $$\mathbf{M}_R=\left[\begin{smallmatrix}1&0&1&0 \\ 0&0&1&0 \\ 1&1&1&0 \\ 0&0&0&1 \end{smallmatrix}\right]$$

• If a relation is reflexive, there will be a loop on each vertex.
• If it's irreflexive, there will be none.
• If it is symmetric, each arrow will be accompanied by another in the opposite direction (like between $b$ and $c$ above).
• It's antisymmetric if that never happens.
• If it is transitive, every pair of adjoining edges will also have another that does the same thing in one step, like this:

• The inverse of a relation can be found by just reversing each arrow.

• That's probably not as interesting as for relations in $A\times A$.

• For example, we could have a relation on $\mathbf{Z}\times\mathbf{Z}\times\mathbf{Z}^{+}$ consisting of triples $(a,b,m)$ where $a\equiv b\ (\text{mod } m)$.
• Then $(3,18,5)$ and $(4,-5,9)$ are in this relation, but $(1,2,5)$ and $(9,100,10)$ are not.

• For example, a database table might have the following data in each row: student number, name, email address.
• Then the table basically defines a relation on $\text{integer}\times \text{strings}\times \text{strings}$.

• For example, we could select form the above relation all people who have an “@zju.edu.cn” email address.
• Or select all entries with student number 3110012345.

• That is, it selects only some of the original sets from the relation.
• If we only care about student number and email, records like (3110012345, "Student Name", "student@example.com") would be projected to (3110012345, "student@example.com").
• That is the projection $P_{1,3}$ on the relation.
• In database terminology, we select only certain columns.

• For example, suppose we have another relation on student number, course, and grade.
• We could join the student number, name, email address relation to this on the student number.
• The result would be a list of all possible combinations where the student numbers match in both relations.
• We would get a relation with values for student number, name, email address, course, and grade.

• Several courses, really.
• We would like to be able to ask questions like “which elements of the relation have some particular property?” and get the answers quickly ($O(\log n)$ time or better).
• SQL (Structured Query Language) gives us syntax to perform the operations described above.
• … as well as to manipulate the data (insert, update, delete) in the relation.