1.3 Cartesian products and relations

Editorial note

Equation (1.1) uses the standard Kuratowski pair here. The supplied PDF prints $\{\{a,b\},a\}$, which is not a generally valid encoding. The second identity in Problem 1.8 has $B\times Q$ on the right, correcting the printed $B\times P$.

Ordered pairs and cartesian products

As it stands, there is no concept of order in a set consisting of two elements, since $\{a,b\}=$ $\{b,a\}$ . Frequently we wish to refer to an ordered pair (a, b). Essentially this is a set of two elements $a,b$ where we specify the order in which the two elements are to be written. A purely set-theoretical way of expressing this idea is to adjoin the element a that is to be regarded as the first’ member. An ordered pair $(a,b)$ can thus be thought of as a set consisting of $\{a,b\}$ together with the element a singled out as being the first,

$$(a,b)=\{\{a\},\{a,b\}\}.\text{\hspace{1em}(1.1)}$$

Referenced 1 time

• 1.3 Cartesian products and relationsEquation (1.1) uses the standard Kuratowski pair here. The supplied PDF prints …, which is not a gen…

While this looks a little artificial at first, it does demonstrate how the concept of‘order’ can be defined in purely set-theoretical terms. Thankfully, we only give this definition for illustrative purposes – there is essentially no need to refer again to the formal representation (1.1).

Exercise

From the definition (1.1) show that $(a,b)=(a^{\prime },b^{\prime })\mathrm{iff}a=a^{\prime }\mathrm{and}b=b^{\prime }.$

Similarly, an ordered n-tuple $(a_1,a_2,\dots ,a_n)$ is a set in which the order of the elements must be specified. This can be defined inductively as

$$(a_1,a_2,\dots ,a_n)=(a_1,(a_2,a_3,\dots ,a_n)).$$

Exercise

Write out the ordered triple $(a,b,c)$ as a set.

The (cartesian) product of two sets, $S\times T$ , is the set of all ordered pairs (s, t) where s belongs to $S$ and t belongs to $T$ ,

$$S\times T=\{(s,t)|s\in S\text{ and }t\in T\}.$$

The product of n sets is defined as

$$S_1\times S_2\times \cdots \times S_n=\left\{\left(s_1,s_2,\dots ,s_n\right)\mid s_1\in S_1,s_2\in S_2,\dots ,s_n\in S_n\right\}.$$

If the n sets are equal, $S_1=S_2=\cdot \cdot \cdot =S_n=S,$ , then their product is denoted $S^n$

Exercise

Show that $S\times T=\varnothing$ if and only if $S=\varnothing$ or $T=\varnothing$.

Relations

Any subset of $S^n$ is called an n-ary relation on a set S. For example,

$$\text{ unary relation }\equiv 1\text{-ary relation }=\text{ subset of }S$$ $$\text{ binary relation }\equiv 2\text{-ary relation }=\text{ subset of }{S}^2=S\times S$$ $$\text{ ternary relation }\equiv 3\text{-ary relation }=\text{ subset of }{S}^3=S\times S\times S,\text{ etc. }$$

We will focus attention on binary relations as these are by far the most important. If $R\subseteq S\times S$ is a binary relation on $S,$ it is common to use the notation aRb in place of $(a,b)\in R$

Some commonly used terms describing relations are the following:

R is said to be a reflexive relation if aRa for all $a\in S$

R is called symmetric if $aRb\Rightarrow bRa$ for all $a,b\in S.$

R is transitive if (aRb and $bRc)\Rightarrow aRc$ for all a, $b,c\in S.$

Example 1.2

Let R be the set of all real numbers. The usual ordering of real numbers is a relation on R, denoted $x\le y$ , which is both reflexive and transitive but not symmetric. The relation of strict ordering $x\text{textless}y$ is transitive, but is neither reflexive nor symmetric. Similar statements apply for the ordering on subsets of R, such as the integers or rational numbers. The notation $x\le y$ is invariably used for this relation in place of the rather odd-looking $(x,y)\in \le \mathrm{where}\le \subseteq {\mathbb{R}}^2$

Referenced 1 time

• 1.3 Cartesian products and relationsThe characteristic features of an ‘order relation’ have been discussed in Example 1.2, specifically …

Equivalence relations

A relation that is reflexive, symmetric and transitive is called an equivalence relation. For example, equality $a=b$ is always an equivalence relation. If R is an equivalence relation on a set S and a is an arbitrary element of S, then we define the equivalence class corresponding to a to be the subset

$$[a{]}_R=\{b\in S|aRb\}.$$

The equivalence class is frequently denoted simply by [a] if the equivalence relation R is understood. By the reflexive property $a\in [a]$ – that is, equivalence classes ‘cover’ the set $S$ in the sense that every element belongs to at least one class. Furthermore, if $aRb$ then $[a]=[b]$ .

Proof

Let $c\in [a]$ so that a $Rc$ . By symmetry, we have $bRa$ , and the transitive property implies that $bRc$ . Hence $c\in [b]$ , showing that $[a]\subseteq [b]$ . Similarly $[b]\subseteq [a]$ , from which it follows that $[a]=[b]$

Furthermore, $\mathrm{if}[a]$ and [b] are any pair of equivalence classes having non-empty intersection, [a] $\cap [b]\ne \varnothing .$ , then $[a]=[b]$ . For, if $c\in [a]\cap [b]$ then aRc and $cRb$ . By transitivity, aRb, or equivalently $[a]=[b]$ . Thus any pair of equivalence classes are either disjoint, $[a]\cap [b]=\varnothing$ , or else they are equal, $[a]=[b]$ . The equivalence relation R is therefore said to partition the set S into disjoint equivalence classes.

