Relations and Functions

Relations

Binary Relation

A binary relation $R$ over sets $X$ and $Y$ is a set of ordered pairs of elements from $X$ and $Y$:$R\subseteq \{(x,y)\mid x\in X,y\in Y\}$The statement $(x,y)\in R$ reads ”$x$ is $R$-related to $y$” and is written as $xRy$.

Homogeneous Relation

A homogeneous relation on a set $X$ is a binary relation between $X$ and itself, i.e. it is a subset of $X\times X$.

Reflexivity

A homogeneous relation $R$ on a set $X$ is reflexive if it relates every element of $X$ to itself. That is $(x,x)\in R$.

Symmetry

A homogeneous relation $R$ on a set $X$ is symmetric if $aRb⟹bRa$.

Antisymmetry

A homogeneous relation $R$ on a set $X$ is antisymmetric if there is no pair of distinct elements of $X$ each of which is related by $R$ to the other. Formally, $R$ is antisymmetric if for all $a,b\in X$,$(a,b)\in R\text{ and }a\ne b⟹(b,a)\notin R$ Equivalently, $aRb,bRa⟹a=b$

Transitivity

A homogeneous relation $R$ on a set $X$ is transitive if, for all elements $a,b,c$ in $X$, whenever $R$ relates $a$ to $b$ and $b$ to $c$, then $R$ also relates $a$ to $c$.

Connectedness

A homogeneous relation $R$ on a set $X$ is connected if for all $x,y\in X$: $x\ne y⟹xRy\text{ or }yRx$It is called strongly connected if $xRy$ or $yRx$ for all $x,y\in X$ no matter if they are equal.

Univalent

For all $x\in X$ and $y_1,y_2\in Y$ with relation $R$, if $xR{y}_1$ and $xR{y}_2$ implies $y_1=y_2$, we say $R$ is univalent.

Serial

We say $R$ defined on $X$ and $Y$ is serial or total if for all $x\in X$, there exists some $y\in Y$ such that $xRy$.

Equivalence Relation

Equivalence Relation

An equivalence relation is a relation on a set, generally denoted by $\sim$, that is reflexive, symmetric, and transitive for everything in the set.

• Reflexivity: $a\sim a$
• Symmetry: $a\sim b⟹b\sim a$
• Transitivity: $a\sim b\text{ and }b\sim c⟹a\sim c$

e.g. The relation “is equal to”, denoted $=$, is an equivalence relation on the set $\mathbb{R}$.

Equivalence Class

Given an equivalence relation $\sim$ defined on set $X$, the equivalence class $[x]$ of an element $x\in X$ is defined by $[x]:=\{y\in X\mid x\sim y\}$

Proposition

Suppose some equivalence relation $\sim$ is defined on set $X$, then every element $z\in X$ is exactly in one of the equivalence classes.

Proof Suppose $z\in [x_1]$ and $z\in [x_2]$. Then we have $z\sim x_1$ and $z\sim x_2$, it follows that $x_1\sim x_2$, hence $x_1\in [x_2]$, yielding that $[x_1]=[x_2]$.

Quotient

The set of all equivalence classes in $X$ with $\sim$, is called the quotient of $X$ by $\sim$: $X/\sim :=\{[x]\mid x\in X\}$

Function and Associated Sets

Function

Let $X$ and $Y$ be two sets. A function $f:X\to Y$ is a relation that is univalent and serial defined over $X$ and $Y$. The sets $X$ and $Y$ are called the domain and codomain of $f$ respectively.

Range

For some function $f:X\to Y$, the range is the set$f(X)=\{y\in Y:y=f(x)\text{ for some }x\in X\}$

Graph

The following set is called the graph of a function $f$:$\Gamma (f)=\{(x,y):x\in X,y\in Y\text{ and }y=f(x)\}$

Image

Given a subset $A\subset X$, its image under $f:X\to Y$ is defined by$f(A)=\{y\in Y:y=f(x)\text{ for some }x\in A\}$

Preimage

Given a subset $B\subset Y$ , its inverse image or preimage under $f$ is defined by$f^{-1}(B)=\{x\in X:f(x)\in B\}$

Proposition

Let $f:X\to Y$ be a function. For any set $A\subset X$ and $B\subset Y$ there hold$A\subset f^{-1}(f(A)),f(f^{-1}(B))\subset B$

Proof For any $x\in A$, $f(x)\in f(A)$, thus $x\in f^{-1}(f(A))$. For any $y\in f(f^{-1}(B))$, $y=f(x)$ for some $x\in f^{-1}(B)$, thus $y=f(x)\in B$. $\square$

Proposition

Suppose $f:X\to Y$. For any family of sets $\{A_i{\}}_{i\in I}$ in $X$ there hold$f\left({\bigcup }_{i\in I}{A}_i\right)={\bigcup }_{i\in I}f(A_i),f\left({\bigcap }_{i\in I}{A}_i\right)\subset {\bigcap }_{i\in I}f(A_i)$

