Monday, September 12, 2011 CC-BY-NC
Introduction to relations

Maintainer: admin

1The Sheffer stroke

Continued from last class: the Sheffer stroke is a binary connective with the following truth table1:

$p$ $q$ $p \mid q$
$\top$ $\top$ $\bot$
$\top$ $\bot$ $\top$
$\bot$ $\top$ $\top$
$\bot$ $\bot$ $\top$

This is a functionally complete connective, if that's a term, meaning that you can define every other connective using just this one.

2The basics of relations

We start with some basic set notation. Let $A$ and $B$ be sets (possibly different, possibly the same). $A \times B = \{ (a, b) : a \in A, \, b\in B\}$. For example, $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ which is 2-dimensional Euclidean space and which consists of all points $(x, y)$ ... well, yeah. Anyways.

A relation $R$ from $A$ to $B$ is just a subset of $A\times B$. As $R \subseteq A \times B$, we can write $aRb$ (where R means, "is related to") for $(a, b) \in R$.

We have $< \in \mathbb{R} \times \mathbb{R}$ so technically $(1, 2) \in <$ since we have $1 < 2$.

The domain of $R$ is $\{ a \in A: aRb \text{ for some } b \in B\}$ (i.e. the set of all things that are, in the first place, related to somethinghuh?). The range is $\{ b \in B: aRb \text{ for some } a \in A\}$. Note that you can't figure out the specific intended domain/range2 just from the relation itself, as there are many possibilities.

N.B. if $R$ is a relation from $A$ to $B$ (note: not symmetric) and $A \subseteq A'$ and $B \subseteq B'$, then the same $R$ is also a relation from $A'$ to $B'$. This is a convention.

In the case where $A = B$ (i.e. $R \subseteq A \times A$), we say $R$ is a (binary) relation on $A$.

2.1Relations as functions

A relation $R: A \to B$ is a function from $A$ to $B$ if, for each $a \in A$, there is a unique $b \in B$ such that $aRb$ (although several $a$'s can be related to the same $b$). The domain of the function is all of $A$ and the range is a subset3 of $B$. For example, if $A = B = \mathbb{R}$ and $R = \{ (x, x^2) : x \in \mathbb{R} \}$, then the domain is $\mathbb{R}$, and the range is only the positive real numbers.

2.1.1Injective function

A function from $A$ to $B$ is injective if, whenever $a \neq a'$ in $A$, then $f(a) \neq f(a')$ - meaning everything in the domain maps to something unique. Such a function is considered one-to-one.

2.1.2Surjective functions

A function is surjective if there is at least one $a \in A$ such that $f(a) = b$ for every $b \in B$. In other words, everything in $B$ is accounted for. Also known as "onto"4.

Although injectiveness is an intrinsic property, surjectiveness is not, as you can only say that a function is onto something.

2.1.3Bijective functions

A function that is both injective and surjective is bijective. So there is a one-to-one correspondence or perfect matching of $A$ and $B$. The notation for this is $A \sim B$, but we won't be using it much. Obviously any one-to-one function is a bijection onto its own range. Beyond that, we have that if $A$ is finite, and $A \sim B$, then $A$ and $B$ have the same number of elements (same cardinality5, i.e. equinumerous)

Fact: $\mathbb{N} \sim \mathbb{Z} \sim \mathbb{Q}$ but $\mathbb{N} \nsim \mathbb{R}$ because they're infinitewat.

Example: $A \sim A$ for all $A$: $\iota_A$6: $\{ (a, a): a \in A \}$ is a bijection

2.1.4Inverse relations

If $R \subseteq A \times B$, then inverse of $R$, denoted $R^{-1}$, is $\{ (b, a): a Rb\}$. The inverse of a function is not always a function (although it is always a relation) - it's only a function if the original function is a bijection. If that is true, then the inverse is also a bijection, i.e. $A \sim B \iff B \sim A$.

2.1.5Composition of relations

If $R \subseteq A \times B$ and $S \subseteq B \times C$, then the composition $S \circ R$7 $= R \times S = \{ (a, c) \text{ for some } b \in B, aRb \text{ and } bSc \}$.

Functionally speaking, $f: A \to B$, $g: B \to C$, so $g \circ f: A \to C$. The chain rule in differentiation is an example of this or something.

For example: say $A = B = C$ are all sets, of people, and $R=S$. $aRb$ means that $a$ is the parent of $b$. So when is $a(R \times R)c$ true? When $a$ is a grandparent of $c$ I guess.

Fact: If $f: A \to B$ and $g: B \to C$ are both bijections, so is $g \circ f$. Same with injections and surjections. Hence if $A \sim B$ and $B \sim C$, then $A \sim C$.

  1. Wikipedia gives a different truth table, but Loveys seems to prefer this definition, which shows up again in assignment 2, question 2 c). It doesn't really matter though, it's the same idea. 

  2. Also known or codomain, or image. Not really relevant. 

  3. Not necessarily a proper subset; it could be all of $B$, in which case the function would be onto

  4. Note that every function is clearly onto its own range. For example, the function in the $x, x^2$ example is onto the non-negative reals, though not $\mathbb{R}$ as a whole. 

  5. The notion of cardinality is much more complex for infinite sets. Not really relevant at the moment but included as a footnote because it was mentioned in class. 

  6. The identity function. There's not much more to it than what is defined above. I don't know. 

  7. Function composition goes right-to-left, as per Euler's convention.