Transcript Chapter 7 Functions

Chapter 7 Functions
In Layman’s terms
A function f from a set X to another set Y is a recipe that
tells you how to convert an input number x to the output
number y.
Usually such a recipe is expressed in a formula, but we
also have:
Function defined by arrow diagrams
f
X
1
a
b
c
2
3
4
Note: this method works only for finite sets.
Y
Arrow diagram of a function with animation.
2
a
b
3
5
8
c
13
d
19
e
26
The following diagram does not represent a function,
do you know why?
2
a
b
3
5
8
c
13
d
19
e
26
Function as a set
a
A
2
f
b
c
d
e
3
5
8
13
B
19
26
The above function is defined as a set of ordered pairs:
f = {(a, 5), (b, 26), (c, 2), (d,8), (e, 13)}
and this set is a subset of A×B
7.1 Functions Defined on General Sets
Definition:
Given any two sets X and Y, a function f from X to Y is a subset of the
Cartesian product X ×Y such that
(a) for every a  X, there is one y  Y such that (a, y)  f
(b) if (a, y)  f and (a, z)  f , then y = z
(in other words, there is one and only one output for each input)
The set X is called the domain of f , Y is called the codomain, and
range of f = {b  Y : b = f (a) for some a  X}
Given any b  Y,
inverse image of b = f -1(b) = {a  X : f (a) = b}
and this set can be empty.
Functions defined on the set of bit strings
Let Σ = {0, 1} and Σ* be the set of all finite strings over Σ.
(1) Define g: Σ* → Σ* by
g(s) = the reverse of s from right to left.
eg. g(10111) = 11101
(2) Define f: Σ* × Σ* → Σ* by
f(s, t) = the concatenation of s followed by t.
eg. f (000, 1101) = 0001101
Check digit functions
The last digit of each UPC or ISBN is always created to catch
errors. In other words, there is a formula to compute the last
digit using all but the last digit as input. If this last digit does
not match the formula, we know that the number must be
wrong.
Example:
1. In the UPC 0-53600-10054-0, the last digit 0 is chosen
such that
0×3 + 5×1 + 3×3 + 6×1 + 0×3 + 0×1 + 1×3 + 0×1 + 0×3 + 5×1 + 4×3 + 0×1
is divisible by 10.
In dot product notation, this can be written as
[(0,5,3,6,0,0,1,0,0,5,4,0)  (3,1,3,1,3,1,3,1,3,1,3,1)] MOD 10 = 0
2. Each ISBN is a 10 digit number such as 0-88385-720-0.
The last digit a10 is chosen such that
[(0,8,8,3,8,5,7,2,0,a10)  (10,9,8,7,6,5,4,3,2,1)]MOD 11 = 0
In this case, a10 = 0 will work. And if a10 = 10, we use the letter X
instead.
In both examples, we see that there is always at most one output
from each input, these procedures of generating check digits are
functions even though they cannot be easily described by formulas.
Coding functions
A typical coding function usually assigns a unique
numeric code (often a binary code) to each input.
The three common reasons for assigning codes are
(1) secrecy (or privacy),
(2) data compression,
(3) error correction.
Examples of Error correcting Codes.
Hamming [7,4,3] binary linear code. (1950)
This is the 1st error detecting code (cannot correct error yet).
Each input is a binary sting of length 4, and the function will
add 3 check digits at the end and make the output a string of
length 7.
input
0000
0001
0010
0100
1000





output
0000000
0001011
0010111
0100101
1000110
input
output
1100  1100011
1010  1010001
….
etc.
It can detect 1 error out of the 7 bits, but cannot correct it.
Functions defined by formulas
Example:
f(x) = 3x2 + 5
for every x in .
g(x) = exsinx
for every x in .
7
These functions can also be
(partially) represented by
graphs instead of arrow
diagrams.
6
5
4
3
2
1
-5
-4
-3
x
-2
-1
00
-1
1
2
3
Examples
In mathematical analysis, many functions are defined by
descriptions rather than by formulas. All examples below
are functions from  to .
1. This function is discontinuous everywhere.
0 if x is rational
f ( x)  
1 if x is irrational
1
Examples
2. This function is continuous only at 0.
0 if x is rational
f ( x)  
 x if x is irrational
