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

Modified

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Rosen text Web site learning resources, requires registration.

http://highered.mcgraw-hill.com/classware/selfstudy.do?isbn=0072880082 - Extra examples with solutions, self-assessments, 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/function-graphs/ - 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:

1. the 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 }        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,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 }?

6. {} ⊆ { 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 23 = 8.

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

q is "23 = 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 }?

6. {} ⊂ { 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| = 23 = 8

Question 5

1. P({R, G, B})?            i.e. Power set of { R, G, B }

2. | P({R, G, B}) |?

Cartesian Products

Definition 8

 Ordered n-tuple (a1, a2,..., an) is ordered collection having a1 as first element, a2 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 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 (x2 = 0)

states that there exists a x ∈ Z such that x2 = 0.

Question 7   Using set notation with quantifiers:

1. State that there exists x ∈ Z such that x2 > 12

2. State that for all x ∈ Z,  x x2

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 ( x2 < 2 )

Truth set

{ x ∈ {-1, 0, 1, 2} | x2 < 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 | x2 = 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} ∪ ∅

7. {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. | {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 BAB

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 ∩ (BC)

 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 }

1. A ∩ B =

2. AB  =

3. Use a membership table to prove:   A ∩ B = AB

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}

1. A ∩ B ∩ C =

2. A ∪ B ∪ C =

Computer Representation of Sets

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

4-bits 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 6-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 5-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 ACodomain 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 ACodomain 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 : RZ

Domain is R

Codomain is Z

Definition 3

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

Example

f1 : RR

f2 : RR

f1(x) = x2

f2(x) = 1/x2

 (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 ) = { x | ∃s ∈ S ( x = 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 ∀a∀b ( f(a) = f(b) → a = b  ) One-to-one 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 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 functions similar to Question 14.2: 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 are one-to-one? A                 B

Proof

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

f : R R

∀x∀y ( f(x) = f(y) → x = y  )        Definition of one-to-one

∀x∀y ( x+1 = y+1 → x = y  )       Hypothesis by choosing f(x) = x + 1 and f(y) = y+1

Show:
p → q

x + 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

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

Examples

f(x) = x

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

22 = 4 = -22

32 = 9 = -32

-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

Onto?               True, ∀y∃x ( f(x) = y )

One-to-one?     False, ∀a∀b ( f(a) = f(b) → a = b  )

f(a) = f(d) = 3, a ≠ d.

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

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

1. Which functions are onto?

2. Which functions are one-to-one?

Example

Is f(x) = x2 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 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?

Definition

 Partial function f from A' to B is assignment of exactly one element of B to each element of A' ⊆ A. f(a) = b where b is the unique element of B assigned by f to the element a of A'. f : A' → B

Example - Below figure is partial function because Yugo does not map to an element.

Example - Integer division is a partial function because n ∈ Z, n/0 is undefined.

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. Note that f-1 is not a function when f is not onto. Invertible when one-to-one correspondence (i.e. one-to-one and onto)

Example

f : R+→R+

f(x) = x2

f-1(x) = x1/2

f( 3 ) = 32 = 9

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

Question 19.1 - From diagram below:

1. In (a), what is f( c )?

2. In (a), what is f-1( 1 )?

3. 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) =
4. Which of the following diagrams (a) - (e) have an inverse, f-1?

5. Which of the following are invertible?

Definition 9

 Inverse of one-to-one 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 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 = a

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

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 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/function-graphs/

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) = x2

Ordered pairs:

(x, x2)

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

an = 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.  a6 =

2.  a42 =

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

cn = 2 • 10n

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

cn = 2 • 10n, what is:

1.  c6 =

2.  c42 =

Sequence {bn}

bn = 1 • (-1)n

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

bn = 3 • (-1)n

the result is 3 or -3, give the result:

1.  b5 =

2.  b42 =

Sequence {dn}

dn = 6 • (1/3)n

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

dn = 6 • (1/3)n

d4 = 6 • (1/3)4

What is:

1.  d6 =

2.  d42 =

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

sn = -1 + 4n

a = -1

d = 4

s0, s1, s2, s3, s4, ...

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

-1, 3, 7, 11, 15, ...

Sequence {tn}

tn = 7 - 3n

a = 7

d = -3

t0, t1, t2, t3, t4, ...

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

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

Question 27

tn = 7 - 3n

t4 = 7 - 3•4 = -5

What is:

1.  t5 =

2.  t42 =

Definition

 String is the sequence a1a2...an

Examples

4-bit Binary Sequence {bn}

b1, b2, b3, b4

1011

Arbitrary Character Sequence {sn}

s1, s2, s3, ..., sn

hello world

Special Integer Sequences

Often want to determine formula for constructing terms of a sequence.

• 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?

sn = -1 + 4n

Examples

Find formula for sequence:

1. 1, 1/2, 1/4, 1/8, 1/16

1/20, 1/21, 1/22, 1/23, 1/24

geometric progression

a=1

r=1/2

an = (1/2)n

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

an = 2•n+1

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

-10, -11, -12, -13, -14

geometric progression

a=1

r=-1

an = (-1)n

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 3n.

• Determine the first couple of terms by adjusting for some constant:
• 1 = 31- 2
• 7 = 32- 2
• 25 = 33- 2

• Generalize on n

3n - 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: 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.

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, nZ+

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 aZ+

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.

• 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, r1, r2, r3, ..., rn, ... where each ri corresponds to a positive integer.