Try our Free Online Math Solver!

Functions
• Domain: set which holds the values to which we
apply the function
• Codomain: set which holds the possible values
(results) of the function
• Range: set of actual values received when applying
the function to the values of the domain
Function
• A “total” function is a relationship between elements of
the
domain and elements of the codomain where each and
every element of the domain relates to one and only one
value in the codomain
• A “partial” function does not need to map every element
of
the domain.
• f: X →Y
– f is the function name
– X is the domain
– Y is the codomain
– x ∈X y ∈Y f sends x to y
– f(x) = y f of x ; value of f at x ; image of x under f
Formal Definitions
• Range of f = {y ∈Y  ∃x ∈X,
f(x) = y}
– where X is the domain and Y is the codomain
• Inverse image of y = {x ∈X f(x) = y}
– the set of things that map to y
• Arrow Diagrams
– Determining if they are functions using the
Arrow Diagram
Teminology of Functions
• Equality of Functions
∀f,g
∈{functions}, f=g ↔ ∀x∈X,
f(x)=g(x)
• F is a OnetoOne (or Injective) Function iff
• F is NOT a OnetoOne Function iff
• F is an Onto (or Surjective) Function iff
∀y
∈Y
∃x∈X,
F(x) = y
• F is NOT an Onto Function iff
∃y∈Y
∀x
∈X, F(x)
y
Proving functions
onetoone and onto
f:R→R
f(x)=3x4
• Prove or give a counter example that f is onetoone
use
def:
• Prove or give a counter example that f is onto
use
def:
OnetoOne Correspondence
or Bijection
F:X →Y is bijective ↔ F:X →Y is onetoone & onto
• F:X →Y is bijective ↔ It has an inverse function
Proving something is a bijection
• F:Z→Z
F(x)=x+1
• Prove it is onetoone
• Prove it is onto
• Then it is a bijection
• So it has an inverse function
– find F^{1}
Pigeonhole Principle
• Basic Form
A function from one finite set to a smaller finite
set cannot be onetoone; there must be at least
two elements in the domain that have the same
image in the codomain.
Examples
• Using this class as the domain,
Must two people share a birthmonth?
Must two people share a birthday?
• A = {1,2,3,4,5,6,7,8}
If I select 5 integers at random from this set,
must two of the numbers sum to 9?
If I select 4 integers?
Other (more useful) Forms of the
Pigeonhole Principle
• Generalized Pigeonhole Principle
– For any function f from a finite set X to a finite set Y and for any
positive integer k, if n(X) > k*n(Y), then there is some y ∈Y
such that y is the image of at least k +1 distinct elements of X.
• Contrapositive Form of Generalized Pigeonhole Principle
– For any function f from a finite set X to a finite set Y and for any
positive integer k, if for each y ∈Y, f^{1}(y) has at most k elements,
then X has at most k*n(Y) elements.
Examples
• Using Generalized Form:
– Assume 50 people in the room, how many must share the same
birthmonth?
– n(A)=5 n(B)=3 F:P(A)→P(B)
How many elements of P(A) must map to a single element of P(B)?
• Using Contrapositive of the Generalized Form:
– G:X→Y where Y is the set of 2 digit integers that do not have
distinct digits. Assuming no more than 5 elements of X can map
to a single element of Y, how big can X be?
– You have 5 busses and 100 students. No bus can carry over 25
students. Show that at least 3 busses must have over 15 students
each.
Composition of Functions
Composition on finite sets
• Example
– X = {1,2,3} Y1 = {a,b,c,d} Y={a,b,c,d,e} Z =
{x,y,z}
Composition for infinite sets
f:Z →Z
f(n)=n+1
g:Z →Z
g(n)=n^{2}
f(n)=g(f(n))=g(n+1)=(n+1)^{2}
g(n)=f(g(n))=f(n^{2})=n^{2}+1
note:
Identity function
•
the identity function for the domain X
• the identity function for the domain Y
• composition with the identity functions
Composition of a function with
its inverse function
• Composing a function with its inverse
returns you to the starting place.
(note: f:X→Y and f^{1}: Y→X)
OnetoOne in Composition
• If f:X→Y and g:Y→Z are both onetoone,
then f:X→Z is onetoone
• If f:X→Y and g:Y→Z are both onto,
then
f:X→Z is onto when Y = Y_{1}
Cardinality
• Comparing the “sizes” of sets
– finite sets ( or has a bijective function from it to
{1,2,…,n})
– infinite sets (can’t have a bijective function from it to
{1,2,…,n})
•
∀A,B ∈{sets}, A and B have the same cardinality
↔ there is a onetoone correspondence from A to B
In other words,
Card(A) = Card(B) ↔∃ f ∈{functions}, f:A→B ∧ f is a
bijection
Countability of sets of integers
is a countably infinite set
is a countably infinite set
is a countably infinite set
is also a countably infinite set
• We’ll take just a part of this infinite set
• Reals between 0 and 1 (noninclusive)
– X = {x ∈ R 0<x<1}
• All elements of X can be written as
Cantor’s Proof
• Assume the set X = {x∈R0<x<1} is countable
• Then the elements in the set can be listed
• Select the digits on the diagonal
• d differs in the n^{th} position from the n^{th} in the list
• Card.({x∈R0<x<1} ) = Card.(R)
Positive Rationals Q ^{+}
• Card.(Q^{+}) =?= Card.(Z)
log function properties
(from back cover of textbook)
Prev  Next 