In addition to sequences and sets, another fundamental building block of much of mathematics is a function. In the following definitions, $A$,$B$,$C$,$S$ are sets and $f,g,h$ are the lambda expressions.
Functions
| Name | Definition |
|---|---|
| Mapping notation | $f\colon A\to B \iff \langle f,A,B\rangle$ is a function from $A$ to $B$ |
| Function existence | If $\forall a \in A.\exists! b \in B.\mc{P}(a,b)$ then $\exists f.f:A\to B \xand \forall x \in A.\mc{P}(x,f(x))$ |
| Function rule | If $f = (\alpha\mapsto \mc{P}(\alpha))$ then $f(x)=\mc{P}(x)$ |
| Alt. function notation | $A\overset{f}{\to}B\iff f\colon A\to B$ |
| Domain | Codomain | $\xdomain\left(f\right)=A\xand\xcodomain\left(f\right)=B\iff f\colon A\to B$ |
| Function equality | $f=g \iff f:A\to B \xand g:A\to B \xand \forall x\in A.f(x)=g(x)$ |
| Graph of a function | $f\colon\!A\to B\implies \xgraph _ f = \Set{ z : z= \langle x,f(x)\rangle \xand x\in A \text{ for some }x }$ |
| Alt. def of graph | $\left\langle x,y\right\rangle\in \xgraph _ f \iff x\in A\xand y=f(x)$ |
| Image | $y\in f\left(S\right)\iff \exists x\in S. y=f\left(x\right)$ |
| Range | $\xrange\left(f\right)=f\left(\xdomain\left(f\right)\right)$ |
| Identity Map | $\xid _ {A}:A\to A\xand\forall x.\xid _ {A}\left(x\right)=x$ |
| Composition | $A\overset{f}{\to}B\xand B\overset{g}{\to}C\implies A\overset{g\circ f}{\longrightarrow} C\xand\forall x.\left(g\circ f\right)\left(x\right)=g\left(f\left(x\right)\right)$ |
| Injective (one-to-one) | $f$ is injective $\iff~\,\forall x.\forall y.f\left(x\right)=f\left(y\right)\implies x=y$ |
| Surjective (onto) | $f$ is surjective $\iff \forall y.\exists x.y=f\left(x\right)$ |
| Bijective | $f$ is bijective $\iff$ $f$ is injective and $f$ is surjective |
| Inverse | If $f\colon A\to B$ and $f$ is bijective then $f^{-1}:B\to A$ and $f\circ f^{-1}=\xid _ {B}$ and $f^{-1}\circ f=\xid _ {A}$ |
| Inverse Image | $f\colon A\to B$ and $S\subseteq B\implies f^{\xinv}(S)=\Set{ x\in A : f(x)\in S } $ |
When deriving rules of inference from these definitions, it is helpful to note the following important theorem about inverse functions and bijections.
Theorem. A function has an inverse function if and only if it is bijective.
Functions
Declare maps, inv, $\circ$, injective, surjective, bijective
Function Application If $f\colon A\to B$ and $x\in A$ then $f(x)\in B$.
Function Rule If $f=x\mapsto\mc{P}(x)$ then $f(z)=\mc{P}(z)$.
Function existence
Given
Let $a\in A$
$\exists! b \in B. \mc{P}(a,b)$
Conclude $\exists f.f\colon A\to B \xand \forall x \in A.\mc{P}(x,f(x))$
Function Equality
Given
$f\colon A \to B$
$g\colon A \to B$
Let x in A
$f(x)=g(x)$
Conclude $f=g$
Image of a Set If $x\in S$ then $f(x)\in f(S)$.
Image of a Set If $y\in f(S)$ then $y=f(x)$ for some $x\in S$.
Identity Map $\xid_A\colon A\to A$ and $\xid_A(x)=x$.
Composition If $f\colon A\to B$ and $g\colon B\to C$ then $g\circ f\colon A\to C$ and $(g\circ f)(x)=g(f(x))$.
Injective If $f$ is injective and $f(x)=f(y)$ then $x=y$.
Surjective If $f\colon A\to B$, $f$ is surjective and $b\in B$ then $b=f(a)$ and $a\in A$ for some $a$.
Injective
Given
Let $x, y$ be such that $f(x)=f(y)$
$x=$
Conclude $f$ is injective
Surjective
Given
Let $b\in B$ $b=f(a)$ and $a\in A$
Conclude $f$ is surjective
Bijective
$f$ is bijective $\equiv f$ is injective
, $f$ is surjective
Inverse Map If $f\colon A\to B$ and $f$ is bijective then $f^{-1}\colon B \to A$, $f^{-1}(a)=a$ and $f(f^{-1}(b))=b$.
Inverse Image $a\in f^\xinv(S) \equiv f(a)\in S$
Inverse Image If $f\colon A\to B$ and $U\subseteq B$ then $f^\xinv(U)\subseteq A$.
Remarks:
In the following problems, capital letters represent sets.
Composition is associative If $h\colon A\to B$, $g\colon B\to C$, and $f\colon C\to D$ then
$$f\circ (g\circ h)=(f\circ g)\circ h$$
Nonsurjective injection Suppose $f\colon \bbN\to\bbN$ and for all $n\in\bbN, f(n)=3n+1$. Then $f$ is injective but not surjective.
Yet this is both Suppose $f\colon \bbR\to\bbR$ and $f(x)=3x+1$ for all $x\in\bbR$. Then $f$ is bijective.
Noninjective Suppose $f\colon \bbQ\to\bbQ$ and $f( r )=r^2$ for all rational numbers $r$. Then $f$ is not injective.
Tiny function If $A=\Set{1}$ and $G=\Set{(1,1)}$ then there exists a function $f:A\to A$ such that $G$ is the graph of $f$.
Image of subsets If $f\colon A \to B$ and $S\subseteq T$ and $T\subseteq A$ then $f(S)\subseteq f(T)$.
A bijection with a proper subset Let $E=\Set{ n\in\bbN : n\text{ is even}}$, and define $f\colon \bbN\to E$ such that $f(n)=2n$ for all $n\in\bbN$. Then $f$ is a bijection.
Composition of injective is injective If $f\colon A\to B$ and $g\colon B\to C$ are both injective then $g\circ f$ is injective.
Composition of surjective is surjective If $f\colon A\to B$ and $g\colon B\to C$ are both surjective then $g\circ f$ is surjective.
Composition of bijective is bijective If $f\colon A\to B$ and $g\colon B\to C$ are both bijective then $g\circ f$ is bijective.
Complement is bijective Let $A$ be a set and define $f\colon \mathcal{P}(A)\to \mathcal{P}(A)$ such that $f(X)=X’$ for all $X\in\mathcal{P}(A)$. Then $f$ is a bijection. Note that in this situation $X’$ refers to $A-X$, i.e., $A$ is the universal set.
Inverse of a composition If $f\colon A\to B$ and $g\colon B\to C$ are both bijective then $$(g\circ f)^{-1}=f^{-1}\circ g^{-1}$$
Identity maps are bijective The function $\xid _ A$ is bijective.
Inverse image of codomain If $f\colon A\to B$ then $f^{\xinv}(B)=A$.
Image of the inverse image If $f\colon A\to B$ is surjective and $S\subseteq B$ then $f(f^{\xinv}(S))=S$.
Inverse image of the image If $f\colon A\to B$ is injective and $S\subseteq A$ then $f^{\xinv}(f(S))=S$.
Identity for composition If $f\colon A\to A$ then $f\circ \xid _ A=f$ and $\xid _ A\circ f=f$.
linear bijections A linear function is bijective if and only if it has nonzero slope. Here we define a linear function to be a map $f\colon \bbR\to\bbR$ such that for some $m,b\in\bbR$, $$f(x)=m\cdot x+b$$ In this situation we say that $m$ is the slope of $f$.
a real example Define $\left(,0…1\right]$ to be the set $\Set{x\in\bbR : 0<x\leq 1}$ and let $f\colon \bbR\to\left(,0…1\right]$ be the function such that for all real numbers $x$, $$f(x)=\frac{1}{1+x^2}$$ Then $f$ is surjective but not injective.
We often identify a function with its graph. From that perspective, a function $f\colon A\to B$ is a subset of $A\times B$ that satisfies certain conditions. We can generalize this concept to other subsets of $A\times B$. Such a set is called a relation from $A$ to $B$. In the case where $A=B$ we say that such a set defines a relation on $A$. Relations are often categorized by the properties they satisfy. Some of the more common properties of relations are described in the following table.
While we can have relations between any two sets, one of the most important special cases is the situation where a relation is from a set to itself. This provides a convenient way to describe relationships between the elements of the set. In the following $A$, $B$, $S$ and $T$ are sets.
Relations
| Name | Definition |
|---|---|
| Def of relation | $\sim$ is a relation from $A$ to $B~\iff\,\sim\subseteq A\times B$ |
| Infix notation | $x\sim y~\iff\,\tuple{x,y}\in\,\sim$ |
| Relation on a set | $\sim$ is a relation on $A~\iff\,\sim\,\subseteq A\times A$ |
| Equivalence Relations | |
| Reflexive relation | $\sim$ is reflexive $\iff~\forall x\in A.x\sim x$ |
| Symmetric relation | $\sim$ is symmetric $\iff~\forall x\in A.\forall y\in A.x\sim y\ximplies y\sim x$ |
| Transitive relation | $\sim$ is transitive $\iff~\forall x\in A.\forall y\in A.\forall z\in A. x\sim y\xand y\sim z\ximplies x\sim z$ |
| Equivalence Relation | $\sim$ is an equivalence relation $\iff~\sim $ is reflexive, symmetric, and transitive. |
| Equivalence Class | $\sim$ is an equivalence relation and $a\in A\ximplies\left[a\right] _ {\sim } =\Set{ x\in A : x\sim a } $ |
| Partition of a set | $P$ is a partition of $A~\equiv$ (a) $P\subseteq\mathscr{P}(A)$ (b) $\Set{}\notin P$ (c) $A=\bigcup\limits _{S\in P}S$ (d) $\forall S\in P.\forall T\in P.S=T\xor S\cap T=\Set{}$ |
| congruent mod $m$ | if $m\in\bbN^+$ and $a,b\in\bbZ$ then $a \xcong{m} b\iff m\mid a-b$ |
| Properties | |
| Irreflexive relation | $\sim$ is irreflexive $\iff~\forall x\in A.\neg(x\sim x)$ |
| Antisymmetric relation | $\sim$ is antisymmetric $\iff~\forall x\in A.\forall y\in A.x\sim y\xand y\sim x\ximplies x=y$ |
| Total relation | $\sim$ is total$\iff~\forall x\in A.\forall y\in A.x\sim y\xor y\sim x$ |
| Order | |
| Partial order | $\sim$ is a partial order $\iff~\sim $ is reflexive, antisymmetric, and transitive. |
| Strict Partial order | $\sim$ is a strict partial order $\iff~\sim $ is irreflexive, antisymmetric, and transitive. |
| Total Order | $\sim$ is total order $\iff~\sim $ is antisymmetric, transitive, and total. |
We often abbreviate $\left[a\right] _ {\sim}$ by $\left[a\right]$ when the relation $\sim$ is clear from context. There is a close relationship between equivalence relations, equivalence classes, and partitions give by the following theorem.
Theorem Let $\sim\,\subseteq A\times A$ be an equivalence relation and $a,b\in A$. Then $$\left[a\right]=\left[b\right]\iff a\sim b$$
Corollary Let $\sim\,\subseteq A\times A$ be an equivalence relation. Then $A$ is a disjoint union of equivalence classes, i.e. $$A=\bigcup _ {a\in A}\left[a\right]$$ and $$\forall a.b\in A,\left[a\right]=\left[b\right]\xor\left[a\right]\cap\left[b\right]=\Set{}$$
Thus, the set of equivalence classes of an equivalence relation on $A$ is a partition of $A$. Furthermore, every partition $P$ of $A$ is the set of equivalence classes for the equivalence relation $\sim$ on $A$ defined by $$\forall x.y\in A,x\sim y\iff\exists S\in P,x\in S\xand y\in S$$.
Relations
Declare $\sim$, reflexive, symmetric, transitive, irreflexive, antisymmetric, total, class, partial order, strict partial order, total order, equivalence relation and partition to be constants.
Relations as sets of pairs
$x\sim y ~\equiv~ \langle x,y\rangle\in\,\sim$
Relation on a set
$\sim$ is a relation on $A~ \equiv ~\sim \,\subseteq A\times
A$
Relation on a set
If $\sim$ is a relation on $A$ and
$x\sim y$ then
$x\in A$ and
$y\in A$.
Equivalence Relations
Reflexive
Given
$\sim$ is a relation on $A$
Let $x\in A$
$x\sim x$
Conclude $\sim$ is reflexive
Symmetric
Given
$\sim$ is a relation on $A$
Let $x,y$ be such that $x\sim y$
$y\sim x$
Conclude $\sim$ is symmetric
Reflexive If $\sim$ is a relation on $A$ and $\sim$ is reflexive then $x\sim x$.
Symmetric If $\sim$ is a relation on $A$, $\sim$ is symmetric and $x\sim y$ then $y\sim x$.
Transitive
Given
$\sim$ is a relation on $A$
Let $x,y,z$ be such that $x\sim y$ and $y\sim z$
$x\sim z$
Conclude $\sim$ is transitive
Equivalence Relation If $\sim$ is a relation on $A$
$\sim$ is an equivalence relation $\equiv$
(a) $\sim$ is reflexive,
(b) $\sim$ is symmetric,
(c) $\sim$ is transitive
Transitive If $\sim$ is a relation on $A$, $\sim$ is transitive, $x\sim y$ and $y\sim z$ then $x\sim z$.
Equivalence Class
If $\sim$ is an equivalence relation
then
$x \sim a ~ \equiv ~ x\in [a]$
Partition
If $P$ is a partition of $A$ then
$P\subseteq \mathscr{P}$ and
$\displaystyle A=\bigcup_{S\in P} S$.
Partition If $P$ is a partition of $A$, $~S\in P$ and $T\in P$ then $S = T \xor S\cap T = \Set{}$
Partition
Given
$A=\bigcup_{S\in P} S$
Let $S, T$ be such that $S\in P$ and $T\in P$
$S = T \xor S\cap T = \Set{}$
Conclude $P$ is a partition of $A$
Congruence mod $m$ $a \xcong{m} b~\equiv~ m\mid a-b$
Other Properties of Relations on a Set
Irreflexive
Given
$\sim$ is a relation on $A$
Let $x\in A$
not $x\sim x$
Conclude $\sim$ is irreflexive
Antisymmetric
Given
$\sim$ is a relation on $A$
Let $x,y$ be such that $x\sim y$ and $y \sim x$
$x=y$
Conclude $\sim$ is antisymmetric
Irreflexive If $\sim$ is a relation on $A$, $\sim$ is irreflexive, and $x\in A$ then not $x\sim x$.
Antisymmetric If $\sim$ is a relation on $A$, $\sim$ is antisymmetric, $x\sim y$ and $y \sim x$ then $x=y$.
Total
Given
$\sim$ is a relation on $A$
Let $x,y$ be such that $x\in A$ and $y \in A$
$x\sim y$ or $y\sim x$
Conclude $\sim$ is total
Total If $\sim$ is a relation on $A$, $\sim$ is total, $x\sim y$ and $y \sim x$ then $x=y$.
Orders
Partial Order If $\sim$ is a relation on $A$
$\sim$ is a partial order $\equiv$
(a) $\sim$ is reflexive,
(b) $\sim$ is antisymmetric,
(c) $\sim$ is transitive
Strict Partial Order If $\sim$ is a relation on $A$
$\sim$ is a strict partial order $\equiv$
(a) $\sim$ is irreflexive,
(b) $\sim$ is antisymmetric,
(c) $\sim$ is total
Total Order If $\sim$ is a relation on $A$
$\sim$ is an total order $\equiv$
(a) $\sim$ is antisymmetric,
(b) $\sim$ is transitive,
(c) $\sim$ is total
In the following problems, capital letters represent sets.
Not an equivalence relation Suppose $\sim$ is the set $$\sim = \Set{ \langle1,1\rangle,\langle2,2\rangle,\langle3,3\rangle,\langle1,2\rangle,\langle2,1\rangle,\langle1,3\rangle,\langle3,1\rangle}$$ Then $\sim$ is not an equivalence relation on the set $\Set{1,2,3}$.
Not not an equivalence relation If $\sim$ is a relation on $\bbZ$ such that for all $x,y\in\bbZ$, $$x\sim y\iff x=y \xor x=\negative{y}$$ then $\sim$ is an equivalence relation.
equivalence relation induced by a function If $f\colon A\to B$ and $\sim$ is a relation on $A$ such that for all $x,y\in A$, $$x\sim y\iff f(x)=f(y)$$ then $\sim$ is an equivalence relation.
an equivalence relation? Let $\sim$ be the relation on $\mathcal{P}(\bbZ)$ such that for all $A,B\in\mathcal{P}(\bbZ)$, $$A\sim B\iff \exists z\in \bbZ,z\in A\cap B$$ Prove your answer to the following questions.
an equivalence relation? Let $z\in\bbZ$. Define $\sim _ z$ be the relation on $\mathcal{P}(\bbZ)$ such that for all $A,B\in\mathcal{P}(\bbZ)$, $$A\sim _ z B\iff z\in A\cap B$$ Prove your answer to the following questions.
Congruence is an equivalence relation Let $m$ be a positive integer. The relation $\xcong{m}$ is an equivalence relation on any set of integers.
class representatives mod $m$ Let $m$ be a positive integer. For any integer $n$ there exists a unique integer $k$ with $0\leq k<m$ such that $n\xcong{m} k$.
moduli are zeroish Let $m\in\bbN^+$ and $a,k\in\bbZ$. Then $a\xcong{m}a+k\cdot m$
modular addition Let $m\in\bbN^+$ and $a,b,c,d\in\bbZ$. If $a\xcong{m}b$ and $c\xcong{m}d$ then $a+c\xcong{m}b+d$.
modular multiplication Let $m\in\bbN^+$ and $a,b,c,d\in\bbZ$. If $a\xcong{m}b$ and $c\xcong{m}d$ then $a\cdot c\xcong{m}b\cdot d$.
Equivalence classes are disjoint If $\sim$ is an equivalence relation on a set $A$ and $x,y\in A$ then either $[x]=[y]$ or $[x]\cap [y]=\Set{}$.
A partial order Let $A$ be a set and $\sim$ be the relation on $\mathcal{P}(A)$ such that for every $S,T\in\mathcal{P}(A)$, $$S\sim T \iff S\subseteq T$$ Then $\sim$ is a partial order.
A strict partial order Define $A=\Set{ X\subseteq\bbN : 0\in X }$. For any $S\in A$ and $n\in\bbN$ we say $S$ is $n$-complete if and only if $\bbO _ n$ is a subset of $S$ and $\bbO _ {n+1}$ is not a subset of $S$. Let $\sim$ be a relation on $A$ such that for all $S,T\in A$, $$S\sim T\iff\exists m.\exists n.m<n\xand S\text{ is $m$-complete}\xand T\text{ is $n$-complete}$$ Then $\sim$ is a strict partial order.