Proof By definition, for all $y\in f\left({\bigcup }_{i\in I}{A}_i\right)$, $y=f(a)$ for some $a\in {\bigcup }_{i\in I}{A}_i$. Thus $a\in A_k$ for some $k\in I$. It follows that $y=f(a)\in {\bigcup }_{i\in I}f(A_i)$. All statements above are reversible, thus we have equality holds: $f\left({\bigcup }_{i\in I}{A}_i\right)={\bigcup }_{i\in I}f(A_i)$. Consider any $y\in f\left({\bigcap }_{i\in I}{A}_i\right)$, then $y=f(a)$ for some $a\in {\bigcap }_{i\in I}{A}_i$. It follows that $a\in A_i$ for all $i\in I$, hence $y=f(a)\in f(A_i)$ for all $i\in I$. Thus $y\in {\bigcap }_{i\in I}f(A_i)$. $\square$

Proposition

Suppose $f:X\to Y$. For any family of sets $\{B_i{\}}_{i\in I}$ in $Y$ there hold$f^{-1}\left({\bigcup }_{i\in I}{B}_i\right)={\bigcup }_{i\in I}{f}^{-1}(B_i),f^{-1}\left({\bigcap }_{i\in I}{B}_i\right)={\bigcap }_{i\in I}{f}^{-1}(B_i)$

Proof For any $x\in f^{-1}\left({\bigcup }_{i\in I}{B}_i\right)$, $f(x)\in {\bigcup }_{i\in I}{B}_i$, thus $f(x)\in B_k$ for some $k\in I$. It follows that $x\in f^{-1}(B_k)$ and hence $x\in {\bigcup }_{i\in I}{f}^{-1}(B_i)$. All statements above are reversible, thus we have equality holds: $f^{-1}\left({\bigcup }_{i\in I}{B}_i\right)={\bigcup }_{i\in I}{f}^{-1}(B_i)$. Consider any $x\in f^{-1}\left({\bigcap }_{i\in I}{B}_i\right)$, then $f(x)\in {\bigcap }_{i\in I}{B}_i$, it follows that $f(x)\in B_i$ for all $i\in I$. Thus $x\in f^{-1}(B_i)$ for all $i\in I$, hence $x\in {\bigcap }_{i\in I}{f}^{-1}(B_i)$. Conversely, for any $x\in {\bigcap }_{i\in I}{f}^{-1}(B_i)$, $x\in f^{-1}(B_i)$ for all $i\in I$, thus $f(x)\in B_i$ for all $i\in I$, hence $f(x)\in {\bigcap }_{i\in I}{B}_i$. That is $x\in f^{-1}\left({\bigcap }_{i\in I}{B}_i\right)$. $\square$

Composition and Inverse

Composition

Let $f:X\to Y$ and $g:Y\to Z$ be two functions. Then the function $g\circ f:X\to Z$ defined by$(g\circ f)(x)=g(f(x)),\text{ for all }x\in X$is called the composition of $f$ and $g$.

Injection, Surjection and Bijection

Let $f:X\to Y$ be a function,

• $f$ is called injective or one-one if $f(x_1)=f(x_2)$ implies $x_1=x_2$.
• $f$ is called surjective or onto if $f(X)=Y$, i.e. for every $y\in Y$ there is $x\in X$ such that $y=f(x)$.
• $f$ is called bijective if $f$ is both injective and surjective.

Proposition

If a set $X$ is finite, then a function $f:X\to X$ is injective if and only if it is surjective.

Proof Suppose $f:X\to X$ is injective. Assume $f$ is not surjective, then there exists $y\in X$ such that $y\notin f(X)$. Because $X$ is finite, by the pigeonhole $\square$

Invertible Function

A function $f:X\to Y$ is invertible if there is a function $g:Y\to X$ such that$g(f(x))=x,\text{ and }f(g(y))=y\text{ for all }x\in X,y\in Y$We will call $g$ the inverse of $f$ and denote it as $f^{-1}$.

Theorem

A function $f:X\to Y$ is invertible if and only if it is bijective.

Proof Assume $f:X\to Y$ is invertible and $f^{-1}:Y\to X$ denotes its inverse function. If $f(x_1)=f(x_2)$, then $x_1=f^{-1}(f(x_1))=f^{-1}(f(x_2))=x_2$which shows that f is injective. Next, for any $y\in Y$ , we have $y=f(f^{-1}(y))$ which means $f$ is surjective. Thus $f$ is bijective. Conversely, if $f$ is bijective, then for any $y$ there is one and only one $x\in X$ such that $y=f(x)$. Define $g:Y\to X$ by $g(y)=x$ which is well-defined. Moreover $g(f(x))=g(y)=x$ and $f(g(y))=f(x)=y$ which shows that f is invertible and $f^{-1}=g$. $\square$