Lesson 1 &2 -Set Theory and Functions.ppt

for sale

1. Discrete Structures 1
Set TheorySet Theory

2. 2
Learning Outcome;
•Describe memberships of sets, including the empty set, using
proper notation, and decide whether given items are members
and determine the cardinality of a given set.
•Describe the relations between sets regarding membership,
equality, subset, and proper subset, using proper notation.
•Perform the operations of union, intersection, complement, and
difference on sets using proper notation.
•Recognize when set theory is applicable to real-life situations,
solve real-life problems, and communicate real-life problems
and solutions to others.
Understanding that inputs and outputs are a set of points that
satisfy a relation
Recognizing that relations can be represented as ordered pairs,
tables, mapping diagrams, or graphs
Finding the rule that satisfies the inputs and the corresponding
outputs of a table

3. Discrete Structures 3
Set TheorySet Theory
•Set: Collection of objects (called Set: Collection of objects (called elementselements))
•aaAA “a is an element of A” “a is an element of A”
“a is a member of A” “a is a member of A”
•aaAA “a is not an element of A” “a is not an element of A”
•A = {aA = {a
11, a, a
22, …, a, …, a
nn} } “A contains a“A contains a
11, …, a, …, a
nn””
•Order of elements is insignificantOrder of elements is insignificant
•It does not matter how often the same It does not matter how often the same
element is listed (repetition doesn’t count).element is listed (repetition doesn’t count).

4. 4
Set EqualitySet Equality
Sets A and B are equal if and only if they Sets A and B are equal if and only if they
contain exactly the same elements.contain exactly the same elements.
Examples:Examples:
• A = {9, 2, 7, -3}, B = {7, 9, -3, 2} :A = {9, 2, 7, -3}, B = {7, 9, -3, 2} :A = BA = B
• A = {dog, cat, horse}, A = {dog, cat, horse},
B = {cat, horse, squirrel, dog} : B = {cat, horse, squirrel, dog} :A A  B B
• A = {dog, cat, horse}, A = {dog, cat, horse},
B = {cat, horse, dog, dog} : B = {cat, horse, dog, dog} : A = BA = B

5. 5
Examples for SetsExamples for Sets
““Standard” Sets:Standard” Sets:
•Natural numbers Natural numbers NN = {0, 1, 2, 3, …} = {0, 1, 2, 3, …}
•Integers Integers ZZ = {…, -2, -1, 0, 1, 2, …} = {…, -2, -1, 0, 1, 2, …}
•Positive Integers Positive Integers ZZ
++
= {1, 2, 3, 4, …} = {1, 2, 3, 4, …}
•Real Numbers Real Numbers RR = {47.3, -12, = {47.3, -12, , …}, …}
•Rational Numbers Rational Numbers QQ = {1.5, 2.6, -3.8, 15, …} = {1.5, 2.6, -3.8, 15, …}
(correct definitions will follow)(correct definitions will follow)

6. Discrete Structures 6
Examples for SetsExamples for Sets
•A = A =  “empty set/null set”“empty set/null set”
•A = {z}A = {z} Note: zNote: zA, but z A, but z  {z} {z}
•A = {{b, c}, {c, x, d}}A = {{b, c}, {c, x, d}} set of setsset of sets
•A = {{x, y}} A = {{x, y}} Note: {x, y} Note: {x, y} A, but {x, y} A, but {x, y}  {{x, y}} {{x, y}}
•A = {x | P(x)} A = {x | P(x)} “set of all x such that P(x)”“set of all x such that P(x)”
P(x) is the P(x) is the membership functionmembership function of set A of set A
x (P(x) x (P(x)  x xA)A)
•A = {x | xA = {x | x NN  x > 7} = {8, 9, 10, …}x > 7} = {8, 9, 10, …}
“set builder notation”“set builder notation”

7. Discrete Structures 7
Examples for SetsExamples for Sets
We are now able to define the set of rational We are now able to define the set of rational
numbers Q:numbers Q:
QQ = {a/b | a = {a/b | aZZ  bbZZ
++
}, }, or or
QQ = {a/b | a = {a/b | aZZ  bbZ Z  bb0} 0}
And how about the set of real numbers R?And how about the set of real numbers R?
RR = {r | r is a real number} = {r | r is a real number}
That is the best we can do. It can neither be That is the best we can do. It can neither be
defined by enumeration nor builder function.defined by enumeration nor builder function.

