3.4: Finite and infinite relations

Last updated
Save as PDF

Page ID: 95639

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Sets can be infinite, and relations can be too. An infinite relation is simply a relation with infinitely many ordered pairs in it. This might seem strange at first, since how could we ever hope to specify all the ordered pairs? But it’s really no different than with sets: we either have to do it intensionally, or else have a rule for systematically computing the extension.

As an example of the first, consider the relation “isGreaterThan" between \(\mathbb{Z}\) and \(\mathbb{Z}\). (Recall that “\(\mathbb{Z}\)" is just a way of writing “the set of integers.") This relation contains ordered pairs like (5, 2) and (17, –13), since 5 isGreaterThan 2 and 17 isGreaterThan –13, but not (7, 9) or (11, 11). Clearly it’s an infinite relation. We couldn’t list all the pairs, but we don’t need to, since the name implies the underlying meaning of the relation.

As an example of the second, consider the relation “isLuckierThan" between \(\mathbb{N}\) and \(\mathbb{N}\). (The “\(\mathbb{N}\)" means “the natural numbers.") We specify it extensionally as follows:

{ (1, 13), (2, 13), (3, 13), …(12, 13), (14, 13), (15, 13), (16, 13), … }

Here we’re just saying “every number is luckier than 13 (except for 13 itself, of course)."