But it is not differentiable
anywhere.
3. This function is differentiable at 0 but is discontinuous
elsewhere.
0 if x is rational
f ( x)   2
 x if x is irrational
4. This function is continuous only at the irrationals.
f x  
1
q
if x is rat ionaland x 
0
if x is irrational
p
in reduced form
q
Remark: There is no function which is continuous only at the
rational numbers.
In 1872, Weierstrass published a paper that states that the
following function is continuous but nowhere differentiable.

f ( x)   (0.5) n cos(13n x)
n 0
(remark: He actually published a more general result.)
Space Filling Curve
In 1890, Giuseppe Peano discovered a continuous function from [0, 1] onto
the unit square [0,1] ×[0,1]. However, this function cannot be one-to-one.
The following function is due to David Hilbert, only the 1st 6 iterations are
shown, the final function is the limit of these iterations.
Equality of functions:
Suppose that both f and g are functions from X to Y, then we say that f is
equal to g, written f = g if and only if
for every a  X, f (a) = g(a)
Example:
f (x) = (x2 + x + 1) mod 3,
g(x) = (x + 2)2 mod 3
They are equal on the domain of integers.
Exercise
Let f be a function from  to  such that
1
f ( x)  2 f (
)x
1 x
whenever x  1.
Find the value of f ( 12 )
Reed-Solomon Codes
(1960)
The commercially used version for CD’s, DVD’s,
cellphones etc. is the [255,223,33]-code, in which
(i) Every codeword is a 255-byte string, hence 2040 bits.
(ii) In each codeword, 223 bytes are from the original
message (others are check digits)
(iii) It can correct up to 16 incorrect bytes (i.e. 16 bits in
16 different bytes in the worst case, and 16×8 bits in a
row in the best case.)
Finite-State Automata
A finite state automaton is a machine that can make a few
decisions, but it is much weaker than a computer because it
does not have an expandable memory and it can only run
one predetermined program.
Examples:
Vending machines,
Definition:
A finite-state automaton consists of five objects
1. a set I called the input alphabet, of input symbol;
2. a set S of states the automaton can be in;
3. a designate state s0 , called the initial state;
4. a designate set of states called the set of accepting states
5. a next-state function N : S × I  S
Finite-State Automaton
Simple Vending Machine – accepts only 25¢ or 50¢
- gives a bottle of soda for $1
- does not return changes
25¢
desposited
0¢
desposited
50¢
25¢
25¢
50¢
desposited
75¢
desposited
50¢
50¢
$1
or more
desposited
50¢
The Next-State Table
Original State
Input
Quarter
Half-Dollar
0¢ deposited
25¢ deposited
50¢ deposited
25¢ deposited
50¢ deposited
75¢ deposited
50¢ deposited
75¢ deposited
Accept
75¢ deposited
Accept
Accept
25¢ deposited
50¢ deposited
Accept
Next State in blue
Examples:
1. Construct a finite state automaton that accepts exactly the
set of strings of 0’s and 1’s that start with the pattern 110.
2. Construct a finite state automaton that accepts exactly the
set of strings of 0’s and 1’s for which the number of 1’s is
divisible by 3.
3. Construct a finite state automaton that accepts exactly the
set of strings of 0’s and 1’s that do not contain the pattern
1011.
Question
For any given set A of strings of 0’s and 1’s, can we build
a finite-state automaton that accepts exactly the strings in
the set A?
In particular, can we build one machine that accepts
exactly those strings where the number of 0’s is equal to
the number of 1’s?
And can we build one machine that accepts exactly those
strings that are palindromes? (eg. 0110110)
7.2 1-to-1, Onto, and Inverse functions
Definition:
Let F be a function from a set X to a set Y. F is one-to-one (or
injective) if, for all elements x1 and x2 in X
F ( x1)  F ( x2 )  x1  x2
Or equivalently,
x1  x2  F ( x1)  F ( x2 )
Different ways to check that a function is one-to-one
Let f be a function from a connected interval in  to  .
Then f is one-to-one if either of the following is true.
1.The graph of f passes the horizontal line test.
2. f is strictly increasing or strictly decreasing.
3. If f is differentiable, then f is one-to-one if f ’(x) > 0 for
all x or if f ’(x) < 0 for all x in the domain of f.
If f is defined on other domains, we have to use the definition
to prove “one-to-one”ness, or we can construct an inverse for
f.
This is a one-to-one function.
2
a
b
3
5
8
c
d
13
19
e
26
This is not a one-to-one function.
2
a
b
3
5
8
c
d
13
19
e
26
We can call this a many-to-one function.
Examples
1. The identity function id:  defined by
id (x) = x
is one-to-one
2. Any linear function f(x) = ax + b with a ≠ 0 is
one-to-one from  to .
Examples
3. Show that the function
x
f ( x) 
x5
is one-to-one throughout its domain.
4. Let S be the set of all finite strings of a’s, b’s and c’s.
Define C: S  S by
C(s) = a*s
for all sS
C is called concatenation, i.e. C(bbc) = abbc .
Show that C is one-to-one.
Sets of Sequences
Notations
a. 2 is the set of all functions from Z+ to 2 (which is the set
{0,1})
This is identified with the set of all infinite sequences of 0’s and 1’s.
such as 0,1,0,1,0,1,0,1, … or 0,1,0,1,1,0,1,1,1,0, …
b. 10 is the set of all functions from Z+ to 10 (which is the
set {0,1, 2, 3, 4, 5, 6, 7, 8, 9})
Similarly this is identified with the set of all infinite sequences of
digits;
such as 3,2,4,8,0,5,9,1, … or 4,2,4,2,4,2,4,2,4,2, …
More examples
a. The embedding function I: 2  10 defined by
I(s) = s for every s2
is one-to-one.
b. We now try to construct a function G: 10  2
which is one-to-one.
Properties of one-to-one functions.
1. If f(x):    is one-to-one, and a, b, c are constants with
a ≠ 0, b ≠ 0, then
a·f(bx) + c
is also one-to-one.
2. The composition of two or more one-to-one functions is
also one-to-one.
example: e sin(x) is one-to-one on the domain (-π/2, π/2).
Onto functions
Definition:
Let F be a function from a set X to a set Y. F is onto (or
surjective) if,
range of F = Y
Or equivalently,
y Y x  X ( F ( x)  y)
This function is not onto.
2
a
b
3
5
8
c
d
13
19
e
26
This function is onto
(even though not one-to-one).
3
a
b
8
c
d
e
19
Unfortunately there is no standard method to check
whether a function is onto or not.
Different functions may require different
techniques.
Whether a given function is onto or not onto depends on its
co-domain as well. If we can reduce the co-domain, we can
make a function onto.
Examples
The function f:   defined by f (x) = 4x + 1 is onto,
but
the function f: Z+  Z+ defined by f (n) = 4n + 1 is not onto.
More Examples
c. The polynomial p(x) = x3 – 4x + 2 is onto but not one-to-one.
d. There is an onto function H: 10  2 defined by
0 if f (n) is even
H ( f )(n)  
for every f 10
1 if f (n) is odd
but this function is not one-to-one.
e. Challenge: Can you construct an onto function
from 2 to 10 ?
Theorem
For any set S (finite or infinite), there is no onto function
from S to (S).
Proof:
It is only necessary to consider the case where S is infinite,
because if S is finite, we know that (S) has more elements.
Assume to the contrary that there is a onto function
f : S → (S)
We then consider the subset
A = { xS : xf(x) }
Inverse functions
Definition:
Let f be a function from a set X to a set Y.
If f is both one-to-one and onto, then we say that f is a bijection
or a one-to-one correspondence between X and Y.
Theorem:
Suppose that f : X  Y is a bijection, then there is a function
f -1 : Y  X defined by
f -1 (y) = the unique element x in X such that f (x) = y
Definition:
The function f -1 defined above is called the inverse of f.
Inverse functions
Theorem:
If X and Y are sets and f : X  Y is one-to-one and
onto, then
f -1 : Y  X
is also one-to-one and onto.
The following theorem provides a very convenient way to prove that
a function is one-to-one and onto.
Theorem:
If X and Y are sets and f : X  Y is a function. Suppose
further that there is a function g: Y  X such that
g ◦ f = IX : X  X
then f is one-to-one and onto.
Special cases
Suppose that both X and Y are finite sets and f : X → Y is a
function,
(1) if n(X) > n(Y), then f cannot be one-to-one,
(2) if n(X) < n(Y), then f cannot be onto,
(3) if n(X) = n(Y), and f is one-to-one, then f is also onto,
(4) if n(X) = n(Y), and f is onto, then f is also one-to-one.
Example
Let f : R → R be a continuous but non-constant function that
preserves addition and multiplication, i.e.
f (x + y) = f (x) + f (y) and f (x · y) = f (x) f (y)
Prove that f is one-to-one.
Solution:
We need to divide the proof into several steps.
(1) prove that f (0) = 0
(2) prove that f (-x) = - f (x)
(3) prove that f (x) = 0 implies that x = 0.
(4) prove that f (x) = f (y) implies that x = y.
In fact, we can prove (in exercise) that this f is actually the
identity function, hence it is also onto.
7.4 Cardinality with Applications
Definition:
A set S is called finite if there is no bijection between S and
a proper subset of S.
A set is called infinite if it is not finite.
(In other words, a set S is infinite if we can construct a bijection
from S to a proper subset of S.
Example:
The set of natural numbers N is infinite because we can
construct the bijective function
f(n) = n + 1
from N to a proper subset {1, 2, 3, 4, ··· } of N itself.
Theorem:
For any function f from a finite set X to a finite set Y, if
n(X) > n(Y), then f cannot be one-to-one.
This theorem is called the Pigeon hole Principle or the
Dirichlet box principle.
We shall study this principle in section 9.4
7.4 Cardinality and Applications
Definition:
Two sets A and B are said to have the same cardinality
i.e. card(A) = card(B)
if and only if there is a bijection between them.
Using the terminology of cardinality, we can redefine infinite sets.
Definition:
A set S is said to be infinite if S has at least one proper subset
W such that card(W) = card(S)
Examples
card({0,1,2,3,4,5, ··· }) = card ({0,2,4,6,8, ···}) = card ()
Exercises
1. Show that the interval (0, 1) has the same cardinality as the
longer interval (5, 8).
2. Show that the interval (0, 1) has the same cardinality as the
infinite interval (0, ∞).
3. Show that the interval (0, 1) has the same cardinality as the
infinite interval (-∞, ∞).
4. Show that the closed interval [0, 1] has the same cardinality
as the open interval (0, 1).
4. Show that the closed interval [0, 1] has the same cardinality
as the open interval (0, 1).
Solution:
Consider the function
 12
 1
f ( x)   n  2
x

if x  0
if x  1n for a postive integer n.
otherwise
It is not difficult to check that f is one-to-one and it
maps [0, 1] onto (0, 1)
Theorem
There is a one-to-one correspondence between the closed
interval [0,1] and the closed square [0,1]×[0,1].
Proof:
Let f : [0,1] → [0,1]×[0,1] be defined by
f (0.a1a2a3a4a5a6…) = (0.a1a3a5… , 0.a2a4a6…)
then f is bijective because it has an obvious inverse.
(remark: we use infinite decimal expansion for every real number,
i.e. 0.5 = 0.49999··· )
Definition:
Given any two sets A and B, we say that
card(A) ≤ card(B)
if there is a injection from A into B.
Schröder-Bernstein Theorem
Given two sets A and B,
if card(A) ≤ card(B) and card(A) ≥ card(B), then
card(A) = card(B).
Consequence of the Schröder-Bernstein Theorem
card (2ω ) = card(10ω )
In other words, the set of infinite binary sequences has the
same cardinality as the set of infinite decimal sequences.
A binary sequence can only use the digits 0 and 1, an
example is
{1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, … }
A decimal sequence can use the ten digits 0 to 9, an
example is
{2, 5, 6, 0, 4, 3, 3, 7, 8, 4, 8, 9, 1, 2, … }
Theorem
The set of real numbers has the same cardinality as the set
S = { x   : 0 < x < 1}
Proof: Consider the function
f ( x)  tan(
π
π
x )
2
2
which is one-to-one and maps (0, 1) exactly
onto (-∞, ∞).
Countable Sets
Definition:
A set S is said to be countably infinite if it has the same
cardinality as the set of natural numbers N.
A set S is said to be countable if it is either finite or countably
infinite.
Loosely speaking, a set is countable if you can put its
elements in a linear order such that every elements has only
finitely many predecessors.
A set S is said to be uncountable if it is not countable.
Theorem
(1) Any subset of a countable set is countable.
(2) The union of two countable sets is countable.
(3) The Cartesian product of any two countable sets is countable.
Examples:
(a) The set Z of integers is countable.
(b) The set Q of rational numbers is countable.
Axiom of countable choice
Any countable union of countable sets is countable.
(Note: this axiom cannot be proved by ZF.)
Theorem
The set Q+ of positive rational numbers is countable.
Proof:
1
,
1
2
,
1
3
,
1
4
,
1
5
,
1
6
,
1
1
,
2
2
,
2
3
,
2
4
,
2
5
,
2
6
,
2
1
,
3
2
,
3
3
,
3
4
,
3
5
,
3
6
,
3
1
,
4
2
,
4
3
,
4
4
,
4
5
,
4
6
,
4
1
,
5
2
,
5
3
,
5
4
,
5
5
,
5
6
,
5
1
,
6
2
,
6
3
,
6
4
,
6
5
,
6
6
,
6
1
,
7
2
,
7
3
,
7
4
,
7
5
,
7
6
,
7
Theorem
The set of real numbers in the interval [0, 1] is uncountable.
Proof: (Cantor Diagonalization method) By contradiction.
Suppose that we can arrange those numbers in a sequence {a1, a2, a3,  }
and since each number in the sequence is a decimal, we can write their
decimal forms as
a1 = 0.a11a12a13a14…
a2 = 0.a21a22a23a24…
a3 = 0.a31a32a33a34…
…
(here we use the non-terminating form if there are two choices, i.e. 1 =
0.999…)
Next we construct a number b whose decimal form is
b = 0.b1b2b3b4…
and such that bk = akk + 1 if akk < 9
and bk = 0
if akk = 9
Then b will be a real number between 0 and 1, but b is not equal to any of
the numbers in the list {a1, a2, a3, …}, a contradiction!
Definition
The first infinite ordinal number ω is defined to be the set
{0, 1, 2, 3,  }
ω +1 is defined to be the 2nd infinite ordinal number, and it is
the set {0, 1, 2, 3,  , ω}
(note: there is no ω – 1 because ω is not constructed by adding just one
more element to any set.)
ω + (n +1) is the set {0, 1, 2, 3,  , ω, ω+1, ω+2, , ω+n}
ω + ω is the set {0, 1, 2, 3,  , ω, ω+1, ω+2, ω+3, }
Theorem
ω + n is countable for any whole number n.
ω + ω is countable.
ω2 (= ω×ω) is countable.
ωn is countable for any whole number n.
ωω is uncountable.
Definition
2ω is the set of all functions from ω to 2 (={0, 1})
ωω is the set of all functions from ω to ω.
Theorem
(a) card(2ω) = card((ω))
(b) card(2ω) = card(ωω)
(c) card() = card(2ω)
Old Theorem Revisit
Theorem
Given any set S, the power set (S) has a strictly larger
cardinality than S.
This implies that we can construct sets with larger and larger
cardinalities using power sets:
S, (S),  ((S)), …
Comment
Since any set obtained from ω using set operations other
than power set is countable, Cantor conjectured the
following
Continuum Hypothesis
There is no set whose cardinality is strictly between that of
card(ω) and card((ω))
It turns out that this hypothesis is independent of the ZFC
axioms. (Paul Cohen, 1963)
General Continuum Hypothesis
For any infinite set X, there is no set whose cardinality is
strictly between that of card(X) and card((X))
Application in computer science
Theorem
Given any computer language, the set of programs in that
language is countable.
Corollary
The set of computable functions from ω to ω is countable.
But there are uncountably many functions from ω to ω.
Hence there are uncountably many functions from ω to ω that
are not computable (i.e. they cannot be generated by a
computer program.)
This means computers can never take over the jobs of human.