1.2.1: Relations as Sets

\(\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} } }\)

In section 1.3, we mentioned some important sets: \(\Nat\), \(\Int\), \(\Rat\), \(\Real\). You will no doubt remember some interesting relations between the elements of some of these sets. For instance, each of these sets has a completely standard order relation on it. There is also the relation is identical with that every object bears to itself and to no other thing. There are many more interesting relations that we’ll encounter, and even more possible relations. Before we review them, though, we will start by pointing out that we can look at relations as a special sort of set.

For this, recall two things from section 1.5. First, recall the notion of a ordered pair: given \(a\) and \(b\), we can form \(\tuple{a, b}\). Importantly, the order of elements does matter here. So if \(a \neq b\) then \(\tuple{a, b} \neq \tuple{b, a}\). (Contrast this with unordered pairs, i.e., \(2\)-element sets, where \(\{a, b\}=\{b, a\}\).) Second, recall the notion of a Cartesian product: if \(A\) and \(B\) are sets, then we can form \(A \times B\), the set of all pairs \(\tuple{x, y}\) with \(x \in A\) and \(y \in B\). In particular, \(A^{2}= A \times A\) is the set of all ordered pairs from \(A\).

Now we will consider a particular relation on a set: the \(<\)-relation on the set \(\Nat\) of natural numbers. Consider the set of all pairs of numbers \(\tuple{n, m}\) where \(n<m\), i.e., \[R=\Setabs{\tuple{n, m}}{n, m \in \Nat \text{ and } n<m}.\nonumber\] There is a close connection between \(n\) being less than \(m\), and the pair \(\tuple{n, m}\) being a member of \(R\), namely: \[n<m\text{ iff }\tuple{n, m} \in R.\nonumber\] Indeed, without any loss of information, we can consider the set \(R\) to be the \(<\)-relation on \(\Nat\).

In the same way we can construct a subset of \(\Nat^{2}\) for any relation between numbers. Conversely, given any set of pairs of numbers \(S \subseteq \Nat^{2}\), there is a corresponding relation between numbers, namely, the relationship \(n\) bears to \(m\) if and only if \(\tuple{n, m} \in S\). This justifies the following definition:

Definition \(\PageIndex{1}\): Binary relation

A binary relation on a set \(A\) is a subset of \(A^{2}\). If \(R \subseteq A^{2}\) is a binary relation on \(A\) and \(x, y \in A\), we sometimes write \(Rxy\) (or \(xRy\)) for \(\tuple{x, y} \in R\).

Example \(\PageIndex{1}\)

The set \(\Nat^{2}\) of pairs of natural numbers can be listed in a 2-dimensional matrix like this: \[\begin{array}{ccccc} \mathbf{\tuple{ 0,0 }} & \tuple{ 0,1 } & \tuple{ 0,2 } & \tuple{ 0,3 } & \ldots\\ \tuple{ 1,0 } & \mathbf{\tuple{ 1,1 }} & \tuple{ 1,2 } & \tuple{ 1,3 } & \ldots\\ \tuple{ 2,0 } & \tuple{ 2,1 } & \mathbf{\tuple{ 2,2 }} & \tuple{ 2,3 } & \ldots\\ \tuple{ 3,0 } & \tuple{ 3,1 } & \tuple{ 3,2 } & \mathbf{\tuple{ 3,3 }} & \ldots\\ \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots} \end{array}\nonumber\] We have put the diagonal, here, in bold, since the subset of \(\Nat^2\) consisting of the pairs lying on the diagonal, i.e., \[\{\tuple{0,0 }, \tuple{ 1,1 }, \tuple{ 2,2 }, \dots\},\nonumber\] is the identity relation on \(\Nat\). (Since the identity relation is popular, let’s define \(\Id{A}=\Setabs{\tuple{ x,x }}{x \in X}\) for any set \(A\).) The subset of all pairs lying above the diagonal, i.e., \[L = \{\tuple{ 0,1 },\tuple{ 0,2 },\ldots,\tuple{ 1,2 }, \tuple{ 1,3 }, \dots, \tuple{ 2,3 }, \tuple{ 2,4 },\ldots\},\nonumber\] is the less than relation, i.e., \(Lnm\) iff \(n<m\). The subset of pairs below the diagonal, i.e., \[G=\{ \tuple{ 1,0 },\tuple{ 2,0 },\tuple{ 2,1 }, \tuple{ 3,0 },\tuple{ 3,1 },\tuple{ 3,2 }, \dots\},\nonumber\] is the greater than relation, i.e., \(Gnm\) iff \(n>m\). The union of \(L\) with \(I\), which we might call \(K=L\cup I\), is the less than or equal to relation: \(Knm\) iff \(n \le m\). Similarly, \(H=G \cup I\) is the greater than or equal to relation. These relations \(L\), \(G\), \(K\), and \(H\) are special kinds of relations called orders. \(L\) and \(G\) have the property that no number bears \(L\) or \(G\) to itself (i.e., for all \(n\), neither \(Lnn\) nor \(Gnn\)). Relations with this property are called irreflexive, and, if they also happen to be orders, they are called strict orders.

Although orders and identity are important and natural relations, it should be emphasized that according to our definition any subset of \(A^{2}\) is a relation on \(A\), regardless of how unnatural or contrived it seems. In particular, \(\emptyset\) is a relation on any set (the empty relation, which no pair of elements bears), and \(A^{2}\) itself is a relation on \(A\) as well (one which every pair bears), called the universal relation. But also something like \(E=\Setabs{\tuple{n, m}}{n>5 \text{ or } m \times n \ge 34}\) counts as a relation.

Problem \(\PageIndex{1}\)

List the elements of the relation \(\subseteq\) on the set \(\Pow{\{a, b, c\}}\).