Chap 3: Mathematical Induction (I)

PRINCIPLE OF MATHEMATICAL INDUCTION:

To prove that P(n) is true for all positive integers n, where P(n) is a propositional function by 2 steps:

Basis      : We verify that P(1) is true @ show that an initial value is true for all Z⁺ of the propositional function.

Inductive  : We show that the conditional statement∀k (P(k) → P(k+1)) is true for all Z⁺ of k.

Similarly, we can say that mathematical induction is a method for proving a property defined that the property for integer n is true for all values of n that are greater than or equal to some initial interger.

                   P(1)^∀k(P(k) → P(k+1))) → ∀nP(n)

METHOD OF PROOF:

The proofs of the basis and inductive steps shown in the example illustrate 2 different ways to show an equation is true

p Transforming LHS and RHS independently until they seem to be equal.

p Transforming one side of equation until it is seen to be the same as the other side of the equation.

Chapter 3: Sequences and Mathematical Induction (I)

Presentation week. All notes are available in slides. You can download this slide at this link:
Chapter 3: Sequences and Mathematical Induction (I)

Chap 2: Set Theory (Part 6)

FUNCTIONS:

• A function f from a set X to a set Y is a relation from X to Y such that x Î X is related to one and only one y Î Y
• X is called the domain & Y is called the range. We say x is mapped into y.
• f = {(a, 3), (b, 3), (c, 5), (d, 1)}
• Functions are described as:
• Set of ordered pairs, example f as given before
• Using a formula such as f(x) = expression, example : f (x) = 2x + 2
• Illustration as in the example below

Chap 2: Set Theory (Part 5)

Relation between 2 sets:

™ A relation between two sets A and B is a subset of the Cartesian product AxB; A is called the source set and B is called the target set.

™ Often, we use notation aRb to denote that (a.b)єR and a~Rb to denote that (a,b)∉  ..

EXAMPLE:

Let U={0,1,2,3,4,5,6} represent set with bit strings

a) A= {2,4,5,6}

      bit string is 0010111

 b) B is the set of all odd integer, B Í U.

      B= {1,3,5} the bit string is 0101010

 c) C is a subset of U, containing all integers greater than 4.

      C={5,6} the bit string is 0000011

Chap 2: Set Theory (Part 4)

COMPUTER REPRESENTATION OF SETS:
 There are many ways to represent sets using a computer.
 One of the method is to store elements using an arbitrary ordering of elements of the universal set.
◦ Ordered set (less time-consuming)
◦ Unordered set (time consuming)
 An arbitrary ordering of the elements of U (universal set), for instance, a1, a2, …, an, then representing a subset of A of U with bit string of length n, where the ith bit in this string is 1 if a1 belongs to A and is 0 if a does not belong to A.

EXAMPLE:
Let U={0,1,2,3,4,5,6} represent set with bit strings (binary form)
a) A= {2,4,5,6}
      bit string is 0010111
 b) B is the set of all odd integer, BÍ U.
      B= {1,3,5} the bit string is 0101010
 c) C is a subset of U, containing all integers greater than 4.
      C={5,6} the bit string is 0000011

Chap 2: Concept of Sets (Part 3)

 SET OPERATIONS:

DEFINITION : UNION OF SETS

Let A and B be sets. The union of the sets A and B, denoted by

A υ B, is the set that contains those elements that are either in A

or in B, or in both.

A υ B = {x | (x Є A)v (x Є B)}

Chap 2: Concept of Sets (Part 2)

 SET OF NUMBERS:

Chap 2: Concept of Sets (Part 1)

DEFINITIONS:

①    A set is an unordered collection of objects, known as elements or members of the set.

②    Sets are usually denoted as capital letters; its elements are denoted as lowercase letters.

③    Often, but not always the object in a set have similar properties.

Eg. S = {a, b, c, d, …} (sets of all English alphabets)

       S= {a, 1, ali, law} (random sets)

1.4 Nested Quantifiers

DEFINITIONS:

It is existed where by one quantifier is within the scope of another.

Example: ∀x∃y(x+y=0) can be translated as

              ∀x Q(x) where Q(x) is ∃y P(x,y) and P(x,y) is x+y=0

Solving Stated Involving Nested Quantifers

Assume that the domain x,y є R, then

①     ∀x∀y(x+y=y+x) shows that x+y=y+x for all real number of x and y (commutative law)

②     ∀x∀y(x+y=0) shows that for all real number of x, there is a real number y such that x+y=0 (additive inverse)

③     ∀x∀y∀z(x+(y+z)=(x+y)+z) shows associative law for addition of real numbers.

To prove that ∀x∀y P(x,y) is true, we loop through the values for x, and for each x, we loop through the values through y; if it’s true if all values of x,y is true.