Chapter 2

Modified: 
© Ray Wisman
Resources
http://highered.mcgrawhill.com/sites/0072880082/student_view0/index.html  Rosen text Web site learning resources, requires registration.
http://highered.mcgrawhill.com/classware/selfstudy.do?isbn=0072880082  Extra examples with solutions, selfassessments, interactive problems and other supplementary material.
http://www.research.att.com/~njas/sequences  Type in a few sequence terms and finds the closed form, if one exists. Try: 1, 2, 6, 24
http://rechneronline.de/functiongraphs/  Function graphing
2.1 Sets
Introduction
Application
Set theory is the foundation of relational databases; critical to informatics and computer science.
Can collect things into a set, "is tall" is the collection of things that are tall.
Definition 1
Set is an unordered collection of objects.
Definition 2
Elements are the objects in a set.
∅ or {} is the empty set, that has no elements.
∅ ≠ {∅} The empty set is not equal to the set containing the empty set.
Just as an empty folder is not the same as a folder containing an empty folder.
Example
Set of all objects in the recycle can: recycle = { Coke can, newspaper, bottle }
Set of all $1000 bills in my wallet: ∅ or {}
Set of all objects in this room: room = { Liz, desk, computer, Andre, chair }
Set of all colors needed in a computer display: RGB = {red, green, blue}
Set of all natural numbers: N = {0, 1, 2, ...}
Set of all integers: Z = {..., 2, 1, 0, 1, 2, ...}
Set of positive integers: Z^{+} = {1, 2, ...}
Set of all even integers: E = { x ∈Z  x is even }
{N, Z^{+}, E, RGB, Obama} a set of five elements, four elements are sets, one is our president.
{ {1, 2, 3}, {desk, chair}, computer} another set.
Question 0 List as a set:
 the names of your two best friends and a favorite flavor of ice cream
 the four states bordering Indiana
Definition
Set builder notation characterizes elements of a set by stating membership properties.
Example
B = { Georgia, Utah, Ohio, Florida, Nevada }
A = { Utah, Nevada }
A = { x ∈ B  x is West of New Albany } x is an element of B such that x is West of New Albany
Example
B = { 0, 1, 2, 3, 4, 5 }
A = { 1, 3, 5 }
A = { x ∈ B  x is odd }
Example
A = { x  x is an odd positive integer and less than 10 }
A = { x ∈ Z^{+}  x is odd ^ x < 10 }
Definition 3
Equal sets if and only if (iff) have same elements.
Sets A = B iff: ∀x ( x ∈ A ↔ x ∈ B )
Example
A = {1, 2, 3}
B = {3, 1, 2}
A = B is true
Example
A = {1, 2, 3}
B = {1, 1, 2, 2, 3}
A = B is true because same elements
Question 1 True or False
 {1,1,3,3,3,5,5,5} = {5, 3, 1}?
 {{1}} = {1}?
B = { a, b, c, d, e }
A = { x ∈ B  x is vowel }
A = { a, e }?
Venn diagrams
Venn diagram for set of vowels in the English alphabet:
V = {a, e, i, o, u}
U = {a, b, c, ..., z}
Definition 4
Subset iff every element of one set is an element of another.
A ⊆ B iff: ∀x ( x ∈ A → x ∈ B )
Example
A = {1, 2 }
B = {1, 2, 3, 4}
A ⊆ B
Question 2  Which are subsets? True or False
 { 1, 3, 5, 5 } ⊆ { 1, 3 }?
 { 1,1,3,3,3} ⊆ { 5, 3, 1}?
 { { 1 } } ⊆ { { 1 }, { 2 } }?
 { 1 } ⊆ {{ 1 }}?
 ∅ ⊆ { 1 }?
 {} ⊆ { 1 }?
Definition 4
Subset iff every element of one set is an element of another.
A ⊆ B iff: ∀x ( x ∈ A → x ∈ B )
Theorem 1
For every set S: ∅ ⊆ S and S ⊆ S
Proof of ∅ ⊆ S
By definition of subset, must show
p → q is true
∀x ( x ∈ ∅ → x ∈ S ) is true
p is x ∈ ∅
q is x ∈ S
Hypothesis, p is x ∈ ∅
 Assume S is a set.
 By definition, ∅ contains no elements:
x ∉ ∅
x ∈ ∅ is false.
p is x ∈ ∅, is false.
false → q is true
 Showing p is false in p → q is called a vacuous proof.
