Relations and Functions

Relations

A relation \(R\) is a subset of the product of sets \(A_1 \times A_2 \times \ldots \times A_N\). That means that elements of a relation are \(N\)-tuples. Including a particular tuple in the relation represents that the things in the tuple have that relationship to each other.

For example, the relation between vowel height \(H = \{\mathrm{high}, \mathrm{mid}, \mathrm{low}\}\) and the English vowels \(V = \{\mathrm{i}, \mathrm{u}, ...\}\) that have that height and can be represented as a relation \(R_\text{height-of}\).

height_of: set[tuple[str, str]] = {
    ('high', 'i'),
    ('high', 'ɪ'),
    ('high', 'u'),
    ('high', 'ʊ'),
    ('mid', 'e'),
    ('mid', 'ɛ'),
    ('mid', 'o'),
    ('mid', 'ɔ'),
    ('mid', 'ə'),
    ('low', 'ɑ'),
    ('low', 'æ')
}

\(R_\text{height-of}\) is a relation, since it is the subset of \(H \times V\).

\[R_\text{height-of} \subseteq H \times V\]

Functions

Functions–or more specifically, their graphs–are particular kinds of relations. The (graph of a) function \(F \subseteq X \times Y\) is a relation s.t. if \(\langle x, y \rangle \in F \land \langle x, z \rangle \in F\), then \(y = z\).

For instance, the relation \(R_\text{height-of}\) is not a function, but its inverse relation \(R_\text{height-of}^{-1} = R_\text{has-height}\) is.

\[R^{-1}_\text{height-of} = R_\text{has-height} = \{\langle y, x \rangle \;|\; \langle x, y \rangle \in R_\text{height-of}\}\]

has_height: set[tuple[str, str]] = {(y, x) for x, y in height_of}

has_height

{('e', 'mid'),
 ('i', 'high'),
 ('o', 'mid'),
 ('u', 'high'),
 ('æ', 'low'),
 ('ɑ', 'low'),
 ('ɔ', 'mid'),
 ('ə', 'mid'),
 ('ɛ', 'mid'),
 ('ɪ', 'high'),
 ('ʊ', 'high')}

We can check that it is a function by checking that:

len({x for x, _ in has_height}) == len(has_height)

True

len({x for x, y in height_of}) == len(height_of)

False

Partiality

A function is total if \(X = \{x \;|\; \langle x, y \rangle \in F\}\); otherwise it is partial.

Domain and codomain

We often think of functions as mapping inputs to outputs. The inputs of the function come from its domain and the outputs come from its codomain.

For instance, if we view \(R_\text{has-height}\) as a function \(f_\text{has-height}\), the domain of \(f_\text{has-height}\) is the set of vowels \(V\) and the codomain is the set of heights \(H\). We will often express this using the following notation.

\[f_\text{has-height}: V \rightarrow H\]

Sometimes we will express it using two other functions \(\text{dom}\) and \(\text{cod}\).

\[\text{dom}(f_\text{has-height}) = V\] \[\text{cod}(f_\text{has-height}) = H\]

For a function \(f\) with graph \(R\), we denote each \(y\) s.t. \(\langle x, y \rangle \in F\) as \(f(x)\).

Image

The image of \(W \subseteq X\) under \(f\) is \(f(W) = \{f(x) \;|\; x \in W\}\).

from typing import TypeVar

T = TypeVar("T")

def image(w: set[T], f: set[tuple[T, T]]) -> set[T]:
    return {y for x, y in f if x in w}

image({'i'}, has_height)

{'high'}

image({'i', 'e'}, has_height)

{'high', 'mid'}

Preimage

The preimage of \(Z \subseteq Y\) under \(f\) is \(f^{-1}(Z) = \{x \;|\; f(x) \in Z\}\).

def preimage(z: set[T], f: set[tuple[T, T]]) -> set[T]:
    return {x for x, y in f if y in z}

preimage({'high'}, has_height)

{'i', 'u', 'ɪ', 'ʊ'}

heights: set[str] = {h for h, _ in height_of}

preimage(heights - {'low'}, has_height)

{'e', 'i', 'o', 'u', 'ɔ', 'ə', 'ɛ', 'ɪ', 'ʊ'}

Range

The range of \(X\) under \(f\) is the image of \(X\) under \(f\): \(f(X)\).