# Logic and Set Theory/Functions

## Definition, first examples

Definition (function):

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

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

Example (shift function):

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

Example (identity function):

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

## Exercises

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