∀x ( false → x ∈ S ) is true
p q p → q F F T F T T T F F T T T p → q is true when q is true. Called a trival proof.
If we all win the lottery then 2^{3} = 8.
p is "we all win the lottery" which is true or false.
q is "2^{3} = 8" which is known to be true.
p q p → q F F T F T T T F F T T T Definition
Proper subset iff every element of set A is an element of set B, A ⊆ B,
and at least one in B is not in A, A ≠ B.
A ⊂ B iff: ∀x ( x ∈ A → x ∈ B ) ^ ∃x ( x ∈ B ^ x ∉ A)
Example
A = {1, 2, 3}
B = {1, 2, 3, 4}
A ⊆ B is true
A ⊂ B is true
Example
A = {1, 2, 3, 4}
B = {1, 2, 3, 4}
A ⊆ B is true
A ⊂ B is false
Question 3  Which are proper subsets? True or False
 { 1, 3, 5, 5 } ⊂ { 1, 3, 5 }?
 { 1,1,3,3,3 } ⊂ { 5, 3, 1 }?
 { { 1 } } ⊂ { { 1 }, { 2 } }?
 { 1 } ⊂ {{1}, 1}?
 ∅ ⊂ { 1 }?
 {} ⊂ { 1 }?
Definition 5
Cardinality is number of distinct elements in a finite set S,
denoted by  S 
Examples
A = {1, 2, 3}
 A  = 3
B = {banana, banana, banana}
 B  = 1
 ∅  = 0
Question 4  Cardinality?
  { 1, 3, 5 } 
  { 1, 1, 3, 3, 3} 
  { { 1 }, 1} 
  { } 
Definition 6
Infinite set is not finite Example
Z, Z^{+}, N are infinite
A = {1, 2, 3} is finite
Power Set
Definition 7
Power set of S is the set of all subsets, denoted by P( S )
The power set of A has 2^{A} elements.
Example
A = {1, 2, 3}
 A  = 3
P( A ) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }
 P( A )  = 2^{A} = 2^{3 }= 8
Question 5
 P({R, G, B})? i.e. Power set of { R, G, B }
  P({R, G, B}) ?
Cartesian Products
Definition 8
Ordered ntuple (a_{1}, a_{2},..., a_{n}) is ordered collection having a_{1 }as first element, a_{2 }as second element, etc.
Example
A = (1, 2, 3)
B = (2, 3, 1)
A ≠ B though same elements, different order
Note that A and B are 3tuples, not sets.
Example
A = (U, R, A, nut)
B = (U, R, A, nut)
A = B same elements, same order
Question 5  Which tuples are equal? True or False
 (R, 1, Frank) = (R, 1, Frank)?
 (1,1,3,3,3,5,5,5) = (5, 3, 1)?
 (1, 3, 5) = (5, 3, 1)?
 ( ( 1 ), 3 ) = (1, 3)?
Definition 9
Cartesian product of sets A x B A x B = { ( a, b )  a ∈ A ^ b ∈ B}
Example
A = {1, 2}
B = {Red, Green, Blue}
A x B = { (1, Red), (2, Red), (1, Green), (2, Green), (1, Blue), (2, Blue) }
B x A = { (Red, 1), (Red, 2), (Green, 1), (Green, 2), (Blue, 1), (Blue, 2) }
Question 6  {a, b, c} x {R, G}?
Definition 10
Cartesian product of sets A_{1}, A_{2}, ..., A_{n} A_{1} x A_{2} x ... x A_{n} = { (a_{1}, a_{2}, ..., a_{n})  a_{i} ∈ A_{i} for i = 1, 2, ..., n}
Example
A = {1, 2}
B = {Red, Green}
C = {Mac, PC}
A x B x C = {
(1, Red, Mac), (1, Red, PC),
(1, Green, Mac), (1, Green, PC),
(2, Red, Mac), (2, Red, PC),
(2, Green, Mac), (2, Green, PC)}
Using Set Notation with Quantifiers
∀x ∈ S ( P(x) ) shorthand for ∀x ( x ∈ S → P(x) )
∃x ∈ S ( P(x) ) shorthand for
∃x ( x ∈ S ^ P(x) )
Example
∀x ∈ {a, e, i, o, u} (P(x))
states that for all x ∈ {a, e, i, o, u}, P( x ) is true.
∀x ∈ Z (x  x = 0)
states that for all x ∈ Z, x  x = 0.
∃x ∈ {a, e, i, o, u} (P(x))
states there exists a x ∈ {a, e, i, o, u} such that P( x ) is true.
∃x ∈ Z (x^{2} = 0)
states that there exists a x ∈ Z such that x^{2} = 0.
Question 7 Using set notation with quantifiers:
 State that there exists x ∈ Z such that x^{2} > 12
 State that for all x ∈ Z, x ≤ x^{2}
