1The Sheffer stroke¶
Continued from last class: the Sheffer stroke is a binary connective with the following truth table^{1}:
$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 2dimensional 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^{2} 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^{3} 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 onetoone.
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 onetoone 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 onetoone 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^{5}, 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$^{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$.

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. ↩

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

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

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

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. ↩

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

Function composition goes righttoleft, as per Euler's convention. ↩