Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

• Sets
  • The Language of Sets
  • Set Operations
  • Set Identities
• Set Cardinality
  • Countable Sets
• Functions
  • Types of Functions
  • Operations on Functions
  • Computability
• Sequences and Summations
  • Types of Sequences
  • Summation Formulae
• Matrices
  • Matrix Arithmetic

Sets S E C T I O N 2. 1

• Definition of sets
• Describing Sets
  • Roster Method
  • Set-Builder Notation
• Some Important Sets in Mathematics
• Empty Set and Universal Set
• Subsets and Set Equality
• Cardinality of Sets
• Tuples
• Cartesian Product

• Sets are one of the basic building blocks for the types of objects considered in discrete mathematics.
  • Important for counting.
  • Programming languages have set operations.
• Set theory is an important branch of mathematics.
  • Many different systems of axioms have been used to develop set theory.
  • Here we are not concerned with a formal set of axioms for set theory. Instead, we will use what is called naïve set theory.

• Roster Method
• Set-Builder Notation
• Interval Notation

• List all the members of a set.
• S a,b,c,d = { }
• Order not important S a,b,c,d b,c,a,d = { } = { }
• Each distinct object is either a member or not; listing more than once does not change the set. S a,b,c,d a,b,c,b,c,d = { } = { }
• Elipses () may be used to describe a set without listing all of the members when the pattern is clear. ... S a,b,c,d = { } , ......,z