Truth Sets of Quantifiers
Definition
Truth set of predicate P is the set of elements x in D such that P(x) is true.
{ x ∈ D  P(x) }
Example
D = { Georgia, Utah, Ohio, Florida, Nevada }
P(x) is ( x is West of New Albany )
Truth set
{ x ∈ D  P(x) } is { Utah, Nevada }
Example
D = { 1, 0, 1, 2 }
P(x) is ( x^{2} < 2 )
Truth set
{ x ∈ {1, 0, 1, 2}  x^{2} < 2 } is { 1, 0, 1 }
{ x ∈ D  P(x) } is { 1, 0, 1 }
Example Z is the set of all integers
{ ∀x ∈ Z  x  x = 0 } the truth set is Z
{ ∃x ∈ Z  x  x = 0 } the truth set is nonempty
{ ∃x ∈ Z  x^{2} = 0 } the truth set is { 0 }
Question 8 State the truth set for: { x ∈ B  P(x) }
B = { New Albany, Beijing, London, New York, Shanghai, Lhasa }
P(x) is ( x is in China )
2.2 Set Operations
Introduction
Definition 1
Union of sets A and B contains elements in A, B or both
A ∪ B = { x  x ∈ A v x ∈ B}
Example
{1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}
{1, 2, 3} ∪ {1, 2, 3} = {1, 2, 3}
Definition 2
Intersection of sets A and B contains those elements in both A and B
A ∩ B = { x  x ∈ A ^ x ∈ B}
Example
{1, 2, 3} ∩ {3, 4} = { 3 }
{1, 2, 3} ∩ {4} = ∅
{1, 2, 3} ∩ {1, 2, 3} = {1, 2, 3}
Definition 3
Disjoint when intersection is empty.
A ∩ B = ∅
Example
{1, 2 } ∩ {3, 4} = ∅
Question 9 Give the resulting sets.
 {1, 2, 3} ∩ { 1, 2 }
 {1, 2, 3} ∩ { R, G, B }
 {1, 2, 3} ∩ ∅
 {1, 2, 3} ∪ { 1, 4 }
 {1, 2, 3} ∪ {R, G, B }
 {1, 2, 3} ∪ ∅
 {1, 2, 3} ∪ {}
Definition
Cardinality of union. A ∪ B = A + B  A ∩ B
A + B counts common elements twice.
A ∩ B is number of common elements.
Example
A = {1, 2, 3}
B = {3, 4}
{1, 2, 3} ∪ {3, 4} = {1, 2, 3, 4}
{1, 2, 3} ∪ {3, 4} = {1, 2, 3} + {3, 4}  {1, 2, 3} ∩ {3, 4}
= 3 + 2   {3} 
= 5  1
= 4
Definition 4
Difference, A  B is set containing elements in A but not in B.
A  B = { x  x ∈ A ^ x ∉ B}
Example
{1, 2 }  {3, 4} = {1, 2}
{1, 2, 3 }  {3, 4} = {1, 2}
{1, 2, 3}  {1, 2, 3} = ∅
Question 10
  {1, 2, 3} ∪ { 2, 3, 4 } 
 {1, 2, 3}  { 1, 2 }
 {1, 2, 3}  { 1, 2, 3 }
 {1, 2, 3}  ∅
Definition 5
Complement, U  A or A is with respect to the universal set, U.
A = { x  x ∈ U ^ x ∉ A}
A = { x  x ∉ A}
Example
U = { 1, 2, 3, 4, 5, 6 }
A = { 1, 2, 3, 4 }
A = { 5, 6}
Question 11
U = {a, e, i, o, u }
A = {a, e, o }
A = ?
Set Identities
Prove  De Morgan's 1st law:
A U B ≡ A ∩ B
In a membership table, think of:
∩ is as ^ conjunction
∪ is as v disjunction
A B A ∪ B A U B A B A ∩ B 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 1
Prove
A U (B ∩ C) = A ∩ (B ∪ C)
A U (B ∩ C) = A ∩ (B ∩ C) first De Morgan's law, A U B ≡ A ∩ B = A ∩(B ∪ C) second De Morgan's law, (B ∩ C) ≡ B ∪ C
Prove
A U B = A ∩ B
A U B = { x  x ∉ A ∪ B} definition of complement = { x  ¬(x ∈ A ∪ B)} definition of not an element symbol = { x  ¬(x ∈ A v x ∈ B)} definition of union = { x  ¬(x ∈ A) ^ ¬(x ∈ B)} De Morgan's law for logical equivalences, ¬(p v q) ≡ ¬p ^ ¬q = { x  (x ∉ A) ^ ( x∉ B)} definition of not an element symbol = { x  (x ∈ A) ^ (x ∈ B)} definition of complement = { x  (x ∈ A ∩ B} definition of intersection = A ∩ B
Prove by Membership Table
A ∩ (B ∪ C) = (A ∩ B) ∪(A ∩ C)
Question 12
U = { 0, 1, 2, 3 }
A = { 0, 2 }
B = { 0, 1 }
 A ∩ B =
 A ∪ B =
 Use a membership table to prove: A ∩ B = A ∪ B
Set Identities
Generalized Unions and Intersections
Definition 6
Union of a collection of sets contains elements that are members of at least one set in the collection.
Definition 7
Intersection of a collection of sets contains elements that are members of all sets in the collection.
Example
A = {0, 2, 4, 6, 8}
B = {0, 1, 2, 3, 4}
C = {0, 1, 3, 5, 7}
A ∩ B ∩ C = { 0 }
A ∪B ∪ C = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }
Question 12.1
A = {R, 2, D}
B = {R, G, B}
C = {2, 2}
 A ∩ B ∩ C =
 A ∪ B ∪ C =
