## Relations

[callout headingicon=”noicon” textalign=”textleft” type=”basic”]Society does not consist of individuals, but expresses the sum of interrelations, the relations within which these individuals stand.

Karl Marx, *Grundrisse der Kritik der Politischen Ökonomie*

[/callout]

If two young people are seeing each other romantically, we usually say something like Frank and Jeremy are *in a relationship*. The word *in* suggests we should use the notion of set membership to record what a relationship means.

### Overview of Relations

**Relations and Set Products (this page)**Relations are*sets of*pairs, so we must think about*sets of pairs.***Basics of Relations.****Operations on Relations.**Relations can be combined in interesting ways.**Graphing Relations.**We can draw visual representations of relations in several different ways.**Properties of Relations.****Equivalence Relations.**Relations which generalize $=$.**Equivalence Classes**.- Partitions.

**Ordering Relations.**Relations which generalize $\leq$.

### Pairs of Elements, Products of Sets

Since a relation is a set of pairs, let’s try to understand sets of pairs.

**Definition. **The *ordered pair with coordinates $a$ and $b$* is the symbol $(a,b)$. Two ordered pairs $(a,b)$ and $(x,y)$ are the same iff $a=x$ and $b=y$.

**Definition. **The *product* of sets $A$ and $B$ is $$A\times B=\left\{(x,y)\middle\vert x\in A \wedge y\in B\right\}$$

That is, $A\times B$ is the set of all pairs whose first coordinate comes from $A$ and whose second coordinate comes from $B$.

We’ve seen set products before: $\mathbb{R}\times\mathbb{R}=\left\{(x,y)\middle\vert x\in \mathbb{R},y\in\mathbb{R}\right\}$ is the set of all pairs of real numbers, i.e. the Cartesian plane. In fact $A\times B$ is sometimes called the *Cartesian product* of $A$ and $B$. (Both the plane and the more general product are named for the philosopher and mathematician Rene Descartes.)

Since $A\times B$ is a set, we should ask, what does it mean to be an element of $A\times B$? That is, let’s unpack $t\in A\times B$. This should mean: $$t=(x,y)$$ But $x$ and $y$ are new variables, so they require new quantifiers. In fact,

$t\in A\times B$ means $\exists x\in A:\exists y\in B: t=(x,y)$

**Theorem. **For any sets $A$, $B$, $C$, and $D$,

- $\left(A\times B\right)\cap\left(C\times D\right)=\left(A\cap C\right)\times\left(B\cap D\right)$
- $\left(A\times B\right)\cup\left(C\times D\right)\subseteq\left(A\cup C\right)\times\left(B\cup D\right)$

Note that the second clause is not set equality, merely subset. This is not an omission.

**Proof. **We’ll prove the first clause and leave the second as an exercise.

First we’ll show that $\left(A\times B\right)\cap\left(C\times D\right)\subseteq \left(A\cap C\right)\times\left(B\cap D\right)$. To this end, let $x\in\left(A\times B\right)\cap\left(C\times D\right)$. So $x\in A\times B$ and $x\in C\times D$. Then there are $a\in A$ and $b\in B$ with $x=(a,b)$. On the other hand, there are $c\in C$ and $d\in D$ with $x=(c,d)$. Since $(a,b)=(c,d)$, we see that $a=c$ and $b=d$. So $a\in C$, hence $a\in A\cap C$. Similarly, $b\in D$, so $b\in B\cap D$. Thus $x=(a,b)\in (A\cap C)\times(B\cap D)$.

Now we’ll show the other inclusion, $\left(A\cap C\right)\times\left(B\cap D\right)\subseteq \left(A\times B\right)\cap\left(C\times D\right)$. To this end, let $x\in \left(A\cap C\right)\times\left(B\cap D\right)$. Then there are $y\in A\cap C$ and $z\in B\cap D$ with $x=(y,z)$. Since $y\in A\cap C$, we know $y\in A$ and $y\in C$. Similarly $z\in B$ and $z\in D$. So $x=(y,z)\in A\times B$ and $x=(y,z)\in C\times D$, hence $x\in \left(A\times B\right)\cap \left(C\times D\right)$. $\Box$

**Exercise. **Is $\times$ commutative or associative? That is, is either of the following equalities automatic?

$$A\times B = B\times A$$

$$\left(A\times B\right)\times C = A\times \left( B\times C\right)$$

There’s one more thing to note about set products, which is why we use the word *product* at all:

**Theorem.** If $A$ has exactly $n$ elements and $B$ has exactly $m$ elements, then $A\times B$ has exactly $n\cdot m$ elements.

That is, the size of the product is the product of the sizes.