8. 8
SubsetsSubsets
A A  B B “A is a subset of B” “A is a subset of B”
A A  B if and only if every element of A is also B if and only if every element of A is also
an element of B. an element of B.
We can completely formalize this:We can completely formalize this:
A A  B B  x (xx (xA A xxB)B)
Examples:Examples:
A = {3, 9}, B = {5, 9, 1, 3}, A A = {3, 9}, B = {5, 9, 1, 3}, A  B ? B ?truetrue
A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A 
B ?B ?
falsefalse
truetrue
A = {1, 2, 3}, B = {2, 3, 4}, A A = {1, 2, 3}, B = {2, 3, 4}, A 
B ?B ?

9. 9
SubsetsSubsets
Useful rules:Useful rules:
•A = B A = B  (A (A  B) B)  (B (B A) A)
•(A (A  B) B) (B (B  C) C)  A A  C C (see Venn Diagram)(see Venn Diagram)
UU
AA
BB
CC

10. 10
SubsetsSubsets
Useful rules:Useful rules:
  A for any set A A for any set A
(but (but   A may not hold for any set A) A may not hold for any set A)
•AA  A for any set A A for any set A
Proper subsets:Proper subsets:
A A  B B “A is a proper subset of B”“A is a proper subset of B”
A A  B B  x (xx (xA A  x xB) B)  x (xx (xB B  x xA)A)
oror
A A  B B  x (xx (xA A  x xB) B)  x (xx (xB B xxA) A)

11. 11
Cardinality of SetsCardinality of Sets
If a set S contains n If a set S contains n distinctdistinct elements, n elements, nNN,,
we call S a we call S a finite setfinite set with with cardinality ncardinality n..
Examples:Examples:
A = {Mercedes, BMW, Porsche}, |A| = 3A = {Mercedes, BMW, Porsche}, |A| = 3
B = {1, {2, 3}, {4, 5}, 6}B = {1, {2, 3}, {4, 5}, 6} |B| = 4|B| = 4
C =

C =

|C| = 0|C| = 0
D = { x

D = { x

N N | x 7000 }

| x 7000 }

|D| = 7001|D| = 7001
E = { x

E = { x

N N | x 7000 }

| x 7000 }

E is infinite!E is infinite!

12. 12
The Power SetThe Power Set
P(A) P(A) “power set of A” (also written as “power set of A” (also written as 22
AA
))
P(A) = {B | B P(A) = {B | B  A} A} (contains all subsets of A)(contains all subsets of A)
Examples:Examples:
A = {x, y, z}A = {x, y, z}
P(A)P(A)

= {= {, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}
A = A = 
P(A) = {P(A) = {}}
Note: |A| = 0, |P(A)| = 1Note: |A| = 0, |P(A)| = 1

13. 13
The Power SetThe Power Set
Cardinality of power sets: Cardinality of power sets: | P(A) | = 2| P(A) | = 2
|A||A|
•Imagine each element in A has an “Imagine each element in A has an “onon//offoff” switch” switch
•Each possible switch configuration in A Each possible switch configuration in A
corresponds to one subset of A, thus one element corresponds to one subset of A, thus one element
in P(A)in P(A)
zzzzzzzzzzzzzzzzzz
yyyyyyyyyyyyyyyyyy
xxxxxxxxxxxxxxxxxx
8877665544332211AA
•For 3 elements in A, there are For 3 elements in A, there are
22222 = 8 elements in P(A)2 = 8 elements in P(A)

14. 14
Cartesian ProductCartesian Product
The The ordered n-tupleordered n-tuple (a (a
11, a, a
22, a, a
33, …, a, …, a
nn) is an ) is an
ordered collectionordered collection of n objects. of n objects.
Two ordered n-tuples (aTwo ordered n-tuples (a
11, a, a
22, a, a
33, …, a, …, a
nn) and ) and
(b(b
11, b, b
22, b, b
33, …, b, …, b
nn) are equal if and only if they ) are equal if and only if they
contain exactly the same elements contain exactly the same elements in the same in the same
orderorder, i.e. a, i.e. a
ii = b = b
ii for 1 for 1  i i  n. n.
The The Cartesian productCartesian product of two sets is defined as: of two sets is defined as:
AAB = {(a, b) | aB = {(a, b) | aA A  b bB}B}

15. 15
Cartesian ProductCartesian Product
Example:Example:
A = {good, bad}, B = {student, prof}A = {good, bad}, B = {student, prof}
AAB = {B = {
(good, student),(good, student), (good, prof),(good, prof), (bad, student),(bad, student), (bad, prof)(bad, prof)}}
(prof, bad)(prof, bad)}} (student, good),(student, good), (prof, good),(prof, good), (student, bad),(student, bad), B A = {

B A = {

Example:Example: A = {x, y}, B = {a, b, c} A = {x, y}, B = {a, b, c}
A B = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}

A B = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}


