
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Discrete Mathematics - Functions
A Function assigns to each element of a set, exactly one element of a related set. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. The third and final chapter of this part highlights the important aspects of functions.
Function - Definition
A function or mapping (Defined as $f: X \rightarrow Y$) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function f.
Function f is a relation on X and Y such that for each $x \in X$, there exists a unique $y \in Y$ such that $(x,y) \in R$. x is called pre-image and y is called image of function f.
A function can be one to one or many to one but not one to many.
Injective / One-to-one function
A function $f: A \rightarrow B$ is injective or one-to-one function if for every $b \in B$, there exists at most one $a \in A$ such that $f(s) = t$.
This means a function f is injective if $a_1 \ne a_2$ implies $f(a1) \ne f(a2)$.
Example
$f: N \rightarrow N, f(x) = 5x$ is injective.
$f: N \rightarrow N, f(x) = x^2$ is injective.
$f: R\rightarrow R, f(x) = x^2$ is not injective as $(-x)^2 = x^2$
Surjective / Onto function
A function $f: A \rightarrow B$ is surjective (onto) if the image of f equals its range. Equivalently, for every $b \in B$, there exists some $a \in A$ such that $f(a) = b$. This means that for any y in B, there exists some x in A such that $y = f(x)$.
Example
$f : N \rightarrow N, f(x) = x + 2$ is surjective.
$f : R \rightarrow R, f(x) = x^2$ is not surjective since we cannot find a real number whose square is negative.
Bijective / One-to-one Correspondent
A function $f: A \rightarrow B$ is bijective or one-to-one correspondent if and only if f is both injective and surjective.
Problem
Prove that a function $f: R \rightarrow R$ defined by $f(x) = 2x 3$ is a bijective function.
Explanation − We have to prove this function is both injective and surjective.
If $f(x_1) = f(x_2)$, then $2x_1 3 = 2x_2 3 $ and it implies that $x_1 = x_2$.
Hence, f is injective.
Here, $2x 3= y$
So, $x = (y+5)/3$ which belongs to R and $f(x) = y$.
Hence, f is surjective.
Since f is both surjective and injective, we can say f is bijective.
Inverse of a Function
The inverse of a one-to-one corresponding function $f : A \rightarrow B$, is the function $g : B \rightarrow A$, holding the following property −
$f(x) = y \Leftrightarrow g(y) = x$
The function f is called invertible, if its inverse function g exists.
Example
A Function $f : Z \rightarrow Z, f(x)=x+5$, is invertible since it has the inverse function $ g : Z \rightarrow Z, g(x)= x-5$.
A Function $f : Z \rightarrow Z, f(x)=x^2$ is not invertiable since this is not one-to-one as $(-x)^2=x^2$.
Composition of Functions
Two functions $f: A \rightarrow B$ and $g: B \rightarrow C$ can be composed to give a composition $g o f$. This is a function from A to C defined by $(gof)(x) = g(f(x))$
Example
Let $f(x) = x + 2$ and $g(x) = 2x + 1$, find $( f o g)(x)$ and $( g o f)(x)$.
Solution
$(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$
$(g o f)(x) = g (f(x)) = g(x + 2) = 2 (x+2) + 1 = 2x + 5$
Hence, $(f o g)(x) \neq (g o f)(x)$
Some Facts about Composition
If f and g are one-to-one then the function $(g o f)$ is also one-to-one.
If f and g are onto then the function $(g o f)$ is also onto.
Composition always holds associative property but does not hold commutative property.