definitions

Question 1

pigeonhole principle and example

Answer 1

is a useful tool for drawing conclusions when the size of a collection exceeds the number of possible variations of some distinguishing trait. ex- many people have same SAT score

Question 2

what is proof by induction and example

Answer 2

Induction means proving something by proving the first statement is true and then proving that all other statements follow from that first statement.
If P(x) true, then P(x+1) also true
example: prime factorization theorem

Question 3

what is proof by contradiction and example

Answer 3

a form of proof that establishes the truth or validity of a proposition by showing that the proposition’s being false would imply a contradiction. ex: irrationality of radica 2

Question 4

strategy for proof of infinite prime numbers

Answer 4

The strategy for proving that there are infinitely many prime numbers is to show that, for each and every given natural number, we can always find a prime number that is larger than that natural number.

Question 5

division algorithm

Answer 5

Th e Division Algorithm. Suppose n and m are natural numbers. Then there exist unique num-bers q ( for quotient) and r ( for remainder), that are either natural numbers or zero, such that m nq r and 0 r n 1 ( r is greater than or equal to 0 but less than or equal to n 1).

Question 6

1-1 correspondence?

Answer 6

the idea that two collections of objects are equally numerous, precisely if there is a one - to - one correspondence between the elements of the two collections, its a type of comparison

Question 7

strategy for proof that + or - even integers have same cardinality as natural numbers

Answer 7

, the even natural numbers are paired with the positive integers, whereas, the odd natural numbers are paired with the negative integers or zero.

Question 8

strategy for proving that real numbers don’t have same cardinality as natural numbers

Answer 8

If the set of real numbers and the set of natural numbers have the same cardinality, then it would be possible to list all the reals in some order — one for each natural number. But, in fact, we will construct a real number in decimal form that does not appear anywhere in the right - hand column. That is, we will show that there are so many more real numbers than natural numbers that given any pairing between the natural numbers and the reals, a real number will always be left out — it is impossible to produce a one - to - one correspondence.

Question 9

what is a power set?

Answer 9

Let S be a set ( finite or infinite). Then the cardinality of the power set of S, ( S), is strictly greater than the cardinality of S.