16. 16
Set OperationsSet Operations
Union: AUnion: AB = {x | xB = {x | xA A  x xB}B}
Example:Example: A = {a, b}, B = {b, c, d} A = {a, b}, B = {b, c, d}
AAB = {a, b, c, d} B = {a, b, c, d}
Intersection: AIntersection: AB = {x | xB = {x | xA A  x xB}B}
Example:Example: A = {a, b}, B = {b, c, d} A = {a, b}, B = {b, c, d}
AAB = {b}B = {b}
Cardinality: |ACardinality: |AB| = |A| + |B| - |AB| = |A| + |B| - |AB|B|

17. 17
Set OperationsSet Operations
Two sets are called Two sets are called disjointdisjoint if their intersection if their intersection
is empty, that is, they share no elements:is empty, that is, they share no elements:
AAB = B = 
The The differencedifference between two sets A and B between two sets A and B
contains exactly those elements of A that are contains exactly those elements of A that are
not in B:not in B:
A-B = {x | xA-B = {x | xA A  x xB}B}
Example: Example: A = {a, b}, B = {b, c, d}, A-B = {a}A = {a, b}, B = {b, c, d}, A-B = {a}
Cardinality: |A-B| = |A| - |ACardinality: |A-B| = |A| - |AB|B|

18. 18
Set OperationsSet Operations
The The complementcomplement of a set A contains exactly of a set A contains exactly
those elements under consideration that are not those elements under consideration that are not
in A: denoted Ain A: denoted A
c c
(or as in the text)(or as in the text)
AA
cc
= U-A = U-A
Example: Example: U = U = NN, B = {250, 251, 252, …}, B = {250, 251, 252, …}
BB
cc
= {0, 1, 2, …, 248, 249} = {0, 1, 2, …, 248, 249}
A

19. 19
Set IdentitySet Identity
Table 1 in Section 1.7 shows many useful equations Table 1 in Section 1.7 shows many useful equations
–Identity laws, Identity laws, AA = A = A, , AAU = AU = A
–Domination laws, Domination laws, AAU = UU = U, , AA = = 
–Idempotent laws, Idempotent laws, AAA = AA = A, , AAAA = = AA
–Complementation law, Complementation law, ((AA
cc
))
cc
= A= A
–Commutative laws, Commutative laws, AAB =B = B BA, AA, AB = BB = BAA
–Associative laws, Associative laws, AA(B(B  C) = (A C) = (AB)B)CC, …, …
–Distributive laws, Distributive laws, AA(B(BC) = (AC) = (AB)B)(A(AC)C), …, …
–De Morgan’s laws, De Morgan’s laws, (A(AB)B)
c c
= = AA
cc
BB
c, c,
(A(AB)B)
c c
= = AA
cc
BB
cc
–Absorption laws,Absorption laws, AA(A(AB) = AB) = A, , AA(A(AB) = AB) = A
–Complement laws,Complement laws,AAAA
cc
= U, A = U, AAA
cc
= = 

