المحاضرة الثامنة هياكل متقطعة

Sets and set operations: cont.
Functions.
Set identities
Set Identities (analogous to logical equivalences)
• Identity
– A ? = A
– A U = A
• Domination
– A U = U
– A ? = ?
• Idempotent
– A A = A
– A A = A
?
?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Double complement
– A = A
• Commutative
– A B = B A
– A B = B A
• Associative
– A (B C) = (A B) C
– A (B C) = (A B) C
• Distributive
– A (B C) = (A B) (A C)
– A (B C) = (A B) (A C)
? ?
? ? ? ?
? ? ?
? ?
? ?
? ? ? ?
? ?
? ? ?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• DeMorgan
– (A B) = A B
– (A B) = A B
• Absorbtion Laws
– A (A B) = A
– A (A B) = A
• Complement Laws
– A A = U
– A A = ?
? ?
? ?
? ?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Set identities can be proved using membership tables.
• List each combination of sets that an element can belong to.
Then show that for each such a combination the element either
belongs or does not belong to both sets in the identity.
• Prove: (A ? B) = A B
A B
_
A
_
B
____
A B
_ _
A B
1 1 0 0 0 0
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1
?
? ?
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and itersections
Definition: The union of a collection of sets is the set that
contains those elements that are members of at least one set
in the collection.
Example:
• Let Ai= {1,2,...,i} i =1,2,...,n
•
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ?
{1 , 2 ,..., }
1
A n
n
i
i ?
? ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and intersections
Definition: The intersection of a collection of sets is the set that
contains those elements that are members of all sets in the
collection.
Example:
• Let Ai = {1,2,...,i} i =1,2,...,n
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ? }
1
{
1
?
? ? n
i
i A
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
• How to represent sets in the computer?
• One solution: Data structures like a list
• A better solution:
• Assign a bit in a bit string to each element in the universal set
and set the bit to 1 if the element is present otherwise use 0
Example:
All possible elements: U={1 2 3 4 5}
• Assume A={2,5}
– Computer representation: A = 01001
• Assume B={1,5}
– Computer representation: B = 10001
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
Example:
• A = 01001
• B = 10001
• The union is modeled with a bitwise or
• A ? B = 11001
• The intersection is modeled with a bitwise and
• A ? B = 00001
• The complement is modeled with a bitwise negation
• A =10110
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
9
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example1:
• Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as:
• 1 ? c
• 2 ? a
• 3 ? c
• Is f a function ?
• Yes. since f(1)=c, f(2)=a, f(3)=c. each element of A is assigned
an element from B
10
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 2:
• Let A = {1,2,3} and B = {a,b,c}
• Assume g is defined as
• 1 ? c
• 1 ? b
• 2 ? a
• 3 ? c
• Is g a function?
• No. g(1) = is assigned both c and b.
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 3:
• A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
• Define h: A ? B as:
• h(x) = x mod 3.
• (the result is the remainder after the division by 3)
• Assignments:
• 0 ?0 3 ? 0
• 1?1 4 ? 1
• 2 ? 2 …
11
M. Hauskrecht
Important sets
Definitions: Let f be a function from A to B.
• We say that A is the domain of f and B is the codomain of f.
• If f(a) = b, b is the image of a and a is a pre-image of b.
• The range of f is the set of all images of elements of A. Also, if
f is a function from A to B, we say f maps A to B.
Example: Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as: 1 ? c, 2 ? a, 3 ? c
• What is the image of 1?
• 1 ? c c is the image of 1
• What is the pre-image of a?
• 2 ? a 2 is a pre-image of a.
• Domain of f ? {1,2,3}
• Codomain of f ? {a,b,c}
• Range of f ? {a,c}
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = ?
A f: A ? B B
S
f(S)
12
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = {c}.
A f: A ? B B
S
f(S)
M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternate: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective Injective function
13
M. Hauskrecht
Injective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
– 1 ? c
– 2 ? a
– 3 ? c
• Is f one to one? No, it is not one-to-one since f(1) = f(3) = c, and
1 ? 3.
Example 2: Let g : Z ? Z, where g(x) = 2x - 1.
• Is g is one-to-one (why?)
• Yes.
• Suppose g(a) = g(b), i.e., 2a - 1 = 2b - 1 => 2a = 2b
`` => a = b.
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
14
M. Hauskrecht
Surjective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? c
• Is f an onto?
• No. f is not onto, since b ? B has no pre-image.
Example 2: A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
– Define h: A ? B as h(x) = x mod 3.
• Is h an onto function?
• Yes. h is onto since a pre-image of 0 is 6, a pre-image of 1 is 4, a
pre-image of 2 is 8.
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
15
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f is a bijection? Yes. It is both one-to-one and onto.
• Note: Let f be a function from a set A to itself, where A is finite.
f is one-to-one if and only if f is onto.
• This is not true for A an infinite set. Define f : Z ? Z, where
f(z) = 2 * z. f is one-to-one but not onto (3 has no pre-image).
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = [n/2] (floor function).
• 0 ? [0/2] = [0] = 0
• 1 ? [1/2] = [1/2] = 0
• 2 ? [2/2] = [1] = 1
• 3 ? [3/2] = [3/2] = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.
Set identities
Set Identities (analogous to logical equivalences)
• Identity
– A ? = A
– A U = A
• Domination
– A U = U
– A ? = ?
• Idempotent
– A A = A
– A A = A
?
?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Double complement
– A = A
• Commutative
– A B = B A
– A B = B A
• Associative
– A (B C) = (A B) C
– A (B C) = (A B) C
• Distributive
– A (B C) = (A B) (A C)
– A (B C) = (A B) (A C)
? ?
? ? ? ?
? ? ?
? ?
? ?
? ? ? ?
? ?
? ? ?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• DeMorgan
– (A B) = A B
– (A B) = A B
• Absorbtion Laws
– A (A B) = A
– A (A B) = A
• Complement Laws
– A A = U
– A A = ?
? ?
? ?
? ?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Set identities can be proved using membership tables.
• List each combination of sets that an element can belong to.
Then show that for each such a combination the element either
belongs or does not belong to both sets in the identity.
• Prove: (A ? B) = A B
A B
_
A
_
B
____
A B
_ _
A B
1 1 0 0 0 0
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1
?
? ?
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and itersections
Definition: The union of a collection of sets is the set that
contains those elements that are members of at least one set
in the collection.
Example:
• Let Ai= {1,2,...,i} i =1,2,...,n
•
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ?
{1 , 2 ,..., }
1
A n
n
i
i ?
? ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and intersections
Definition: The intersection of a collection of sets is the set that
contains those elements that are members of all sets in the
collection.
Example:
• Let Ai = {1,2,...,i} i =1,2,...,n
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ? }
1
{
1
?
? ? n
i
i A
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
• How to represent sets in the computer?
• One solution: Data structures like a list
• A better solution:
• Assign a bit in a bit string to each element in the universal set
and set the bit to 1 if the element is present otherwise use 0
Example:
All possible elements: U={1 2 3 4 5}
• Assume A={2,5}
– Computer representation: A = 01001
• Assume B={1,5}
– Computer representation: B = 10001
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
Example:
• A = 01001
• B = 10001
• The union is modeled with a bitwise or
• A ? B = 11001
• The intersection is modeled with a bitwise and
• A ? B = 00001
• The complement is modeled with a bitwise negation
• A =10110
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
9
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example1:
• Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as:
• 1 ? c
• 2 ? a
• 3 ? c
• Is f a function ?
• Yes. since f(1)=c, f(2)=a, f(3)=c. each element of A is assigned
an element from B
10
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 2:
• Let A = {1,2,3} and B = {a,b,c}
• Assume g is defined as
• 1 ? c
• 1 ? b
• 2 ? a
• 3 ? c
• Is g a function?
• No. g(1) = is assigned both c and b.
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 3:
• A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
• Define h: A ? B as:
• h(x) = x mod 3.
• (the result is the remainder after the division by 3)
• Assignments:
• 0 ?0 3 ? 0
• 1?1 4 ? 1
• 2 ? 2 …
11
M. Hauskrecht
Important sets
Definitions: Let f be a function from A to B.
• We say that A is the domain of f and B is the codomain of f.
• If f(a) = b, b is the image of a and a is a pre-image of b.
• The range of f is the set of all images of elements of A. Also, if
f is a function from A to B, we say f maps A to B.
Example: Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as: 1 ? c, 2 ? a, 3 ? c
• What is the image of 1?
• 1 ? c c is the image of 1
• What is the pre-image of a?
• 2 ? a 2 is a pre-image of a.
• Domain of f ? {1,2,3}
• Codomain of f ? {a,b,c}
• Range of f ? {a,c}
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = ?
A f: A ? B B
S
f(S)
12
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = {c}.
A f: A ? B B
S
f(S)
M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternate: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective Injective function
13
M. Hauskrecht
Injective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
– 1 ? c
– 2 ? a
– 3 ? c
• Is f one to one? No, it is not one-to-one since f(1) = f(3) = c, and
1 ? 3.
Example 2: Let g : Z ? Z, where g(x) = 2x - 1.
• Is g is one-to-one (why?)
• Yes.
• Suppose g(a) = g(b), i.e., 2a - 1 = 2b - 1 => 2a = 2b
`` => a = b.
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
14
M. Hauskrecht
Surjective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? c
• Is f an onto?
• No. f is not onto, since b ? B has no pre-image.
Example 2: A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
– Define h: A ? B as h(x) = x mod 3.
• Is h an onto function?
• Yes. h is onto since a pre-image of 0 is 6, a pre-image of 1 is 4, a
pre-image of 2 is 8.
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
15
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f is a bijection? Yes. It is both one-to-one and onto.
• Note: Let f be a function from a set A to itself, where A is finite.
f is one-to-one if and only if f is onto.
• This is not true for A an infinite set. Define f : Z ? Z, where
f(z) = 2 * z. f is one-to-one but not onto (3 has no pre-image).
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = [n/2] (floor function).
• 0 ? [0/2] = [0] = 0
• 1 ? [1/2] = [1/2] = 0
• 2 ? [2/2] = [1] = 1
• 3 ? [3/2] = [3/2] = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.
Set identities
Set Identities (analogous to logical equivalences)
• Identity
– A ? = A
– A U = A
• Domination
– A U = U
– A ? = ?
• Idempotent
– A A = A
– A A = A
?
?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Double complement
– A = A
• Commutative
– A B = B A
– A B = B A
• Associative
– A (B C) = (A B) C
– A (B C) = (A B) C
• Distributive
– A (B C) = (A B) (A C)
– A (B C) = (A B) (A C)
? ?
? ? ? ?
? ? ?
? ?
? ?
? ? ? ?
? ?
? ? ?
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• DeMorgan
– (A B) = A B
– (A B) = A B
• Absorbtion Laws
– A (A B) = A
– A (A B) = A
• Complement Laws
– A A = U
– A A = ?
? ?
? ?
? ?
?
?
?
?
CS 441 Discrete mathematics for CS M. Hauskrecht
Set identities
• Set identities can be proved using membership tables.
• List each combination of sets that an element can belong to.
Then show that for each such a combination the element either
belongs or does not belong to both sets in the identity.
• Prove: (A ? B) = A B
A B
_
A
_
B
____
A B
_ _
A B
1 1 0 0 0 0
1 0 0 1 0 0
0 1 1 0 0 0
0 0 1 1 1 1
?
? ?
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and itersections
Definition: The union of a collection of sets is the set that
contains those elements that are members of at least one set
in the collection.
Example:
• Let Ai= {1,2,...,i} i =1,2,...,n
•
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ?
{1 , 2 ,..., }
1
A n
n
i
i ?
? ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Generalized unions and intersections
Definition: The intersection of a collection of sets is the set that
contains those elements that are members of all sets in the
collection.
Example:
• Let Ai = {1,2,...,i} i =1,2,...,n
{ ... } 1 2
1
n
n
i
i A ? A ? A ? ? A
? ? }
1
{
1
?
? ? n
i
i A
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
• How to represent sets in the computer?
• One solution: Data structures like a list
• A better solution:
• Assign a bit in a bit string to each element in the universal set
and set the bit to 1 if the element is present otherwise use 0
Example:
All possible elements: U={1 2 3 4 5}
• Assume A={2,5}
– Computer representation: A = 01001
• Assume B={1,5}
– Computer representation: B = 10001
CS 441 Discrete mathematics for CS M. Hauskrecht
Computer representation of sets
Example:
• A = 01001
• B = 10001
• The union is modeled with a bitwise or
• A ? B = 11001
• The intersection is modeled with a bitwise and
• A ? B = 00001
• The complement is modeled with a bitwise negation
• A =10110
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Functions
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
9
M. Hauskrecht
Functions
• Definition: Let A and B be two sets. A function from A to B,
denoted f : A ? B , is an assignment of exactly one element of
B to each element of A. We write f(a) = b to denote the
assignment of b to an element a of A by the function f.
A f: A ?B B
Not allowed !!!
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example1:
• Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as:
• 1 ? c
• 2 ? a
• 3 ? c
• Is f a function ?
• Yes. since f(1)=c, f(2)=a, f(3)=c. each element of A is assigned
an element from B
10
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 2:
• Let A = {1,2,3} and B = {a,b,c}
• Assume g is defined as
• 1 ? c
• 1 ? b
• 2 ? a
• 3 ? c
• Is g a function?
• No. g(1) = is assigned both c and b.
M. Hauskrecht
Representing functions
Representations of functions:
1. Explicitly state the assignments in between elements of the
two sets
2. Compactly by a formula. (using ‘standard’ functions)
Example 3:
• A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
• Define h: A ? B as:
• h(x) = x mod 3.
• (the result is the remainder after the division by 3)
• Assignments:
• 0 ?0 3 ? 0
• 1?1 4 ? 1
• 2 ? 2 …
11
M. Hauskrecht
Important sets
Definitions: Let f be a function from A to B.
• We say that A is the domain of f and B is the codomain of f.
• If f(a) = b, b is the image of a and a is a pre-image of b.
• The range of f is the set of all images of elements of A. Also, if
f is a function from A to B, we say f maps A to B.
Example: Let A = {1,2,3} and B = {a,b,c}
• Assume f is defined as: 1 ? c, 2 ? a, 3 ? c
• What is the image of 1?
• 1 ? c c is the image of 1
• What is the pre-image of a?
• 2 ? a 2 is a pre-image of a.
• Domain of f ? {1,2,3}
• Codomain of f ? {a,b,c}
• Range of f ? {a,c}
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = ?
A f: A ? B B
S
f(S)
12
M. Hauskrecht
Image of a subset
Definition: Let f be a function from set A to set B and let S be a
subset of A. The image of S is a subset of B that consists of the
images of the elements of S. We denote the image of S by f(S),
so that f(S) = { f(s) | s ? S }.
Example:
• Let A = {1,2,3} and B = {a,b,c} and f: 1 ? c, 2 ? a, 3 ? c
• Let S = {1,3} then image f(S) = {c}.
A f: A ? B B
S
f(S)
M. Hauskrecht
Injective function
Definition: A function f is said to be one-to-one, or injective, if
and only if f(x) = f(y) implies x = y for all x, y in the domain of
f. A function is said to be an injection if it is one-to-one.
Alternate: A function is one-to-one if and only if f(x) ? f(y),
whenever x ? y. This is the contrapositive of the definition.
A f: A ? B B A f: A ? B B
Not injective Injective function
13
M. Hauskrecht
Injective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
• Define f as
– 1 ? c
– 2 ? a
– 3 ? c
• Is f one to one? No, it is not one-to-one since f(1) = f(3) = c, and
1 ? 3.
Example 2: Let g : Z ? Z, where g(x) = 2x - 1.
• Is g is one-to-one (why?)
• Yes.
• Suppose g(a) = g(b), i.e., 2a - 1 = 2b - 1 => 2a = 2b
`` => a = b.
M. Hauskrecht
Surjective function
Definition: A function f from A to B is called onto, or surjective,
if and only if for every b ? B there is an element a ? A such that
f(a) = b.
Alternative: all co-domain elements are covered
A f: A ?B B
14
M. Hauskrecht
Surjective functions
Example 1: Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? c
• Is f an onto?
• No. f is not onto, since b ? B has no pre-image.
Example 2: A = {0,1,2,3,4,5,6,7,8,9}, B = {0,1,2}
– Define h: A ? B as h(x) = x mod 3.
• Is h an onto function?
• Yes. h is onto since a pre-image of 0 is 6, a pre-image of 1 is 4, a
pre-image of 2 is 8.
M. Hauskrecht
Bijective functions
Definition: A function f is called a bijection if it is both one-toone
and onto.
A f: A ?B B
15
M. Hauskrecht
Bijective functions
Example 1:
• Let A = {1,2,3} and B = {a,b,c}
– Define f as
• 1 ? c
• 2 ? a
• 3 ? b
• Is f is a bijection? Yes. It is both one-to-one and onto.
• Note: Let f be a function from a set A to itself, where A is finite.
f is one-to-one if and only if f is onto.
• This is not true for A an infinite set. Define f : Z ? Z, where
f(z) = 2 * z. f is one-to-one but not onto (3 has no pre-image).
M. Hauskrecht
Bijective functions
Example 2:
• Define g : W ? W (whole numbers), where
g(n) = [n/2] (floor function).
• 0 ? [0/2] = [0] = 0
• 1 ? [1/2] = [1/2] = 0
• 2 ? [2/2] = [1] = 1
• 3 ? [3/2] = [3/2] = 1
• ...
• Is g a bijection?
– No. g is onto but not 1-1 (g(0) = g(1) = 0 however 0 ? 1.