• Set of all vowels in the English alphabet: V = {a,e,i,o,u}
• Set of all odd positive integers less than: 10 O = {1,3,5,7,9}
• Set of all positive integers less than: 100 S
• Set of all integers less than 0: = {1,2,3,........,99} S -3,-2,-1} = {....,

• Specify the property or properties that all members must satisfy: S x | x is a positive integer less than 100} = { O | = { x x is an odd positive integer less than 10} O = { x | is odd and < 10} x x
• A predicate may be used: ∈ Z+ S = | P( { x x )}
• Example: S = x | Prime(x )} {
• Positive rational numbers: Q = { + x R x = p q | / , for some positive integers p } , q ∈

[ a ] = { x a x b

, b

|

}

[ a) = { x a x b

, b

|

< }

≤ ≤

(a ] = { x a x b

, b

| <

}

≤

(a) = { x a x b

, b

| < < }

≤

closed interval [ a,b ] open interval (a,b)

• Sets can be elements of sets.

{ {1,2,3} , a b,c

, { } }

{N,Z,Q,R}

• The empty set is different from a set containing the empty set. = {} ∅ ≠ { ∅ } ∅

Definition: The set of all subsets of a set A, denoted P (A) , is called the

power set of A.

Example: If A = {a,b} then

P

(A) = {ø, {a},{b},{a,b}}

• If a set has n elements, then the cardinality of the power set is. (In 2 n Chapters 5 and 6, we will discuss different ways to show this.)

Set Operations S E C T I O N 2. 2

• Set Operations
  • Union
  • Intersection
  • Complementation
  • Difference
• More on Set Cardinality
• Set Identities
• Proving Identities
• Membership Tables

Example: U = { 0,1,2,3,4,5 6,7,8,9,10

,

} A = { 1,2,3,4,5

}, B ={ 4,5,6,7,8

}

1. A B Solution: { 1,2,3,4,5 6,7,8 , } ∪
2. A B Solution: { } 4,5 ∩

3.

Solution: { 0,6,7,8,9,10

}

4.

Solution: { 0,1,2,3,9,10 }

1. A B Solution: { }
   • 1,2,3
2. B A Solution: { 6,7,8 }

• Different ways to prove set identities:

1. Prove that each set (side of the identity) is a subset of the other.
2. Use set-builder notation and propositional logic.
3. Membership Tables: Verify that elements in the same combination of sets always either belong or do not belong to the same side of the identity. Use to indicate it is in the set and a to indicate that it is 1 0 not.

Functions S E C T I O N 2. 3

• Definition of a Function.
  • Domain, Cdomain
  • Image, Preimage
• Injection, Surjection, Bijection
• Inverse Function
• Function Composition
• Graphing Functions
• Floor, Ceiling, Factorial
• Partial Functions (optional)

• Functions may be specified in different ways:
  • An explicit statement of the assignment. Assignment of Grades in a Discrete Mathematics Class example.
  • A formula. f (x) = + 1 x
  • A computer program.
    • A Java program that when given an integer n, produces the n th Fibonacci Number (covered in the next section and also in Chapter ). 5

Let A = B = R, the reals. Determine which are injections, surjections, bijections:

• f(x) = x,

2,

• f(x) = x

3,

• f(x) = x

• f(x) = x + sin(x),

• f(x) = | x |

Let A = B = R, the reals. Determine which are injections, surjections, bijections:

injective, surjective, bijective

• f(x) = x,

2, none

• f(x) = x

3, injective, surjective, bijective

• f(x) = x

• f(x) = x + sin(x), injective, surjective, bijective |, none

• f(x) = | x

Example: Let f be the function from { a,b,c } to {1,2,3} such that

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

Is f invertible and if so what is its inverse?

Solution

:

The function f is invertible because it is a one-to-one correspondence. The inverse function reverses the correspondence given by f, so f

-1 (1) = c, f (2) = a, and f (3) = b.

-1

-1

Example Let f: Z Z be such that f(x) = x + . Is f invertible, and if so,

2:



what is its inverse?

Solution: The function f is invertible because it is a one-to-one correspondence. The inverse function f -1 reverses the correspondence so f - 1 (y) = y – 1.

Example Let f: R R be such that

3:

. Is f invertible,

and if so, what is its inverse?

→

Solution:

The function f is not invertible because it is not one-to-one.

Composition

Floor and Ceiling Functions

Sequences and Summations S E C T I O N 2. 4

• Sequences.
  • Examples: Geometric Progression, Arithmetic Progression
• Recurrence Relations
  • Example: Fibonacci Sequence
• Summations
• Special Integer Sequences (optional)

• Sequences are ordered lists of elements.
  • 1, 2, 3, 5, 8
  • 1, 3, 9, 27, 81, .......
• Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music.
• We will introduce the terminology to represent sequences and sums of the terms in the sequences.

• Given a few terms of a sequence, try to identify the sequence. Conjecture a formula, recurrence relation, or some other rule.
• Some questions to ask?
  • Are there repeated terms of the same value?
  • Can you obtain a term from the previous term by adding an amount or multiplying by an amount?
  • Can you obtain a term by combining the previous terms in some way?
  • Are they cycles among the terms?
  • Do the terms match those of a well known sequence?

• Here are three interesting sequences to try from the OESIS site. To solve each puzzle, find a rule that determines the terms of the sequence.
• Guess the rules for forming for the following sequences:
  • 2, 3, 3, 5, 10, 13, 39, 43, 172, 177, ...
    • Hint: Think of adding and multiplying by numbers to generate this sequence.
  • 0, 0, 0, 0, 4, 9, 5, 1, 1, 0, 55, ...
    • Hint: Think of the English names for the numbers representing the position in the sequence and the Roman Numerals for the same number.
  • 2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, ...
    • Hint: Think of the English names for numbers, and whether or not they have the letter ‘e.’
• The answers and many more can be found at http://oeis.org/Spuzzle.html

Summations

from Table 2, slide 113

Recurrence Relations

Definition: A recurrence relation for the sequence { a } is an equation

n

that expresses a in terms of one or more of the previous terms of the

n

sequence, namely, a, a, ..., a

, for all integers n with n ≥ n

, where n

0 1

n-1

is a nonnegative integer.

• A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.
• The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect.

Example: Let { a } be a sequence that satisfies the recurrence relation

n

a = a + 3 for n = 1,2,3,4, .... and suppose that

a = 2. What are a, a

n n-1

1 2

and a ?

[Here a = is the initial condition. ]

Solution: We see from the recurrence relation that

a a + 3 = 2 + 3 = 5

=

a = 5 + 3 = 8

a = 8 + 3 = 11

• Finding a formula for the n th term of the sequence generated by a recurrence relation is called solving the recurrence relation.
• Such a formula is called a closed formula.
• Various methods for solving recurrence relations will be covered in Chapter 8 where recurrence relations will be studied in greater depth.
• Here we illustrate by example the method of iteration in which we need to guess the formula. The guess can be proved correct by the method of induction (Chapter 5).

2.6. Matrices