Basics of Relations – Foundations of Mathematics

What's a relation?

Definition. A relation from the set $A$ to the set $B$ is a(ny) subset of $A\times B$ . We call $A$ the source and $B$ the target or codomain of the relation.

A relation from $A$ to $A$ is called a {\em relation on $A$ }.

If $R$ is a relation from $A$ to $B$ , and $(x,y)\in R\subseteq A\times B$ , we say that $x$ is $R$ -related to $y$ , and sometimes write $x\operatorname{R}y$ . If $(x,y)\notin R$ , we sometimes write $x\cancel{\operatorname{R}} y$ .

The notation $x\operatorname{R}y$ is called infix notation; the notation $(x,y)\in R$ is called set notation or postfix notation or reverse Polish notation. The term infix comes from linguistics. An infix is a grammatical feature that gets inserted into the middle of a word, as opposed to the beginning or the end. The examples of this in English are almost all obscenities. The term reverse Polish refers to the school of logicians founded by Jan Łukasiewicz and Kazimierz Twardowski at the Universities of Lwów and Warsaw in the early 1900s.

Exercise. A relation on $\mathbb{R}$ is a subset of $\mathbb{R}\times\mathbb{R}$ . What is a relation on $\mathbb{R}\times\mathbb{R}$ ?

Eg. The identity relation $I_A$ on any set $A$ is defined by:

$I_A=\left\{(a,a)\middle | a\in A\right\}$

Then $x\operatorname{I_A}y$ means $(x,y)\in I_A$ , i.e. that there is some $a\in A$ with $(x,y)=(a,a)$ . But then $x=a$ and $y=a$ , so $x=y$ .

Thus the identity relation is nothing more than equality.

If we draw a picture of the identity relation, we get a diagonal line, so the identity relation is sometimes also called the diagonal relation on $A$ .

Exercise. If $A$ has exactly $n$ elements and $B$ has exactly $m$ elements, how many relations are there from $A$ to $B$ ?

Since relations are sets, we can do set operations to them (although this is usually not so interesting), for example:

Eg. Consider the relation on $\mathbb{R}$ given by:

$LT=\left\{(x,y)\middle| x<y\right\}$

Then $x \operatorname{(LT)^c} y$ iff $(x,y)\in (LT)^c$ iff $(x,y)\notin LT$ iff $x\geq y$ .

We could summarize this all by saying the complement of the less-than relation is the greater-than-or-equal-to relation.

Note that ${}^c$ has a fairly natural meaning in terms of relationships: to say two elements are $R^c$ -related is precisely to say they are not $R$ -related.

Exercise. Explain what the intersection and union of two relations would mean.

Domain, Range, and Fibers of a Relation

To any relation $R$ from a set $A$ to a set $B$ , we can associate the following sets:

Definition. The domain of $R$ is the set of its first coordinates. That is:

$Domain(R)=\left\{x\middle\vert \exists y:(x,y)\in R\right\}$

The range of $R$ is the set of its second coordinates. That is:

$Range(R)=\left\{y \middle\vert \exists x:(x,y)\in R\right\}$

Observe that the domain is automatically a subset of the source $A$ , and the range is automatically a subset of the target $B$ . We can also focus on particular first coordinates:

Definition. The horizontal fiber at $d\in B$ is