Chapter 2
Basic Structures: Sets, Functions, Sequences, and Sums

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter2/self_assessments.html - Chapter self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter2/extra_examples.html - Extra examples with solutions.

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

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.

Example

The set of all objects in the recycle can:    recycle = { Coke can, newspaper, bottle } 

The set of all $1000 bills in my wallet: ∅ or {}

The set of all objects in this room:    room = { Oli, desk, computer, me, Josh } 

The set of all colors needed in a computer display: RGB = {red, green, blue}

The set of all natural numbers: N = {0, 1, 2, ...}

The set of all integers: Z = {..., -2, -1, 0, 1, 2, ...}

The set of positive integers: Z⁺ = {1, 2, ...}

The 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 the elements in the set of:

1. names of your two best friends and a favorite flavor of ice cream
    
2. 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 }

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,1,3,3,3,5,5,5} = {5, 3, 1}?
    
2. {{1}} = {1}?
    

3. 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. { 1, 3, 5, 5 } ⊆ { 1, 3 }?
    
2. { 1,1,3,3,3} ⊆ { 5, 3, 1}?
    
3. { { 1 } } ⊆ { { 1 }, { 2 } }?
    
4. { 1 } ⊆ {{ 1 }}?
    
5. ∅ ⊆ { 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 ∈ ∅

1. Assume S is a set.
    
2. By definition, ∅ contains no elements:

   x ∉ ∅
   x ∈ ∅ is false.
    

3. p is x ∈ ∅, is false.

   false → q is true
    

4. 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³ = 8.

p is "we all win the lottery" which is true or false.

q is "2³ = 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. { 1, 3, 5, 5 } ⊂ { 1, 3, 5 }?
    
2. { 1,1,3,3,3 } ⊂ { 5, 3, 1 }?
    
3. { { 1 } } ⊂ { { 1 }, { 2 } }?
    
4. { 1 } ⊂ {{1}, 1}?
    
5. ∅ ⊂ { 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. | { 1, 3, 5 } |
    
2. | { 1, 1, 3, 3, 3} |
    
3. | { { 1 }, 1} |
    
4. | { } |

 

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³ = 8

 

Question 5 - Power set of { R, G, B }?

 

Cartesian Products

Definition 8

Ordered n-tuple (a1, a2,..., an) is ordered collection having as a1 as first element, etc.

Example

A = (1, 2, 3)

B = (2, 3, 1)

A ≠ B though same elements, different order

Note that A and B are 3-tuples, 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

1. (R, 1, Frank) = (R, 1, Frank)?
    
2. (1,1,3,3,3,5,5,5) = (5, 3, 1)?
    
3. (1, 3, 5) = (5, 3, 1)?
    
4. ( ( 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 A1, A2, ..., An A1 x A2 x ... x An = { (a1, a2, ..., an) |  ai ∈ Ai 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² = 0) states that there exists a x ∈ Z such that x² = 0.

 

Question 7   Using set notation with quantifiers:

1. State that there exists x ∈ Z such that x² > 12
    
2. State that for all x ∈ Z,  x ≤ x²
    

 

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 = { 0, 1, 2 }

P(x) is ( x² < 2 )

Truth set

{ x ∈ {0, 1, 2} | x² < 2 } is { 0, 1 }

{ x ∈ D | P(x) } is { 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² = 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. {1, 2, 3} ∩ { 1, 2 }
    
2. {1, 2, 3} ∩ { R, G, B }
    
3. {1, 2, 3} ∩ ∅
    
4. {1, 2, 3} ∪ { 1, 4 }
    
5. {1, 2, 3} ∪ {R, G, B }
    
6. {1, 2, 3} ∪ ∅

 

Definition

Cardinality of union.  |A ∪ B| = |A| + |B| - |A ∩ B|

Elements in both sets are counted twice, intersection is elements in both sets.

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. | {1, 2, 3} ∪ { 2, 3, 4 } |
    
2. {1, 2, 3} - { 1, 2 }
    
3. {1, 2, 3} - { 1, 2, 3 }
    
4. {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 U B ≡ A ∩ B

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 by Direct Proof

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 by Direct Proof

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 - Use a membership table to prove:   A ∩ B = A ∪ B

 

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 }

 

Computer Representation of Sets

Example - Bit strings arranged so that right-most bit position, position 0, is least significant.

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 as bit 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 bit 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

1. { a, i, o } =
    
2. { e, o } =
    
3. { a, i, o } ∪ { e, o } =
    
4. { 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; }

2.3 Functions

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 Domain of G is A Codomain of G is B A = { Adams, Chou, Goodfriend, Rodriguez, Stevens } B = { A, B, C, D, F } G( Chou ) = C C is image of G( Chou ) Chou is preimage of 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

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

f1 : A → R f2 : A → R (f1 + f2)(x) = f1(x) + f2(x) (f1• f2)(x) = f1(x) • f2(x)

Example

f₁ : R → R

f₂ : R → R

f₁(x) = x²

f₂(x) = 1/x²

(f1 + f2)(x) = f1(x) + f2(x) = x2 + 1/x2

(f1f2)(x) = f1(x) • f2(x) = x2 • (1/x2) = x2 / x2 = 1

 

Definition 4

f : A → B S ⊆ A Image of S under f is a subset of B. f( S ) ⊆ B f( S ) = { t | ∃s ∈ S ( t = f( s ) ) }

Example

M = { Adams, Chou, Goodfriend,           Rodriguez, Stevens } B = { A, B, C, D, F } G : M → B S = { Adams, Rodriguez, Chou } S ⊆ M G(S) = { A, A, C } = { A, C } ⊆ B

 

One-to-One and Onto Functions

Definition 5

One-to-one 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  ) One-to-one or injective function iff    f(a) ≠ f(b)   whenever a ≠ b. ∀a∀b( a ≠ b → f(a) ≠ f(b) )

Example

A = { a, b, c, d } B = { 1, 2, 3, 4, 5 } G : A → B G(a) = 4 G(b) = 5 G(c) = 1 G(d) = 3 One-to-One

 

Question 14.1

Does below student grade diagram illustrate a one-to-one mapping?

A = { Adams, Chou, Goodfriend, Rodriguez, Stevens } B = { A, B, C, D, F } G : A → B G(Adams) = G(Rodriguez) but Adams ≠ Rodriguez

Question 14.2 The diagram at right is not a one-to-one mapping. Why not? f : A → B A = { Yugo, Honda, Ford, Chevy } B = { Red, Blue, Green, Yellow }

Question 15

Diagram the following two functions from {a,b,c,d} to {1,2,3,4}.

Which functions from {a, b, c, d} to {1, 2, 3, 4} are one-to-one?

1. f(a)=1, f(b)=2, f(c)=3, f(d)=4
    
2. f(a)=1, f(b)=1, f(c)=4, f(d)=4

 

Proof

Is f(x) = x + 1 from the set of real numbers to the real numbers one-to-one?

f : R → R

Show:
                          p → q

x + 1 = y + 1 → x = y                ∀x∀y( f(x) = f(y) → x = y  )

x + 1 = y + 1	Hypothesis, 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

One-to-one 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  ) One-to-one or injective function iff    f(a) ≠ f(b)   whenever a ≠ b. ∀a∀b( a ≠ b → f(a) ≠ f(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 one-to-one.

Examples

f(x) = x

f(x) = x² is not one-to-one and is not strictly increasing

2² = 4 = -2²

3² = 9 = -3²

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

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

It is an onto function?

Is it one-to-one?

Examples

Question 17.1

1. Is (e) above a function?
    
2. Which of the above are one-to-one?
    
3. Which of the above are onto?
    

Question 17.2

Diagram the below functions.

Which functions are onto?

Which functions are one-to-one?

1. f(a)=1, f(b)=2, f(c)=3, f(d)=4
    
2. f(a)=1, f(b)=1, f(c)=4, f(d)=4
    

Example

Is f(x) = x² from integers to integers onto?     f : Z → Z

No, because does not map to negative integers.

f : Z → 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 y-1 for x in f(x) = x + 1
f(y - 1) = y - 1 + 1 = y	Then x = y - 1 for each y

 

Definition 8

One-to-one correspondence or bijection function if one-to-one and onto.

Examples

Question 18

1. Which of the above are one-to-one?
    
2. Which of the above are onto?
    
3. Which of the above are one-to-one and onto?

 

Inverse Functions and Compositions of Functions

Definition 9

Inverse of one-to-one function f from A to B such that  f-1(b) = a when f(a) = b. Invertible when one-to-one correspondence (i.e. one-to-one and onto)

 

Example

f : R⁺→R⁺

f(x) = x²

f^-1(x) = x^1/2

f( 3 ) = 3² = 9

f^-1(9) = 9^1/2 = 3

 

Question 19.1

1. Which of the following diagrams (a)-(e) have an inverse?
    
2. Which of the following are invertible?
    
3. In (a), what is f( c )?
    
4. In (a), what is f^-1( 1 )?
    
5. 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) =

Definition 9

Inverse of one-to-one function f from A to B such that  f-1(b) = a when f(a) = b. Invertible when one-to-one correspondence (i.e. one-to-one and onto)

Example

f: Z → Z such that f( x ) = x + 1

What is f(3)?   3 + 1 = 4

Is f( x ) one-to-one? 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

f^-1( 9 ) = 9 - 3 = 6 = a

Public-private 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 two 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 ) )

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 range of f, {1, 2, 3}, is not a subset of the domain of g, {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 = a

(f^-1 ○ f) (6) = f^-1( f( 6 ) ) = f^-1(6 + 3) = f^-1( 9 ) = 9 - 3 = 6

  

The Graphs of Functions

Function grapher - http://rechneronline.de/function-graphs/

 

Definition 11

Graph of function f from set A to B is set of ordered pairs { (a,b) | a ∈ A and f(a) = b}

Example

f(n) = 2n + 1

Ordered pairs:

(n, 2n + 1)

{ (-1, -1), (0, 1), (1, 3), (2, 5) }

Example

f(x) = x²

Ordered pairs:

(x, x²)

{(-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}

1. What are the ordered pair values for (x, 2x+1)?
    
2. 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:

1. ⌊5/2⌋ =
    
2. ⌊-5/2⌋=
    
3. ⌈5/2⌉=
    
4. ⌈-5/2⌉=
    
5. ⌈5⌉=
    
6. ⌊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⌉

 

2.4 Sequences and Summations

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. an, a sequence term, denotes the image of the integer n. f(n) = an {an} describes the sequence.

Example

Sequence {a_n}

a_n = 1/n

List of terms starts at n=1

a1,	a2,	a3,	a4,	a5,	...
1/1,	1/2,	1/3,	1/4,	1/5,	...

Question 23      In the above sequence, what is:

1.  a₆ =
    
2.  a₄₂ =

 

Definition 2

Geometric progression is the sequence a, ar, ar2, ar3, ..., arn, ... where initial term a and common ratio r are real numbers.

Examples

Sequence {c_n}

c_n = 2 • 10ⁿ

a = 2

r = 10

c0,	c1,	c2,	c3,	c4,	...
2 • 100,	2 • 101,	2 • 102,	2 • 103,	2 • 104,	...
2,	20,	200,	2000,	20000,	...

Question 24      In the above sequence, what is:

1.  a₆ =
    
2.  a₄₂ =

 

Sequence {b_n}

b_n = 1 • (-1)ⁿ

a = 1

r = -1

b0,	b1,	b2,	b3,	b4,	...
(-1)0,	(-1)1,	(-1)2,	(-1)3,	(-1)4,	...
1,	-1,	1,	-1,	1,	...

Question 25      In the above sequence, the result is 1 or -1, give the result:

1.  b₅ =
    
2.  b₄₂ =

 

Sequence {d_n}

d_n = 6 • (1/3)ⁿ

a = 6

r = 1/3

d0,	d1,	d2,	d3,	d4,	...
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      In the above sequence, d₄ = 6 • (1/3)⁴

What is:

1.  d₆ =
    
2.  d₄₂ =

 

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₀, s₁, s₂, s₃, s₄, ...

-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₀, t₁, t₂, t₃, t₄, ...

7 - 3•0, 7 - 3•1, 7 - 3•2, 7 - 3•3, 7 - 3•4,...

7, 4, 1, -2, -5, ...

Question 27      In the above sequence, t₄ = 7 - 3•4 = -5

What is:

1.  t₅ =
    
2.  t₄₂ =

 

Definition

String is the sequence a1a2...an

Examples

4-bit Binary Sequence {b_n}

b₁, b₂, b₃, b₄

1011

Arbitrary Character Sequence {s_n}

s₁, s₂, s₃, ..., s_n

hello world

 

Special Integer Sequences

Often want to determine formula for constructing terms of 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, 1/2, 1/4, 1/8, 1/16

   1/2⁰, 1/2¹, 1/2², 1/2³, 1/2⁴

   geometric progression

   a=1

   r=1/2

   a_n = (1/2)ⁿ

2. 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

    

3. 1, -1, 1, -1, 1

   -1⁰, -1¹, -1², -1³, -1⁴

   geometric progression

   a=1

   r=-1

   a_n = (-1)ⁿ

4. 1, 2, 2, 3, 3, 3, 4, 4, 4, 4
    
5. 5, 11, 17, 23, 29, 35
    
6. 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ⁿ.
      
   • Determine the first couple of terms by adjusting for some constant:
     • 1 = 3¹- 2
     • 7 = 3²- 2
     • 25 = 3³- 2
        
   • Generalize on n

     3ⁿ - 2 for n=1, 2, 3, ...

RESOURCES

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

 

Summations

Definition

Summation notation expresses the sum of terms: am, am+1, am+2, ..., an

represents: am + am+1 + am+2 + ... + an m is lower limit n is upper limit

Example

Example

1 + 1 + ... + 1 = 100

 

Question 28 - What are the following values?

1. 
    
2. 

 

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 one-to-one 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 one-to-one correspondence with positive integers.

Consider the function

f(n) = 2n - 1

from Z⁺ to the odd positive integers.

• Show f is one-to-one and onto.

  One-to-one

  m, n ∈ Z⁺

  if f(n) = f(m) then 2n-1 = 2m-1 so n = m

Definition 5

One-to-one 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  ) One-to-one 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 one-to-one 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₁, r₂, r₃, ..., r_n, ... where each r_i corresponds to a positive integer.