20. 20
Set OperationsSet Operations
Method : Membership tableMethod : Membership table
1 means “x is an element of this set”1 means “x is an element of this set”
0 means “x is not an element of this set” 0 means “x is not an element of this set”
11111111111 1 11 1 1
11111111001 1 01 1 0
11111111001 0 11 0 1
11111111001 0 01 0 0
11111111110 1 10 1 1
00001100000 1 00 1 0
00110000000 0 10 0 1
00000000000 0 00 0 0
(A(AB) B) (A(AC)C)AACCAABBAA(B(BC)C)BBCCA B CA B C

21. 21
FunctionsFunctions

22. Discrete Structures 22
FunctionsFunctions
A A functionfunction f from a set A to a set B is an f from a set A to a set B is an
assignmentassignment of of exactly oneexactly one element of B to element of B to eacheach
element of A.element of A.
We writeWe write
f(a) = bf(a) = b
if b is the unique element of B assigned by the if b is the unique element of B assigned by the
function f to the element a of A.function f to the element a of A.
If f is a function from A to B, we writeIf f is a function from A to B, we write
f: Af: ABB
(note: Here, “(note: Here, ““ has nothing to do with if… then)“ has nothing to do with if… then)

23. Discrete Structures 23
FunctionsFunctions
If f:AIf f:AB, we say that A is the B, we say that A is the domaindomain of f and B of f and B
is the is the codomaincodomain of f. of f.
If f(a) = b, we say that b is the If f(a) = b, we say that b is the imageimage of a and a is of a and a is
the the pre-imagepre-image of b. of b.
The The rangerange of f:A of f:AB is the set of all images of B is the set of all images of allall
elements of A.elements of A.
We say that f:AWe say that f:AB B mapsmaps A to B. A to B.

24. Discrete Structures 24
FunctionsFunctions
Let us take a look at the function f:PLet us take a look at the function f:PC withC with
P = {Linda, Max, Kathy, Peter}P = {Linda, Max, Kathy, Peter}
C = {Boston, New York, Hong Kong, Moscow}C = {Boston, New York, Hong Kong, Moscow}
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = New Yorkf(Peter) = New York
Here, the range of f is C.Here, the range of f is C.

25. 25
FunctionsFunctions
Let us re-specify f as follows:Let us re-specify f as follows:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
Is f still a function?Is f still a function?yesyes
{Moscow, Boston, Hong Kong}{Moscow, Boston, Hong Kong}What is its range?What is its range?

26. 26
FunctionsFunctions
Other ways to represent f:Other ways to represent f:
BostonBostonPeterPeter
Hong Hong
KongKong
KathyKathy
BostonBostonMaxMax
MoscowMoscowLindaLinda
f(x)f(x)xx
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow

27. 27
FunctionsFunctions
If the domain of our function f is large, it is If the domain of our function f is large, it is
convenient to specify f with a convenient to specify f with a formulaformula, e.g.:, e.g.:
f:f:RRRR
f(x) = 2xf(x) = 2x
This leads to:This leads to:
f(1) = 2f(1) = 2
f(3) = 6f(3) = 6
f(-3) = -6f(-3) = -6
……

28. 28
FunctionsFunctions
Let fLet f
11 and f and f
22 be functions from A to be functions from A to RR..
Then the Then the sumsum and the and the productproduct of f of f
11 and f and f
22 are also are also
functions from A to functions from A to RR defined by: defined by:
(f(f
11 + f + f
22)(x) = f)(x) = f
11(x) + f(x) + f
22(x)(x)
(f(f
11ff
22)(x) = f)(x) = f
11(x) f(x) f
22(x)(x)
Example:Example:
ff
11(x) = 3x, f(x) = 3x, f
22(x) = x + 5(x) = x + 5
(f(f
11 + f + f
22)(x) = f)(x) = f
11(x) + f(x) + f
22(x) = 3x + x + 5 = 4x + 5(x) = 3x + x + 5 = 4x + 5
(f(f
11ff
22)(x) = f)(x) = f
11(x) f(x) f
22(x) = 3x (x + 5) = 3x(x) = 3x (x + 5) = 3x
22
+ 15x + 15x

