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, , is a subset of the Cartesian product of two (or more) sets.

  • also

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

  • or

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.


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

Domain Range and are both sets. and are universal sets.

Inverse Relation For a binary relation, , its inverse relation, , is the relation created by reversing the order of the elements of the pairs of .

For , Axiom [Inverse] We have the following properties for inverse relations:

Identity Relation The identity relation for a set , written as , is the pairing of every element of with itself. I don’t know why this is useful, but oh well, we’ll see.

Relational Composition For three sets , and , and two relations on them , and , the relational composition of and is the relation containing the pairs , such that there is an , and and . It is pronounced β€œ followed by ”.

Relational Image This is sounding way too complicated for no reason. is a set, and is a relation. gives the image of restricted to as a set.

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


The trick is to remember that

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

Domain Restriction retains only the pairs whose first elements are part of a set Domain Subtraction retains the pairs of binary relation whose first elements are NOT part of set The symbol is different but I can’t get it to show up on Obsidian. It has an extra slash

Range Restriction retains only the pairs of relation whose second elements are part of set

Range Subtraction retains the pairs of relation whose second elements are NOT part of set

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

is NOT a set here.

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.


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 (equivalently or ) is a function if and only if

  • Functions can be classified as total, surjective, injective, and bijective.
  • Functions are also called mappings.
  • is called the application of to .
  • is the same as if is a TOTAL function.

Partial Function

For a function f from set A to set B, the domain of 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:

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):

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 to set is defined for all the elements of . Total functions are a subset of the set of partial functions from to . means f is a total function from to