Computer Representation of Sets
Example  Bit strings arranged so that rightmost bit position, position 0, is least significant.
4bits to represent universe of 4 elements.
3 2 1 0 1 0 1 1
Example using bit strings to represent sets.
U = { 5, 4, 3, 2, 1, 0 }
A = { 2, 1, 0 }
B = { 3, 2 }
Could represent universe as 6bit strings by:
U = { 5, 4, 3, 2, 1, 0 } = 111111
A = { 2, 1, 0 } = 000111
B = { 3, 2 } = 001100
A ∪ B = A v B
{ 2, 1, 0 } ∪ { 3, 2 } = {3, 2, 1, 0}
000111 { 2, 1, 0 }
v 001100 ∪ { 3, 2 }
001111 {3, 2, 1, 0}A ∩ B = A ^ B
{ 2, 1, 0 } ∩ { 3, 2 } = { 2 }
000111 { 2, 1, 0 }
^ 001100 ∩ { 3, 2 }
000100 { 2 }
Question 12.5 Represent the sets as 5bit strings. Hint: let u be the rightmost bit.
U = { a, e, i, o, u } = 11111
4 3 2 1 0 a e i o u
 { a, i, o } =
 { e, o } =
 { a, i, o }
∪ { e, o }
 { a, i, o }
∩ { e, o }
Example using Boolean arrays
U = { 0, 1, 2, 3, 4 }
A = { 0, 1, 2 }
B = { 2, 3 }
Could represent in Java by arrays:
0 1 2 3 4
Boolean U[] = { true, true, true, true, true };
Boolean A[] = { true, true, true, false, false };
Boolean B[] = { false, false, true, true, false };
Boolean C[] = { true, true, true, true, false };
C = A ∪ B
Boolean [ ] union( Boolean [ ] A, Boolean [ ] B ) { Boolean C[ ] = A;
for( int i = 0; i < C.length; i++)
if( B[i] )
C[i] = true;
return C;
}
Introduction
Definition 1
Function f from A to B is assignment of exactly one element of B to each element of A.
f(a) = b where b is the unique element of B assigned by f to the element a of A.
f : A → B
Functions also called mappings or transformations.
Definition 2
Domain of f : A → B is A Codomain of f : A → B is B
Image f(a) = b is b
Preimage f(a) = b is a
Range of f : A → B is set of all images of elements of A
Examples  Note that the range is only those elements of A that have an image in B, the range is not all of B in this case.
G :
A → B
A = { Adams, Chou, Goodfriend, Rodriguez, Stevens } B = { A, B, C, D, F } G( Chou ) = C
Range of G is {A, B, C, F} 
Definition 2
Domain of f : A → B is A Codomain of f : A → B is B
Image f( a ) = b is b
Preimage f( a ) = b is a
Range of f : A → B is set of all images of elements of A
A B
Question 13
f : A → B
A = { Yugo, Honda, Ford, Chevy }
B = { Red, Blue, Green, Yellow }
 Domain of f : A → B
 Codomain of f : A → B
 Image f( Yugo )
 Preimage f( Yugo )
 Range of f : A → B
Example
Domain and codomain of functions defined in programming languages.
int truncate( real x ) { ... } Z truncate( R x ) { ... }
truncate : R → Z
Domain is R
Codomain is Z
Definition 3
f_{1} : A → R f_{2} : A → R
(f_{1} + f_{2})(x) = f_{1}(x) + f_{2}(x)
(f_{1}• f_{2})(x) = f_{1}(x) • f_{2}(x)
Example
f_{1} : R → R
f_{2} : R → R
f_{1}(x) = x^{2}
f_{2}(x) = 1/x^{2}
(f_{1} + f_{2})(x) = f_{1}(x) + f_{2}(x) = x^{2} + 1/x^{2 }
(f_{1}f_{2})(x) = f_{1}(x) • f_{2}(x) = x^{2} • (1/x^{2}) = x^{2} / x^{2 }= 1
Definition 4
f : A → B S ⊆ A
Image of S under f is a subset of B.
f( S ) ⊆ B
f( S ) = { x  ∃s ∈ S ( x = f( s ) ) }
Example
M = { Adams, Chou, Goodfriend, Rodriguez, Stevens } B = { A, B, C, D, F } G : M → B

OnetoOne and Onto Functions
Definition 5
Onetoone or injective function ∀a∀b ( f(a) = f(b) → a = b )
Onetoone or injective function
∀a∀b ( a ≠ b → f(a) ≠ f(b) )
Example
A = { a, b, c, d } B = { 1, 2, 3, 4, 5 } G : A → B
OnetoOne 
Question 14.1
Does below student grade diagram illustrate a onetoone mapping?
A = { Adams, Chou, Goodfriend, Rodriguez, Stevens } B = { A, B, C, D, F } G : A → B G(Adams) = G(Rodriguez) but Adams ≠ Rodriguez


A
B