The factor space

It is sometimes useful to think of elements of S belonging to the same equivalence class as being ‘identified’ with each other through the equivalence relation R. The set whose elements are the equivalence classes defined by the equivalence relation R is called the factor space, denoted $S/R$

$$S/R=\{[a{]}_R\mid a\in S\}\equiv \{x\mid x=[a{]}_R,a\in S\}.$$

Example 1.3

Let p be a positive integer. On the set of all integers Z, define the equivalence relation R by m Rn if and only if there exists $k\in \mathbb{Z}$ such that $m-n=kp$ , denoted

$$m\equiv n(\mathrm{mod}p).$$

This relation is easily seen to be an equivalence relation. For example, to show it is transitive, simply observe that if $m-n=kp$ and $n-j=lp$ then $m-j=(k+l)p$ . The equivalence class [m] consists of the set of integers of the form $m+kp,(k=0,\pm 1,\pm 2,\dots )$ . It follows that there are precisely p such equivalence classes, [0], $[1],\dots ,[p-1]$ , called the residue classes modulo $p.$ . Their union spans all of $\mathbb{Z}.$

Referenced 1 time

• 1.6 StructuresSimple algebra reveals that … , so that … . In this case … is isomorphic with the residue class of i…

Example 1.4

Let ${\mathbb{R}}^2=\mathbb{R}\times \mathbb{R}$ be the cartesian plane and define an equivalence relation on ${\mathbb{R}}^2$ by

$$(x,y)\equiv (x^{\prime },y^{\prime })\text{ iff }\exists n,m\in \mathbb{Z}\text{ such that }{x}^{\prime }=x+m,y^{\prime }=y+n.$$

Each equivalence class $[(x,y)]$ has one representative such that $0\le x<1,0\le y<1$ The factor space

$$T^2={\mathbb{R}}^2/\equiv =\{[(x,y)]\mid 0\le x,y<1\}$$

is called the 2-torus. The geometrical motivation for this name will become apparent in Chapter 10.

Order relations and posets

The characteristic features of an ‘order relation’ have been discussed in Example 1.2, specifically for the case of the real numbers. More generally, a relation R on a set S is said to be a partial order on S if it is reflexive and transitive, and in place of the symmetric property it satisfies the ‘antisymmetric’ property

$$aRb\text{ and }bRa⟹a=b.$$

The ordering on real numbers has the further special property of being a total order, by which it is meant that for every pair of real numbers x and $y$ , we have either $x\le y$ or $y\le x$

Example 1.5

The power set $2^S$ of a set S is partially ordered by the relation of set inclusion $\subseteq$ ,

$$\begin{array}{c}U\subseteq U\text{ for all }U\in 2^S,\\ U\subseteq V\text{ and }V\subseteq W⟹U\subseteq W,\\ U\subseteq V\text{ and }V\subseteq U⟹U=V.\end{array}$$

Unlike the ordering of real numbers, this ordering is not in general a total order.

A set S together with a partial order $\le$ is called a partially ordered set or more briefly a poset. This is an example of a structured set. The words ‘together with’ used here are a rather casual type ofmathspeak commonly used to describe a set with an imposed structure. Technically more correct is the definition of a poset as an ordered pair,

$$\text{ poset }S\equiv (S,\le )$$

where $\le \subseteq S\times S$ satisfies the axioms of a partial order. The concept of a poset could be totally reduced to its set-theoretical elements by writing ordered pairs (s, t) as sets of the form $\{\{s,t\},s\}$ , etc., but this uninstructive task would only serve to demonstrate how simple mathematical concepts can be made totally obscure by overzealous use of abstract definitions.

Problems

Problem 1.8

Show the following identities:

$$(A\cup B)\times P=(A\times P)\cup (B\times P),$$ $$(A\cap B)\times (P\cap Q)=(A\times P)\cap (B\times Q),$$ $$(A-B)\times P=(A\times P)-(B\times P).$$

Referenced 1 time

• 1.3 Cartesian products and relationsEquation (1.1) uses the standard Kuratowski pair here. The supplied PDF prints …, which is not a gen…

Problem 1.9

If $\cdot \mathcal{A}=\{A_i\mid i\in I\}$ and $\mathcal{B}=\{B_j\mid j\in J\}$ are any two families of sets then

$$\bigcup \mathcal{A}\times \bigcup \mathcal{B}=\bigcup _{i\in I,j\in J}{A}_i\times B_j,$$ $$\bigcap \mathcal{A}\times \bigcap \mathcal{B}=\bigcap _{i\in I,j\in J}{A}_i\times B_j.$$

Problem 1.10

Show that both the following two relations:

$$\begin{array}{ll}(a,b)\le (x,y)& \text{ iff }a<x\text{ or }(a=x\text{ and }b\le y)\\ (a,b)⪯(x,y)& \text{ iff }a\le x\text{ and }b\le y\end{array}$$

are partial orders on $\mathbb{R}\times \mathbb{R}$. For partial orders $\le$ and $⪯$ on a set $A$, say that $\le$ is stronger than $⪯$ if $a\le b\Rightarrow a⪯b$. Is the lexicographic order $\le$ stronger than, weaker than, or incomparable with the componentwise order $⪯$?

Referenced 1 time

• Chapter 1 · Sets and structuresThe most fundamental notion in mathematics is that of a set, or ‘collection of objects’. The subject…