English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


Functions

Terminology

• Domain: set which holds the values to which we
apply the function

• Co-domain: 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 co-domain where each and
every element of the domain relates to one and only one
value in the co-domain

• 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 co-domain
– 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 co-domain

• 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 One-to-One (or Injective) Function iff

• F is NOT a One-to-One 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
one-to-one and onto

f:R→R
f(x)=3x-4

• Prove or give a counter example that f is one-to-one
use
def:

• Prove or give a counter example that f is onto
use
def:

One-to-One Correspondence
or Bijection

F:X →Y is bijective ↔ F:X →Y is one-to-one & 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 one-to-one

• 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 one-to-one; there must be at least
two elements in the domain that have the same
image in the co-domain.

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)=n2

f(n)=g(f(n))=g(n+1)=(n+1)2
g(n)=f(g(n))=f(n2)=n2+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)

One-to-One in Composition

• If f:X→Y and g:Y→Z are both one-to-one,

then f:X→Z is one-to-one

• If f:X→Y and g:Y→Z are both onto,
then f:X→Z is onto when Y = Y1

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 one-to-one 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

Real Numbers

• We’ll take just a part of this infinite set

Reals between 0 and 1 (non-inclusive)
– X = {x ∈ R| 0<x<1}

• All elements of X can be written as

Cantor’s Proof

• Assume the set X = {x∈R|0<x<1} is countable

• Then the elements in the set can be listed

• Select the digits on the diagonal

build a number

• d differs in the nth position from the nth in the list

All Reals

• Card.({x∈R|0<x<1} ) = Card.(R)

Positive Rationals Q +

• Card.(Q+) =?= Card.(Z)

log function properties
(from back cover of textbook)

definition of log :
 

Prev Next