Proof
Is f(x) = x + 1 from the set of real numbers to the real numbers onetoone?
f : R → R
∀x∀y ( f(x) = f(y) → x = y ) Definition of onetoone
∀x∀y ( x+1 = y+1 → x = y ) Hypothesis
Show:
p → qx + 1 = y + 1 → x = y ∀x∀y( f(x) = f(y) → x = y )
x + 1 = y + 1 Hypothesis assumed True, if p x + 1  1= y + 1  1 Subtract 1 from both sides x = y then q ∴x + 1 = y + 1 → x = y p → q Definition 5
Onetoone or injective function ∀a∀b ( f(a) = f(b) → a = b )
iff f(a) = f(b) implies a = b for all a and b in domain.
Onetoone or injective function
∀a∀b ( a ≠ b → f(a) ≠ f(b) )
iff f(a) ≠ f(b) whenever a ≠ b.
Definition 6
Increasing f(x) ≤ f(y) for real x < y
∀x∀y( x < y → f(x) ≤ f(y) )
Example
f(x) = 1
f(1) = 1 1 < 2
f(2) = 1 f(1) ≤ f(2)
Strictly increasing f(x) < f(y) for real x < y.
∀x∀y( x < y → f(x) < f(y) )
Strictly increasing functions must be onetoone.
Examples
f(x) = x
f(x) = x^{2} is not onetoone and is not strictly increasing
2^{2} = 4 = 2^{2}
3^{2} = 9 = 3^{2}
3 < 2 but f(3) > f(2)
Decreasing f(x) ≥ f(y) for real x < y. ∀x∀y( x < y → f(x) ≥ f(y) )
Example
f(x) = 1
f(1) = 1 1 < 2
f(2) = 1 f(1) ≥ f(2)
Strictly decreasing f(x) > f(y) for real x < y. ∀x∀y( x < y → f(x) > f(y) )
Strictly decreasing functions must be onetoone.
Example
f(x) = x
f(3) = 3 2 < 3
f(2) = 2 f(2) > f(3)
2 > 3
Definition 7
Onto or surjective function iff every b ∈ B has a ∈ A with f(a) = b.
∀y∃x ( f(x) = y )
Example below
Onto? True, ∀y∃x ( f(x) = y )
Onetoone? False, ∀a∀b ( f(a) = f(b) → a = b )
f(a) = f(d) = 3, a ≠ d.
Examples
Question 17.1
 Is (e) above a function?
 Which of the above are onetoone?
 Which of the above are onto?
Question 17.2
 Diagram the following functions:
f : {a, b, c, d} → {1, 2, 3, 4}
f(a)=1
f(b)=2
f(c)=3
f(d)=4
g : {a, b, c, d} → {1, 2, 3, 4}
g(a)=1
g(b)=1
g(c)=4
g(d)=4
 Which functions are onto?
 Which functions are onetoone?
Example
Is f(x) = x^{2} from integers to integers onto? f : Z → Z
No, because does not map to negative integers.
f : Z → Z^{+}
No. For example: f(1)=1, f(2)=4, no Z value maps to 2 or 3 in Z^{+}.
Example
Is f(x) = x + 1 from integers to integers onto? f : Z → Z
Yes, because for each y there is x such that f(x) = y.
Show: f(y  1) = y ∀y∃x( f(x) = y )
f(x) = y iff y = x + 1 Function definition f(x) = x + 1 y = x + 1 iff x = y  1 Subtract 1 from both sides x = y  1 iff f(y  1) = y Substitute y1 for x in f(x) = x + 1 f(y  1) = y  1 + 1 = y Then x = y  1 for each y
Definition 8
Onetoone correspondence or bijection function if onetoone and onto.
Examples
Question 18
 Which of the above are onetoone?
 Which of the above are onto?
 Which of the above are onetoone and onto?
Inverse Functions and Compositions of Functions
Definition 9
Inverse of onetoone function f from A to B such that f^{1}(b) = a when f(a) = b.
Note that f^{1} is not a function when f is not onto.
Invertible
when onetoone correspondence (i.e. onetoone and onto)
Example
f : R^{+}→R^{+}
f(x) = x^{2}
f^{1}(x) = x^{1/2}
f( 3 ) = 3^{2 }= 9
f^{1}(9) = 9^{1/2 }= 3
Question 19.1  From diagram below:
 In (a), what is f( c )?
 In (a), what is f^{1}( 1 )?
 In (c), what is f and f^{1} for all values?
f(a) =
f(b) =
f(c) =
f(d) =f^{1}(1) =
f^{1}(2) =
f^{1}(3) =
f^{1}(4) = Which of the following diagrams (a)  (e) have an inverse, f^{1}?
 Which of the following are invertible?
