1.1.5: Pairs, Tuples, Cartesian Products

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    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\]


    This page titled 1.1.5: Pairs, Tuples, Cartesian Products was last modified on Fri, 08 Mar 2024 05:56:22 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .