1.1.5: Pairs, Tuples, Cartesian Products

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

It follows from extensionality that sets have no order to their elements. So if we want to represent order, we use ordered pairs \(\tuple{x, y}\). In an unordered pair \(\{x, y\}\), the order does not matter: \(\{x, y\} = \{y, x\}\). In an ordered pair, it does: if \(x \neq y\), then \(\tuple{x, y} \neq \tuple{y, x}\).

How should we think about ordered pairs in set theory? Crucially, we want to preserve the idea that ordered pairs are identical iff they share the same first element and share the same second element, i.e.:

\[\tuple{a, b}= \tuple{c, d}\text{ iff both }a = c \text{ and }b=d.\nonumber\]

We can define ordered pairs in set theory using the Wiener-Kuratowski definition.

Definition \(\PageIndex{1}\): Ordered pair

\(\tuple{a, b} = \{\{a\}, \{a, b\}\}\).

Problem \(\PageIndex{1}\)

Using Definition \(\PageIndex{1}\), prove that \(\tuple{a, b}= \tuple{c, d}\) iff both \(a = c\) and \(b=d\).

Having fixed a definition of an ordered pair, we can use it to define further sets. For example, sometimes we also want ordered sequences of more than two objects, e.g., triples \(\tuple{x, y, z}\), quadruples \(\tuple{x, y, z, u}\), and so on. We can think of triples as special ordered pairs, where the first element is itself an ordered pair: \(\tuple{x, y, z}\) is \(\tuple{\tuple{x, y},z}\). The same is true for quadruples: \(\tuple{x,y,z,u}\) is \(\tuple{\tuple{\tuple{x,y},z},u}\), and so on. In general, we talk of ordered \(n\)-tuples \(\tuple{x_1, \dots, x_n}\).

Certain sets of ordered pairs, or other ordered \(n\)-tuples, will be useful.

Definition \(\PageIndex{2}\): Cartesian product

Given sets \(A\) and \(B\), their Cartesian product \(A \times B\) is defined by

\[A \times B = \Setabs{\tuple{x, y}}{x \in A \text{ and } y \in B}.\nonumber\]

Example \(\PageIndex{1}\)

If \(A = \{0, 1\}\), and \(B = \{1, a, b\}\), then their product is

\[A \times B = \{ \tuple{0, 1}, \tuple{0, a}, \tuple{0, b}, \tuple{1, 1}, \tuple{1, a}, \tuple{1, b} \}.\nonumber\]

Example \(\PageIndex{2}\)

If \(A\) is a set, the product of \(A\) with itself, \(A \times A\), is also written \(A^2\). It is the set of all pairs \(\tuple{x, y}\) with \(x, y \in A\). The set of all triples \(\tuple{x, y, z}\) is \(A^3\), and so on. We can give a recursive definition: \[\begin{aligned} A^1 & = A\\ A^{k+1} & = A^k \times A\end{aligned}\]

Problem \(\PageIndex{2}\)

List all elements of \(\{1, 2, 3\}^3\).

Proposition \(\PageIndex{1}\)

If \(A\) has \(n\) elements and \(B\) has \(m\) elements, then \(A \times B\) has \(n\cdot m\) elements.

Proof. For every element \(x\) in \(A\), there are \(m\) elements of the form \(\tuple{x, y} \in A \times B\). Let \(B_x = \Setabs{\tuple{x, y}}{y \in B}\). Since whenever \(x_1 \neq x_2\), \(\tuple{x_1, y} \neq \tuple{x_2, y}\), \(B_{x_1} \cap B_{x_2} = \emptyset\). But if \(A = \{x_1, \dots, x_n\}\), then \(A \times B = B_{x_1} \cup \dots \cup B_{x_n}\), and so has \(n\cdot m\) elements.

To visualize this, arrange the elements of \(A \times B\) in a grid:

\[\begin{array}{rcccc} B_{x_1} = & \{\tuple{x_1, y_1} & \tuple{x_1, y_2} & \dots & \tuple{x_1, y_m}\}\\ B_{x_2} = & \{\tuple{x_2, y_1} & \tuple{x_2, y_2} & \dots & \tuple{x_2, y_m}\}\\ \vdots & & \vdots\\ B_{x_n} = & \{\tuple{x_n, y_1} & \tuple{x_n, y_2} & \dots & \tuple{x_n, y_m}\} \end{array}\nonumber\]

Since the \(x_i\) are all different, and the \(y_j\) are all different, no two of the pairs in this grid are the same, and there are \(n\cdot m\) of them. ◻

Problem \(\PageIndex{3}\)

Show, by induction on \(k\), that for all \(k \ge 1\), if \(A\) has \(n\) elements, then \(A^k\) has \(n^k\) elements.

Example \(\PageIndex{3}\)

If \(A\) is a set, a word over \(A\) is any sequence of elements of \(A\). A sequence can be thought of as an \(n\)-tuple of elements of \(A\). For instance, if \(A = \{a, b, c\}\), then the sequence “\(bac\)” can be thought of as the triple \(\tuple{b, a, c}\). Words, i.e., sequences of symbols, are of crucial importance in computer science. By convention, we count elements of \(A\) as sequences of length \(1\), and \(\emptyset\) as the sequence of length \(0\). The set of all words over \(A\) then is

\[A^* = \{\emptyset\} \cup A \cup A^2 \cup A^3 \cup \dots\nonumber\]