3.1 Ordered pairs and relations
Definition 3.1. The Cartesian product of sets \(X\) and \(Y\), written \(X\times Y\) and read “\(X\) cross \(Y\)”, is the set of all ordered pairs with first entry from \(X\) and second from \(Y\): \[X\times Y=\{(x,y) : x\in X,\ y\in Y\}.\]
The pairs are ordered: \((1,a)\) and \((a,1)\) are different, and in \(X\times X\) the pairs \((1,2)\) and \((2,1)\) are different too.
Solution. Take each element of the first set with each element of the second, in turn: \[A\times B=\{(1,a),\,(1,b),\,(1,c),\,(2,a),\,(2,b),\,(2,c)\}.\] For \(A\times A\) the same rule applies, with \(A\) playing both parts: \[A\times A=\{(1,1),\,(1,2),\,(2,1),\,(2,2)\}.\]
Count them as a check. If \(|X|=m\) and \(|Y|=n\) then \(|X\times Y|=mn\), because each of the \(m\) first entries can be paired with each of the \(n\) second entries. Here \(|A\times B|=2\times 3=6\) and \(|A\times A|=2\times 2=4\), which matches what was listed.
That check earns its place: \((1,2)\) and \((2,1)\) are both in \(A\times A\) and it is easy to write one and forget the other, leaving three pairs where there should be four.
Definition 3.3. A relation \(R\) from \(X\) to \(Y\) is any subset of \(X\times Y\). If \((x,y)\in R\) we say \(x\) is related to \(y\) and write \(x\,R\,y\).
So a relation is just a rule that links some elements of one set to some elements of another. \(X\) is the input set and \(Y\) the output set.
3.1.1 Classifying relations
Relations are described by how many arrows leave and arrive at each element.
| Type | Description |
| One-to-one | each input goes to one output, and no output is used twice |
| Many-to-one | several inputs share the same output |
| One-to-many | one input goes to several outputs |
| Many-to-many | both of the last two happen |
Example 3.4. Let \(X=\{3,5,7\}\) and \(Y=\{6,10,14\}\) with the relation “is a factor of”. Show it on an arrow diagram and classify it.
Solution. \(3\) divides \(6\); \(5\) divides \(10\); \(7\) divides \(14\). No other pairs work, since \(3\) does not divide \(10\) or \(14\), and so on.
Every input has exactly one arrow out and every output exactly one arrow in, so the relation is one-to-one.
Definition 3.5. For a relation from \(X\) to \(Y\):
- (i).
- the domain is the set of inputs actually used — the first entries of the pairs;
- (ii).
- the range is the set of outputs actually reached — the second entries;
- (iii).
- the co-domain is the whole of \(Y\), whether or not every element of it is reached.
Note 3.6. The range is always a subset of the co-domain, and often a proper one. The co-domain is the set you declared the outputs would come from; the range is what actually came out.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.