1.4 Functions, Relations, and Sequences

Functions

Definition

A function $ƒ$ from a set $A$ domain to a set $B$ codomain is a rule that assigns to each $x\in A$ a unique $ƒ\left(x\right)\in B$. Denote $ƒ:A\to B$.

Types of Functions

Injective (One-to-One): $ƒ\left(x_1\right)=ƒ\left(x_2\right)\to x_1=x_2$.

Surjective (Onto): $\forall y\in B\exists x\in A:ƒ\left(x\right)=y$

Bijective: Both injective and surjective; has an inverse ${ƒ}^{-1}:B\to A$.

Operations on Functions

Composition: Given $ƒ:A\to B$, $g:B\to C$, define $g○ƒ:B\to C$ by $(g○ƒ)\left(x\right)=g(ƒ\left(x\right))$.

Inverse Function: If $ƒ$ is bijective, then ${ƒ}^{-1}:B\to A$ satisfies ${ƒ}^{-1}(ƒ\left(x\right))=x$ and $ƒ({ƒ}^{-1}\left(y\right))=y$.

Relations

Definition

A relation $R$ on sets $A$ and $B$ is a subset $R\subseteq A\times B$. If $(a,b)\in R$, we write $aRb$.

Properties of Relations on a Set A

Reflexive: $\forall a\in A:(a,a)\in R$.

Symmetric: If $(a,b)\in R$, then $(b,a)\in R$.

Antisymmetric: If $(a,b)\in R$ and $(b,a)\in R$, then $a=b$.

Transitive: If $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Special Relations

Equivalence Relation: Reflexive, symmetric, and transitive. Partitions $A$ into equivalence classes.

Partial Order: Reflexive, antisymmetric, and transitive. Yields poset $(A,\le )$.

Sequences

Definition

A sequence is a function $a:\mathbb{N}\to S$, often denoted ${\left(a_n\right)}_{n\geqq 0}$ or ${\left\{a_n\right\}}_{n=0}^{\infty }$.

Types of Sequences

Finite Sequence: Defined for $n=01,\cdots ,N$.

Infinite Sequence: Defined for all $n\in \mathbb{N}$.

Arithmetic Sequence

Defined by $a_n=a_0+nd$. Sum of first $n$ terms: ${\sum }_{k=0}^n\left(a_k\right)=(n+1)\frac{a_0+a_n}{2}$.

Geometric Sequence

Defined by $a_n=a_0{r}^n$. Sum of first $n$ terms: ${\sum }_{k=0}^n(a_0{r}^k)=a_0\frac{1-r^{n+1}}{1-r}$ $;r\ne 1$.

Recurrence Relations

A relation defining $a_n$ in terms of previous terms, e.g. $a_{n+1}=p{a}_n+q{a}_{\text{n-1}}$ with initial conditions. Use characteristic equations to solve.