Relations – Foundations of Mathematics

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

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.