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.
- Ordering Relations. Relations which generalize .
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 and is the symbol . Two ordered pairs and are the same iff and .
Definition. The product of sets and is
That is, is the set of all pairs whose first coordinate comes from and whose second coordinate comes from .
We've seen set products before: is the set of all pairs of real numbers, i.e. the Cartesian plane. In fact is sometimes called the Cartesian product of and . (Both the plane and the more general product are named for the philosopher and mathematician Rene Descartes.)
Since is a set, we should ask, what does it mean to be an element of ? That is, let's unpack . This should mean:
But and are new variables, so they require new quantifiers. In fact,
Theorem. For any sets , , , and ,
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 . To this end, let . So and . Then there are and with . On the other hand, there are and with . Since , we see that and . So , hence . Similarly, , so . Thus .
Now we'll show the other inclusion, . To this end, let . Then there are and with . Since , we know and . Similarly and . So and , hence .
Exercise. Is commutative or associative? That is, is either of the following equalities automatic?
There's one more thing to note about set products, which is why we use the word product at all:
Theorem. If has exactly elements and has exactly elements, then has exactly elements.
That is, the size of the product is the product of the sizes.