Monday, September 12, 2011

Introduction to relations

1The Sheffer stroke¶

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

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 something^huh?). The range is $\{ b \in B: aRb \text{ for some } a \in A\}$. Note that you can't figure out the specific intended domain/range² 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 subset³ 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"⁴.

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 cardinality⁵, i.e. equinumerous)

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

Example: $A \sim A$ for all $A$: $\iota_A$⁶: $\{ (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$⁷ $= 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$.