29. Discrete Structures 29
FunctionsFunctions
We already know that the We already know that the rangerange of a function of a function
f:Af:AB is the set of all images of elements aB is the set of all images of elements aA.A.
If we only regard a If we only regard a subsetsubset S SA, the set of all A, the set of all
images of elements simages of elements sS is called the S is called the imageimage of S. of S.
We denote the image of S by f(S):We denote the image of S by f(S):
f(S) = {f(s) | sf(S) = {f(s) | sS}S}

30. 30
FunctionsFunctions
Let us look at the following well-known function:Let us look at the following well-known function:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
What is the image of S = {Linda, Max} ?What is the image of S = {Linda, Max} ?
f(S) = {Moscow, Boston}f(S) = {Moscow, Boston}
What is the image of S = {Max, Peter} ?What is the image of S = {Max, Peter} ?
f(S) = {Boston}f(S) = {Boston}

31. 31
Properties of FunctionsProperties of Functions
A function f:AA function f:AB is said to be B is said to be one-to-oneone-to-one (or (or
injectiveinjective), if and only if), if and only if
x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
In other words:In other words: f is one-to-one if and only if it f is one-to-one if and only if it
does not map two distinct elements of A onto the does not map two distinct elements of A onto the
same element of B.same element of B.

32. 32
Properties of FunctionsProperties of Functions
And again…And again…
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
Is f one-to-one?Is f one-to-one?
No, Max and Peter are No, Max and Peter are
mapped onto the same mapped onto the same
element of the image.element of the image.
g(Linda) = Moscowg(Linda) = Moscow
g(Max) = Bostong(Max) = Boston
g(Kathy) = Hong Kongg(Kathy) = Hong Kong
g(Peter) = New Yorkg(Peter) = New York
Is g one-to-one?Is g one-to-one?
Yes, each element is Yes, each element is
assigned a unique assigned a unique
element of the image.element of the image.

33. 33
Properties of FunctionsProperties of Functions
How can we prove that a function f is one-to-one?How can we prove that a function f is one-to-one?
Whenever you want to prove something, first take Whenever you want to prove something, first take
a look at the relevant definition(s):a look at the relevant definition(s):
x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
Example:Example:
f:f:RRRR
f(x) = xf(x) = x
22
Disproof by counterexample:
f(3) = f(-3), but 3 f(3) = f(-3), but 3  -3, so f is not one-to-one. -3, so f is not one-to-one.

34. 34
Properties of FunctionsProperties of Functions
… … and yet another example:and yet another example:
f:f:RRRR
f(x) = 3xf(x) = 3x
One-to-one: One-to-one: x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
To show:To show: f(x) f(x)  f(y) whenever x f(y) whenever x  y ( y (indirect proofindirect proof))
x x  y y
 3x 3x  3y 3y
 f(x) f(x)  f(y), f(y),
so if x so if x  y, then f(x) y, then f(x)  f(y), that is, f is one-to-one. f(y), that is, f is one-to-one.

35. 35
Properties of FunctionsProperties of Functions
A function f:AA function f:AB with A,B B with A,B  R is called R is called strictly strictly
increasingincreasing, if , if
x,yx,yA (x < y A (x < y  f(x) < f(y)), f(x) < f(y)),
and and strictly decreasingstrictly decreasing, if, if
x,yx,yA (x < y A (x < y  f(x) > f(y)). f(x) > f(y)).
Obviously, a function that is either strictly Obviously, a function that is either strictly
increasing or strictly decreasing is increasing or strictly decreasing is one-to-oneone-to-one..

36. 36
Properties of FunctionsProperties of Functions
A function f:AA function f:AB is called B is called ontoonto, or , or surjectivesurjective, if , if
and only if for every element band only if for every element bB there is an B there is an
element aelement aA with f(a) = b.A with f(a) = b.
In other words, f is onto if and only if its In other words, f is onto if and only if its rangerange is is
its its entire codomainentire codomain..
A function f: AA function f: AB is a B is a one-to-one correspondenceone-to-one correspondence, ,
or a or a bijectionbijection, if and only if it is both one-to-one , if and only if it is both one-to-one
and onto.and onto.
Obviously, if f is a bijection and A and B are finite Obviously, if f is a bijection and A and B are finite
sets, then |A| = |B|.sets, then |A| = |B|.

