# Binary Relation

In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain.

I am surprised they never taught us this. NOTE: Finally learning this in SE212

Relations are sets. A relation, $R$, is a subset of the Cartesian product of two (or more) sets.

- $RβCβB$ also $RβP(CβB)$

We can state that R is a relation from a set C to a set B as a type:

- $R:CβB$ or $R:P(CβB)$

IMPORTANT: Note that the symbol $β$ above does not mean transformational proof in this context.

A **binary** relation is a set of pairs. We can also have a ternary relation, which would have a set of 3 elements.

### Relation

Wow, SE212 exposed me to this new way of thinking about Functions as mappings between sets to sets (well yea, but notation is different). This is for relation

For relation $R:AβB$

**Domain**
$dom(R)={x:Aβ£βy:Bβ(x,y)βR}$
**Range**
$ran(R)={y:Bβ£βx:Aβ(x,y)βR}$
$dom(R)$ and $ran(R)$ are both sets. $A$ and $B$ are universal sets.

**Inverse Relation**
For a binary relation, $R$, its inverse relation, $R_{βΌ}$, is the relation created by reversing the order of the elements of the pairs of $R$.

For $R:AβB$, Axiom [Inverse] $R_{βΌ}={(b,a)β£(a,b)βR}$ We have the following properties for inverse relations:

- $(R_{βΌ})_{βΌ}=R$
- $dom(R_{βΌ})=ran(R)$
- $ran(R_{βΌ})=dom(R)$

**Identity Relation**
The identity relation for a set $B$, written as $id(B)$, is the pairing of every element of $B$ with itself.
$id(B)={(a,a)β£aβB}$
I donβt know why this is useful, but oh well, weβll see.

**Relational Composition**
For three sets $A$, $B$ and $C$, and two relations on them $R:AβB$, and $S:BβC$, the relational composition of $R$ and $S$ is the relation containing the pairs $(a,c)$, such that there is an $bβB$, and $(a,b)βR$ and $(b,c)βS$. It is pronounced β$R$ followed by $S$β.

$R;S={(a,c)β’a:A,c:Cβ£βbβ’(a,b)βRβ§(b,c)βS}$

**Relational Image**
This is sounding way too complicated for no reason. $S$ is a set, and $R$ is a relation. $R(β£Sβ£)$ gives the image of $R$ restricted to $S$ as a set.

If you do $Rβ·S$, that would still give you a set of pairs, but you want a set of the image/range generated.

$R(β£Sβ£)={yβ£βxβ’(x,y)βRβ§xβS}$

### Restrictions

The trick is to remember that

- domain = (put set on) left to restrict the intake of relation $R$
- Range = (put set on) right to restrict output of relation $R$

**Domain Restriction** retains only the pairs whose first elements are part of a set
$SβR={(a,b)β’a:A,b:Bβ£(a,b)βRβ§aβS}$
**Domain Subtraction** retains the pairs of binary relation $R$ whose first elements are NOT part of set $S$
*The symbol is different but I canβt get it to show up on Obsidian*. It has an extra slash
$SβR={(a,b)β’a:A,b:Bβ£(a,b)βRβ§Β¬(aβS)}$

**Range Restriction** retains only the pairs of relation $R$ whose second elements are part of set $S$
$Rβ·S={(a,b)β’a:A,b:Bβ£(a,b)βRβ§bβS}$

**Range Subtraction** retains the pairs of relation $R$ whose second elements are NOT part of set $S$
$Rβ·S=(a,b)β’a:A,b:Bβ£(a,b)βRβ§Β¬(bβS)$

Using **relational overriding**, we can βupdateβ a relation $R$ with another relation $S$ where the pairs of $S$ are added to the relation, and pairs in $R$ with the first element of pairs in $S$ are eliminated (think of it like being overwritten)

$S$ is NOT a set here.

$RβS=(dom(S)!βR)βͺS$ R β S = ((dom(S) !β R) βͺ S = \set{(a, b) | (a, b) β R β§ a ΜΈβ dom(S) β¨ (a, b) β S} This is NOT the same as relational composition.

## Functions

This is a new way to think about functions as a relation.

A Function is a Relation in which each domain element is associated with a unique range element.

A relation $f:AβB$ (equivalently $fβP(AβB))$ or $fβAβB$) is a function if and only if $βx:Aβ’βy,z:Bβ’(x,y)βfβ§(x,z)βfβy=z$

- Functions can be classified as total, surjective, injective, and bijective.
- Functions are also called mappings.
- $f(x)$ is called the application of $f$ to $x$.
- $f(x)=y$ is the same as $(x,y)βf$ if $f$ is a TOTAL function.

### Partial Function

For a function f from set A to set B, the domain of $f$ may include all, some or none of the elements of A. If an element of A is not in the domain of the function we say that it is βundefinedβ for that element.

Partial functions are the most general kind of function. All functions are partial functions.

The set of partial functions from A to B is: ${f:AβBβ£βx:Aβ’βy,z:Bβ’(x,y)βfβ§(x,z)βfβy=z}$

This is exactly what we said was necessary for something to be a function.

### Function Space

A set of functions is called a function space. The set of (non-total) functions (note this is from SE212, they use these really weird symbols that I canβt use in SE212, they use these really weird symbols that I canβt use in LateX):

$A7βB={f:AβBβ£βx:Aβ’βy,z:Bβ’(x,y)βfβ§(x,z)βfβy=z}$

We can use the function space as the type of the function. f : A 7β B means f is a partial function from A to B

Notation in SE212 for Injective, Surjective and Non-Total functions.

See Injective and Surjective Function for definitions.

### Total Function

A total function simply means that it is defined for all of the domain.

A total function from set $A$ to set $B$ is defined for all the elements of $A$. Total functions are a subset of the set of partial functions from $A$ to $B$. $AβB={f:Aβ¦Bβ£dom(f)=A}$ $f:AβB$ means f is a total function from $A$ to $B$