# Logic and Set Theory/Functions

## Definition, first examples

Definition (function):

Let ${\displaystyle S,T}$ be two sets. A function ${\displaystyle f:S\to T}$ is an object that associates to every ${\displaystyle s\in S}$ a unique element ${\displaystyle f(s)}$ of ${\displaystyle T}$.

That is, a function ${\displaystyle f}$ is something where you can put in any element ${\displaystyle s\in S}$ and you get a uniquely defined element ${\displaystyle f(s)\in T}$.

Example (shift function):

Let ${\displaystyle S=T=\mathbb {N} }$, the natural numbers (ie. ${\displaystyle \mathbb {N} =\{1,2,3,4,\ldots \}}$, an infinite set). Define ${\displaystyle f(n):=n+1}$ for ${\displaystyle n\in \mathbb {N} }$.

Example (identity function):

Let ${\displaystyle S}$ be any set, and ${\displaystyle T=S}$. Then the function defined by ${\displaystyle f(s)=s}$ for all ${\displaystyle s\in S}$ is called the identity function.

## Exercises

1. Suppose that ${\displaystyle X,Y,Z}$ are sets and ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to Z}$ are functions. Suppose further that ${\displaystyle g\circ f}$ is injective. Prove that ${\displaystyle f}$ is injective.
2. Prove that if ${\displaystyle X}$ is any set, then the identity on ${\displaystyle X}$ is injective.
3. Conclude that if ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to X}$ are two functions such that ${\displaystyle g\circ f=\operatorname {Id} _{X}}$, then ${\displaystyle f}$ is injective.
4. Do an analogous discussion for surjectivity.
5. Prove that if ${\displaystyle f:X\to Y}$ and ${\displaystyle g:Y\to X}$ are two functions such that ${\displaystyle g\circ f=\operatorname {Id} _{X}}$ and ${\displaystyle f\circ g=\operatorname {Id} _{Y}}$, then ${\displaystyle f}$ is bijective.