37. Discrete Structures 37
Properties of FunctionsProperties of Functions
Examples:Examples:
In the following examples, we use the arrow In the following examples, we use the arrow
representation to illustrate functions f:Arepresentation to illustrate functions f:AB. B.
In each example, the complete sets A and B are In each example, the complete sets A and B are
shown.shown.

38. Discrete Structures 38
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No.No.
Is f surjective?Is f surjective?
No.No.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow

39. Discrete Structures 39
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No.No.
Is f surjective?Is f surjective?
Yes.Yes.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
PaulPaul

40. Discrete Structures 40
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
Yes.Yes.
Is f surjective?Is f surjective?
No.No.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeck

41. Discrete Structures 41
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No! f is not evenNo! f is not even
a function!a function!
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeck

42. Discrete Structures 42
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
Yes.Yes.
Is f surjective?Is f surjective?
Yes.Yes.
Is f bijective?Is f bijective?
Yes.Yes.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeckHelenaHelena

43. Discrete Structures 43
InversionInversion
An interesting property of bijections is that An interesting property of bijections is that
they have an they have an inverse functioninverse function..
The The inverse functioninverse function of the bijection f:A of the bijection f:AB is B is
the function fthe function f
-1-1
:B:BA with A with
ff
-1-1
(b) = a whenever f(a) = b. (b) = a whenever f(a) = b.

44. Discrete Structures 44
InversionInversion
Example:Example:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Lf(Peter) = Lüübeckbeck
f(Helena) = New Yorkf(Helena) = New York
Clearly, f is bijective.Clearly, f is bijective.
The inverse function fThe inverse function f
--
11
is given by: is given by:
ff
-1-1
(Moscow) = Linda(Moscow) = Linda
ff
-1-1
(Boston) = Max(Boston) = Max
ff
-1-1
(Hong Kong) = Kathy(Hong Kong) = Kathy
ff
-1-1
(L(Lüübeck) = Peterbeck) = Peter
ff
-1-1
(New York) = Helena(New York) = Helena
Inversion is only Inversion is only
possible for bijectionspossible for bijections
(= invertible functions)(= invertible functions)

45. 45
InversionInversion
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeckHelenaHelena
ff
ff
-1-1
ff
-1-1
:C:CP is no P is no
function, because function, because
it is not defined it is not defined
for all elements of for all elements of
C and assigns two C and assigns two
images to the pre-images to the pre-
image New York.image New York.

46. 46
CompositionComposition
The The compositioncomposition of two functions g:A of two functions g:AB and B and
f:Bf:BC, denoted by fC, denoted by fg, is defined by g, is defined by
(f(fg)(a) = f(g(a))g)(a) = f(g(a))
This means that This means that
• firstfirst, function g is applied to element a, function g is applied to element aA,A,
mapping it onto an element of B, mapping it onto an element of B,
• thenthen, function f is applied to this element of , function f is applied to this element of
B, mapping it onto an element of C. B, mapping it onto an element of C.
• ThereforeTherefore, the composite function maps , the composite function maps
from A to C. from A to C.

47. 47
CompositionComposition
Example:Example:
f(x) = 7x – 4, g(x) = 3x,f(x) = 7x – 4, g(x) = 3x,
f:f:RRRR, g:, g:RRRR
(f(fg)(5) = f(g(5)) = f(15) = 105 – 4 = 101g)(5) = f(g(5)) = f(15) = 105 – 4 = 101
(f(fg)(x) = f(g(x)) = f(3x) = 21x - 4g)(x) = f(g(x)) = f(3x) = 21x - 4

48. 48
CompositionComposition
Composition of a function and its inverse:Composition of a function and its inverse:
(f(f
-1-1
f)(x) = ff)(x) = f
-1-1
(f(x)) = x(f(x)) = x
The composition of a function and its inverse The composition of a function and its inverse
is the is the identity functionidentity function i(x) = x. i(x) = x.