Definition 9
Inverse of onetoone function f from A to B such that f^{1}(b) = a when f(a) = b.
Note that f^{1} is not a function when f is not onto.
Invertible
when onetoone correspondence (i.e. onetoone and onto)
Example
f: Z → Z such that f( x ) = x + 1
What is f(3)? 3 + 1 = 4
Is f( x ) onetoone? Yes.
Is f( x ) onto? Yes.
Is f( x ) invertible? Yes.
What is the inverse? f^{1}(b) = a when f(a) = b
f( a ) = a + 3 = b
f( 6 ) = 6 + 3 = 9
f^{1}( b ) = b  3 = a
f^{1}( 9 ) = 9  3 = 6
Publicprivate key encryption/decryption algorithms use inverse functions, public key encrypts message encrypted, private key decrypts.
Encrypt 'A' f( 'A' ) = 'A' + 3 = 'D'
Decrypt 'D' f^{1}( 'D' ) = 'D'  3 = 'A'
In practice (e.g. RSA algorithm) use invertible functions based on large (1024 bit) prime numbers.
Question 19.2 Encrypt and decrypt one of your initials using:
f( a ) = a + 3 = b
f^{1}( b ) = b  3
Definition 10
Composition of function g from A to B and
function f from B to C.
(f ○ g) (a) = f( g( a ) )
Base 2 8 10 16 Glyph
100 0001 101 65 41 A
100 0010 102 66 42 B
100 0011 103 67 43 C
100 0100 104 68 44 D
100 0101 105 69 45 E
100 0110 106 70 46 F
100 0111 107 71 47 G
100 1000 110 72 48 H
100 1001 111 73 49 I
100 1010 112 74 4A J
100 1011 113 75 4B K
100 1100 114 76 4C L
100 1101 115 77 4D M
100 1110 116 78 4E N
100 1111 117 79 4F O
101 0000 120 80 50 P
101 0001 121 81 51 Q
101 0010 122 82 52 R
101 0011 123 83 53 S
101 0100 124 84 54 T
101 0101 125 85 55 U
101 0110 126 86 56 V
101 0111 127 87 57 W
101 1000 130 88 58 X
101 1001 131 89 59 Y
101 1010 132 90 5A Z
101 1011 133 91 5B [
101 1100 134 92 5C \
101 1101 135 93 5D ]Example
g: {a, b, c} → {X, Y, Z} g( a ) = X
g( b ) = Y
g( c ) = Z
f: {X, Y, Z} → {1, 2, 3} f( X ) = 1
f( Y ) = 2
f( Z ) = 3
(f ○ g) (a) = f( g( a ) ) = f( X ) = 1 (f ○ g) (b) = f( g( b ) ) = f( Y ) = 2
(f ○ g) (c) = f( g( c ) ) = f( Z ) = 3
g ○ f is not defined because f range, {1, 2, 3}, is not a subset of g domain, {a, b, c}
(g ○ f)(X) = g( f( X ) ) = g( 1 ) is not defined.
Example functions from R to R
f(x) = 5x + 7
g(x) = 3x + 2
(f ○ g) (x) = f( g(x) ) = f(3x+2) = 5(3x+2) + 7 = 15x + 17
(g ○ f) (x) = g( f(x) ) = g(5x+7) = 3(5x+7) + 2 = 15x + 23
(f ○ g) (x) ≠ (g ○ f) (x)
Question 20  Find f ○ g where
g: {R, G, B} → {red, green, blue} g( R ) = red
g( G ) = green
g( B ) = blue
f: {red, green, blue} → {Ford, Chevy} f( red ) = Ford
f( green ) = Chevy
f( blue ) = Ford
a. (f ○ g) (R) = f( g (R) ) = f( red ) = ?
b. (f ○ g) (G) = ?
c. (f ○ g) (B) = ?
Question 21  For above, does the (g ○ f) composition exist?
(g ○ f)( blue ) = g( f ( blue ) )?
Definition
Identity function obtained from composition of function and its inverse.
(f^{1 }○ f) (a) = f^{1}( f( a ) ) = f^{1}( b ) = a
(f ○ f^{1}) (b) = f( f^{1}( b ) ) = f( a ) = b
(f^{1})^{1} = f
Example
f( a ) = a + 3 = b
f( 6 ) = 6 + 3 = 9
f^{1}( b ) = b  3
f^{1}( 9 ) = 9  3 = 6
(f^{1 }○ f) (6) = f^{1}( f( 6 ) ) = f^{1}(6 + 3) = f^{1}( 9 ) = 9  3 = 6
(f^{ }○ f^{1}) (6) = f( f^{1}( 6 ) ) = f(6  3) = f( 3 ) = 3 + 3 = 6
The Graphs of Functions
Function grapher  http://rechneronline.de/functiongraphs/
Definition 11
Graph of f: A → B is set of ordered pairs { (a, b)  a ∈ A and f(a) = b}
Example
f(n) = 2n + 1
A = { 1, 0, 1, 2 }
B = { 1, 1, 3, 5 }
Ordered pairs:
(n, 2n + 1)
{ (1, 1), (0, 1), (1, 3), (2, 5) }
Example
f(x) = x^{2}
Ordered pairs:
(x, x^{2})
{(3, 9), (2, 4), (1, 1), (0,0), (1,1), (2,4), (3,9)}
Question 22.1
f( x ) = 2x+1
for x ∈ {2, 1, 0, 1, 2}
 What are the ordered pair values for (x, 2x+1)?
 Draw the corresponding graph.
