## Basics of Relations

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 $$A_d^R=\left\{x\middle\vert (x,d)\in R\right\}$$The *vertical fiber at $c\in A$ *is $$B_c^R=\left\{y\middle\vert (c,y)\in R \right\}$$

That is, the horizontal fiber is all the first coordinates with $d$ as their corresponding second coordinate.

**Theorem.** The domain and the range are unions of the corresponding fibers. That is,

- $Domain(R)=\bigcup_{d\in B} A_d^R$
- $Range(R)=\bigcup_{c\in A} B_c^R$