Some Important Functions
Definition 12
Floor function assigns to real number x the largest integer less than or equal to x.
⌊ x ⌋
Ceiling function
assigns to real number x the smallest integer greater than or equal to x.
⌈ x ⌉
Examples
⌊ 1/2 ⌋ = 0
⌈ 1/2 ⌉ = 1
⌊ 1/2 ⌋ = 1
⌈ 1/2 ⌉ = 0
⌈ 1 ⌉ = ⌊ 1 ⌋ = 1
Example
Prove or disprove ⌈x + y⌉ = ⌈x⌉ + ⌈y⌉
Counterexample:
⌈1/2 + 1/2⌉ = 1
⌈1/2⌉ + ⌈1/2⌉ = 1 + 1 = 2
Question 22.2  What are the values of:
 ⌊ 5/2 ⌋ =
 ⌊ 5/2 ⌋ =
 ⌈ 5/2 ⌉ =
 ⌈ 5/2 ⌉ =
 ⌈ 5 ⌉ =
 ⌊ 5 ⌋ =
Definition 12
Floor function assigns to real number x the largest integer less than or equal to x.
⌊ x ⌋
Ceiling function
assigns to real number x the smallest integer greater than or equal to x.
⌈ x ⌉
Sequences
Definition
Sequence is a discrete structure used to represent an ordered list.
Example
1, 3, 5, 7, 11 is ordered sequence of 5 terms
1, 3, 5, 7, 11, ... is an infinite sequence
Definition 1
Sequence is a function from a subset of the set of integers, usually {0, 1, 2, ...} or {1, 2, 3, ...}, to a set S.
a_{n}, a sequence term, denotes the image of the integer n.
f(n) = a_{n}
{a_{n}} describes the sequence.
Example
Sequence {a_{n}}
a_{n }= 1/n
List of terms starts at n=1
a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, ... 1/1, 1/2, 1/3, 1/4, 1/5, ... Question 23 In the above sequence, what is:
 a_{6} =
 a_{42} =
Definition 2
Geometric progression is the sequence
a, ar, ar^{2}, ar^{3}, ..., ar^{n}, ...
where initial term a and common ratio r are real numbers.
Examples
Sequence {c_{n}}
c_{n }= 2 • 10^{n}
a = 2
r = 10
c_{0}, c_{1}, c_{2}, c_{3}, c_{4}, ... 2 • 10^{0}, 2 • 10^{1}, 2 • 10^{2}, 2 • 10^{3}, 2 • 10^{4}, ... 2, 20, 200, 2000, 20000, ... Question 24
c_{n }= 2 • 10^{n}, what is:
 c_{6} =
 c_{42} =
Sequence {b_{n}}
b_{n }= 1 • (1)^{n}
a = 1
r = 1
b_{0}, b_{1}, b_{2}, b_{3}, b_{4}, ... (1)^{0}, (1)^{1}, (1)^{2}, (1)^{3}, (1)^{4}, ... 1, 1, 1, 1, 1, ... Question 25
b_{n }= 3 • (1)^{n}
the result is 3 or 3, give the result:
 b_{5} =
 b_{42} =
Sequence {d_{n}}
d_{n }= 6 • (1/3)^{n}
a = 6
r = 1/3
d_{0}, d_{1}, d_{2}, d_{3}, d_{4}, ... 6 • (1/3)^{0}, 6 • (1/3)^{1}, 6 • (1/3)^{2}, 6 • (1/3)^{3}, 6 • (1/3)^{4}, ... 6, 2, 2/3, 2/9, 2/27, ... Question 26
d_{n }= 6 • (1/3)^{n}
d_{4} = 6 • (1/3)^{4 }
What is:
 d_{6} =
 d_{42} =
Definition 3
Arithmetic progression is the sequence
a, a+d, a+2d, a+3d, a+4d, ..., a+nd, ...
where initial term a and common difference d are real numbers.
Examples
Sequence {s_{n}}
s_{n }= 1 + 4n
a = 1
d = 4
s_{0}, s_{1}, s_{2}, s_{3}, s_{4}, ...
1+4•0, 1+4•1, 1+4•2, 1+4•3, 1+4•4,...
1, 3, 7, 11, 15, ...
Sequence {t_{n}}
t_{n }= 7  3n
a = 7
d = 3
t_{0}, t_{1}, t_{2}, t_{3}, t_{4}, ...
7  3•0, 7  3•1, 7  3•2, 7  3•3, 7  3•4,...
7, 4, 1, 2, 5, ...
Question 27
t_{n }= 7  3n
t_{4 }= 7  3•4 = 5
What is:
 t_{5} =
 t_{42} =
Definition
String is the sequence a_{1}a_{2}...a_{n}
Examples
4bit Binary Sequence {b_{n}}
b_{1}, b_{2}, b_{3}, b_{4}
1011
Arbitrary Character Sequence {s_{n}}
s_{1}, s_{2}, s_{3}, ..., s_{n}
hello world
Special Integer Sequences
Often want to determine formula for constructing terms of a sequence.
Questions to ask:
 Does same value occur frequently in a row? Indicates a cycle.
 Are later terms obtained by some operation (e.g. addition, exponentiation, etc.) by the same amount or an amount dependent on the term position?
s_{n }= 1 + 4n
Examples
Find formula for sequence:
 1, 1/2, 1/4, 1/8, 1/16
1/2^{0}, 1/2^{1}, 1/2^{2}, 1/2^{3}, 1/2^{4}
geometric progression
a=1
r=1/2
a_{n }= (1/2)^{n}
 1, 3, 5, 7, 9
2•0+1, 2•1+1, 2•2+1, 2•3+1, 2•4+1
arithmetic progression
a=1
d=2
a_{n }= 2•n+1
 1, 1, 1, 1, 1
1^{0}, 1^{1}, 1^{2}, 1^{3}, 1^{4}
geometric progression
a=1
r=1
a_{n }= (1)^{n}
 1, 2, 2, 3, 3, 3, 4, 4, 4, 4
 5, 11, 17, 23, 29, 35
 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047
 Determine the difference between next term:
6, 18, 54, 162, 486, 1458
 Note whether a ratio. Here it is multiple of 3, or 3^{n}.
 Determine the first couple of terms by adjusting for some constant:
 1 = 3^{1} 2
 7 = 3^{2} 2
 25 = 3^{3} 2
 Generalize on n
3^{n } 2 for n=1, 2, 3, ...
RESOURCES
http://oeis.org  Type in a few sequence terms and finds the closed form, if one exists. Try: 1, 2, 6, 24
Summations
Definition
Summation notation expresses the sum of terms:
a_{m}, a_{m+1}, a_{m+2}, ..., a_{n}
represents: a_{m} + a_{m+1} + a_{m+2} + ... + a_{n}
m is lower limit
n is upper limit
Example
Example
1 + 1 + ... + 1 = 100
Question 28  What are the following values?
Usual arithmetic rules apply to summations
a and b are constants
Example
4(1+2+3) + 2(1+4+9) = 24 + 28 = 52
Set notation can be used to define specific values.
Question 29  What is the following value?
Theorem 1
Geometric series can be represented in closed form
If a and r are real numbers and r ≠ 0, then
Proof when r ≠1
Proof when r = 1
Nested summations
Example
int sum = 0; for(int i=1; i<=4; i++)
for(int j=1; j<=3; j++)
sum = sum + i * j;
i j sum 1 1 1 1 2 3 1 3 6 2 1 8 2 2 12 2 3 18 3 1 21 3 2 27 3 3 36 4 1 40 4 2 48 4 3 60 Question 30  What is the following value?
Question 31  What is the following value for n=100? Use Table 2.
Cardinality
Definition 4
Cardinality of A and B same iff onetoone correspondence from A to B.
Definition 5
Countable set that is either finite or has same cardinality of positive integers.
Infinite countable set
S cardinality denoted by: S = ℵ_{0}
Example
Show set of odd positive integers is countable.
Equivalent to showing has same cardinality as positive integers.
Requires showing onetoone correspondence with positive integers.
Consider the function
f(n) = 2n  1
from Z^{+} to the odd positive integers.
 Show f is onetoone and onto.
Onetoone
m, n ∈ Z^{+}
if f(n) = f(m) then 2n1 = 2m1 so n = m
Definition 5
Onetoone or injective function iff f(a) = f(b) implies a = b for all a and b in domain. ∀a∀b( f(a) = f(b)→a = b )
Onetoone or injective function iff f(a) ≠ f(b) whenever a ≠ b.
∀a∀b( a ≠ b → f(a) ≠ f(b) )
Definition 7
Onto or surjective function iff every b ∈ B has a ∈ A with f(a) = b. ∀y∃x(f(x) = y )
Onto
Suppose b is odd integer, b = 2a  1 .
Then b is one less than an even integer 2a where a ∈ Z^{+}
b = 2a  1 = f(a)
f(n) = 2n  1 is onetoone and onto with the positive integers, therefore is countable.
Example
Show that the set of real numbers is uncountable.
Assume real numbers are countable and demonstrate a contradiction.
Basic idea:
 List all the real numbers between 0 and 1, any subset of a countable set is countable.
 Suppose your list includes
 0.23
 0.24
 The contradiction is there exists a real number between, 0.23 < 0.235 < 0.24
 Further that, for any two real numbers there are an infinite real numbers in between.
 It is impossible to list the real numbers, therefore real numbers are not the same cardinality as the positive integers, so are not countable.
Example
Show that the set of positive rational numbers is countable.
Basic idea is that we can list each rational number uniquely by defining a sequence of rational numbers, r_{1}, r_{2}, r_{3}, ..., r_{n}, ... where each r_{i} corresponds to a positive integer.