Proofs

Question 1

How would you define an even integer?

Answer 1

An integer n is even, if and only if, n equals twice some integer.

Question 2

How would you define an odd integer

Answer 2

An integer n is odd, if only if, n equals twice some integer plus 1

Question 3

Given that a and b are integers

Is 6a²b even?

Answer 3

Question 4

Given a and b are integers

Is 10a + 8b + 1 odd?

Answer 4

Question 5

Integers are closed under which operations?

Answer 5

Addition, subtraction, multiplication

Meaning for example, integer+integer=integer. But integer/integer does not necessarily equal and integer

Question 6

How would you define a prime number?

Answer 6

An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if n = rs, then either r or s equals n

Question 7

How would you define a composite integer?

Answer 7

An integer n is composite if, and only if, n>1 and for some integers r and s, n=rs such that 1 < r,s < n

Question 8

Is every integer greater than 1 either prime or composite? If so, why?

Answer 8

Given an integer n. If n is greater than one and n=rs where r and s is

Question 9

Prove that ∃ an even integer, n, that can be written in two ways as a sum of two prime numbers.

Answer 9

Suppose n = 10. 10=2k where k is an integer (5) meaning 10 is even. 10 can be written as 5+5 or 7+3. 5=5⋅1 and 7=7⋅1 and 3=3⋅1 meaning all these numbers are prime.

Question 10

Suppose r and s are integers.

Prove that ∃ an integer k such that 22r + 18s = 2k

Answer 10

Let k=11r + 9s. This means that k is an integer because it is the sum of two integers (11r and 9r are integers as it integers are also closed under multiplication)

Question 11

True or false?

Disproving a statement is the same as proving the negation statement true.

Answer 11

True

Question 12

What is the difference between constructive proofs of existence and nonconstructive proofs of existence

Answer 12

In constructive, it is more theoretical meaning it basically proves it by insert values into the predicate and showing that it is true. On the other hand, nonconstructive does this by using known rules (more algebraic)

Question 13

How would you prove a statement false through a counterexample?

Answer 13

Find the negation of that statement and prove that the negation is true. Then the original statement, will be false by default.

Question 14

How would you prove a statement true through a counterexample?

Answer 14

Find the negation of that statement and prove that the negation is false. Then the original statement, will be true by default.

Question 15

Disprove the following using a counterexample

∀ a,b ∈ ℝ, if a²=b² then a=b

Answer 15

First, find the negation: ∃ a,b ∈ ℝ such that a²=b² and a≠b. And note the nature of squares where the sign of the negative will not matter. Suppose a=2 and b=-2. here a²=b² but they are not equavalent

Question 16

What is the “method of generalizing from a generic particular”?

Answer 16

It is used for universal quanitifers. In contrast to the method of exhaustion, it supposes that x is a particular but arbituary chosen element of a set and show that x satisfies the statement.

x must be particular (meaning a single number) and x must be arbituary (meaning that any value substituted into x will give the same output).

Question 17

What is it called when the “method of generalizing from a generic particular” is applied to the form “If P(x) then Q(x)”

Answer 17

Method of direct proof

Question 18

What are the steps for the method of direct proof?

Answer 18

1. Make sure it is in the form ∀ x ∈ D, if P(x) then Q(x)
2. Start the proof by supposing x is a particular but arbitrarily chosen value of D. For which P(x) is true. It can be written as “Suppose x∈D and P(x)”
3. Finally prove that Q(x) is true by using previously established rules and definitions

Question 19

Prove that the sum of any two even integers is even.

Answer 19

Formally written: ∀ a, b ∈ ℤ, if a and b are even, then ab is even.
1. Suppose ∀ a,b ∈ ℤ and a and b are even
2. a = 2c where ∀ j ∈ ℤ
3. b = 2d where ∀ d ∈ ℤ
4. a+b=2c+2d=2(c+d) Using laws of the distrubutive properties of algebra
5. Since integers are closed under addition, c+d is can be written as some integer k. a+b=2k
6. Therefore a+b=2k (a+b is even) as it follows the form n=2k meaning the statement is true
7. Make sure to end with a QED (□)

Question 20

For the statement: “Every complete bipartite graph is connected”

Write the first sentence of the proof (the “starting point”) and the last sentence of the proof (the “conclusion to be shown”)

Answer 20

It is helpful to write it in its formal form:
For all graphs G, if G is a complete bipartite, then G is connected.
**Starting point: ** Suppose that G is a particular but arbitirary graph and G is a complete bipartite
Conclusion to be shown G is connected □

Question 21

Fill in the blanks for the following theorum

Theorum: For all integers r and s, if r is even and s is odd, then 3r+2s is even.

Answer 21

a) The definition of even and odd
b) Substitution (Algebra)
c) Integers are closed under products and sums
d) The definition of even

Question 22

True or false?

At the start of a proof, you must always write “proof”

Answer 22

True

Question 23

True or false?

Proofs don’t need to be self contained (meaning you don’t have to define every variable)

Answer 23

False. All variables should be defined with their domains and such.

Question 24

What is a indirect proof?

Also known as a reductio ad absurdum or proof by contradiction

Answer 24

Supposing that the statement is to be proved false. Then you work through the proof until you find a contradiction. The contradiction shows that the statement is not false, therefore true.

For example. imagine a man is accuesed of robbing a bank and he says that he did not rob it. Suppose the man did commit the crime. Then, at the time of the crime he must of been at the bank. However, at the time of the crime, he was in a meeting with 20 people far from the bank and all 20 people testified that he was indeed in the meeting. This contradicts the supposition that he committed the crime, therefore he did not commit the crime.

Question 25

Use proof by contradiction to show that there is no greatest integer. | Also known as indirect proof

Answer 25

Question 26

Use indirect proof to show that there is no integer that is even and odd

Answer 26

Question 27

Wee ## Footnote testing

Question 28

What is the notation for "n divides m"

Answer 28

n | m

Question 29

What is the notation for n does not divide m

Answer 29

n∤m

Question 30

If k is any non zero integer, does k divide 0?

Answer 30

Yes because 0=k⋅0

Question 31

# True or false? When one positive integer divides a second positive integer, the first is less than to the second. (givOe they are divisable)

Answer 31

False.

Question 32

#True or false? n is divisible by m if n equals d times some integer where d is a non zero number

Answer 32

False. n is divisible by m **if and only if** n equals d times some integer where d is a non zero number

Question 33

What are the only divisors of 1?

Answer 33

1 and -1

Question 34

If one positive integer, n can be divided by another positive integer, m, which one is greater?

Answer 34

According to the properties of divisibility, if one positive integer can be divided by another positive integer then the second one is lesser or equal to the first. Therefore, m is less or equal to n.

Question 35

Write the definition of divisibility formally.

Answer 35

Question 36

Does 4|5?

Answer 36

No, since 15/4 is not an integer.

Question 37

Prove that for all integers a,b,c and c if a|b and b|c then a|c

Answer 37

Question 38

# True or false? Any integer greater than 1 that is not a prime can be written as a product of prime numbers

Answer 38

True.

Question 39

Write 3300 in standard factored form

Answer 39

Question 40

What does quotient-remainder theorem say?

Answer 40

When any integer `n` is divided by any positive integer, `d`, the result is a quotient `q` multiplied by `d` plus a nonnegative integer remiander `r` that is smaller than `d`

Question 41

True or false? The remainder in quotient remainder theorum can be negative

Answer 41

False. It must be nonnegative

Question 42

Answer 42

Question 43

What does `n div d` mean?

Answer 43

The integer qutient obtained when n is divided by d (n/d). It is equivalent to integer division in python

Question 44

What does `n mod d` mean?

Answer 44

The nonnegative integer remiander when n is divided by d (n/d). It equivalent to remainder division in python (n%d)

Question 45

# True or false? According to quotient-remainder theorum, `n mod d` (remainder) equals one of the integers from 0 to d

Answer 45

False. The true statement is that it equals one of the integers from _0 to d-1_. Say we divide n by d, we cannot have a remainder of d because then there can be another set of groups.

Question 46

Computer `32 div 9` and `32 mod 9` without a calculator

Answer 46

`32 div 9` = 3 *(32//9)* `32 mod 9` = 5 *(32%9)*

Question 47

Suppose today is Tuesday, and neither this year nor next year is a leap year. What day of the week will it be 1 year from today?

Answer 47

1 year is 365 days. There are 52 weeks in a year `365 mod 52` = 1 Therefore, 364 days from now will be tuesday but we need it to be a year so 1 more day is wednesday

Question 48

Suppose m is an integer. If `m mod 11` = 6, what is `4m mod 11`?

Answer 48

`m mod 11`=6 means the remiander obtained when m is divided by 11 is 6. According to quotient-remainder theorum, this can be written as so: m=11q+6 `4m mod 11` can be written as the following according to quotient-remainder theorum: 4m=44q+24 (multiplied *m=11q+6*) 4m=11(4q)+24 4m=11q+24 (q is an integer because it closed under multiplication) 4m=11q+22+2 (the remainder has to be between 0 inclusive and 11) 4m=11(q+2)+2 4m=11q+2 (q is an integer because it closed under multiplication) Therfore the remainder is 2

Question 49

Given an integer n, how would you show that n is even (by using `q mod d`)

Answer 49

`n mod 2`=0

Question 50

Given an integer n, how would you show that n is odd (by using `q mod d`)

Answer 50

`n mod 2`≥0

Question 51

What does parity mean?

Answer 51

If an integer is odd or even. ## Footnote For instance 5 has odd parity and 28 has even parity

Question 52

What is proof by division into cases?

Answer 52

It is when you have an or statement and you proof each case of the or statement. Suppose two integers m and n have opposite parity. In proof of division into cases, you must proof that m is even then n is odd but then you must also proof that m is odd then n is even.

Question 53

Answer 53

Question 54

What is meant by "if an integer n is divided by an integer d, the possible remainders 0,1,2...,(d-1)

Answer 54

If an integer is divided by another integer, the remainder is between 0 and the divisor. *(Remainder cannot be bigger than the divisor because that will make another group)*

Question 55

What is the floor of a number?

Answer 55

The **integer** to the immediate left of that number on the number line. the floor of a number x is equal to a unique integer n such that n-1 < x ≤ n ## Footnote Note it is not the number rounded down

Question 56

What is the ceiling of a number?

Answer 56

The **integer** to the immediate right of that number on the number line. the ceiling of a number x is equal to a unique integer n such that n ≤ x < n+1 ## Footnote Note it is not the number rounded up

Question 57

What does ⌊x⌋ mean?

Answer 57

The floor of x

Question 58

What does ⌈x⌉ mean?

Answer 58

The ceiling of x

Question 59

# Compute ⌊x⌋ and ⌈x⌉ for the following values: a) x=25/4 b) 0.999 c) x=-2.01

Answer 59

a) ⌊x⌋=6, ⌈x⌉=7 b ⌊x⌋=0, ⌈x⌉=1 c) ⌊x⌋=-3, ⌊x⌋=-2

Question 60

# For this question use: ceiling and floor The 1,370 students at a college are given the opportunity to take buses to an out of town event. Each bus holds a maximum of 40 passengers. a) For reasons of economy, the leader of the event will send only full buses. What is the maximum number of buses the event leader will send? b) If the vent leader is willing to send one partially filled bus, how many buses will be needed to allow all the students to take the trip?

Answer 60

Question 61

What does gcd(x, y) mean?

Answer 61

The greatest common divisor/denominator of x and y. Where it is an integer and non zero.

Question 62

What are the properties of gcd(x, y)

Answer 62

1. d is a common divisor of both x and y: d|x and d|y 2. For every integer, c, that is divisable by x and y, c is less than or equal to d (meaning d must be the biggest common denominator)

Question 63

Find gcd(10²⁰, 6²⁰)

Answer 63

Question 64

In the definition of greatest common divisor, gcd(0,0) is not allowed. Why not? What would gcd(0,0) equal if it were found in the same way as the greatest common divisors for other pairs of numbers?

Answer 64

0 divided by any number is still zero. Meaning there is no **greatest** common denominator. *This follows the property of gcd where the common divisor must be the largest*

Question 65

Given that r is a positive integer, then what does gcd(r, 0) equal to

Answer 65

It equals to r. This is because 0 shares a common denominator with every number (0/any number = 0).

Question 66

True or false? To prove that A=B, you can say A≤B and B≤A

Answer 66

True. This is because you know that A is greater or equal to B and B is greater or equal to A. Then you for the statement to be true, they cannot be both greater than each other so you are left with that they are equal.

Question 67

If a=bq+r. What does gcd(a, b) equal to

Answer 67

gcd(a,b)=gcd(b,r) | Just remember it

Question 68

Find the gcd(330, 156)

Answer 68

Question 69

What is the set-roster notation?

Answer 69

It is when all the elements of a set is written between braces. ## Footnote For example {1, 2, 3} denotes the set whose elements are 1, 2, and 3.

Question 70

What is the axiom of extension?

Answer 70

The axium of extension says that a set is completely defined by what its elements are. Not the order in which they are listed or that fact that some elements be listed more than once.

Question 71

# Let A= {1, 2, 3}, B = {3, 1, 2}, and C = {1, 1, 2, 3, 3, 3} What are the elemnts of A, B, and C? How are A, B, and C related

Answer 71

A,b, and C have exactly the same three elements: 1, 2, and 3. Therefore, by the axium of extension, A, B and C are simply different ways to represent the same set.

Question 72

# True or false {0} = 0

Answer 72

False. {0} ≠ 0. ## Footnote This is because {0} is a set with one element, namely 0, whereas 0 is just the symbol that represents the number zero.

Question 73

How many elements are in the set {1, {1}}

Answer 73

2 elements. Note that 1 and {1} are different elements as 1 is a symbol representing the number one and {1} is a set whose only element is 1

Question 74

# For each nonnegative intger n, let U_n = {n, -n} Find U₀

Answer 74

U₀ = {0, -0} = {0, 0} = {0} ## Footnote By the axiom of extension

Question 75

# In the statement {x ∈ S | P(x)} What does the "|" mean?

Answer 75

"such that"

Question 76

# Given two sets A, B When is can A be called a subset of B

Answer 76

A is called a subset of B if and only if every element of A is also an element of B

Question 77

What does A ⊆ B mean?

Answer 77

A is a subset of B ## Footnote Alternative ways to say this is "A is contained in B" or "B contains A"

Question 78

What does the following mean?

Answer 78

"A is not a subset of B" and mathmatically: there is at least one element x such that x ∈ A but x ∉ B

Question 79

What is the difference between **subset** and **proper subset**

Answer 79

Suppose A and B are sets. Subset means for A to B contained in B. But proper subset means for A to B contained in B with B having atleast one more element than A

Question 80

Answer 80

Question 81

Answer 81

Question 82

What is this: (a, b)

Answer 82

(a, b) denotes the ordered pair consisting of a and b together with a being the first element while b is the second element.

Question 83

# Given two element (a, b) and (c, d) When can (a, b) = (c, d)

Answer 83

(a, b) = (c, d) if and only if a=c and b=d

Question 84

Answer 84

Question 85

Answer 85

Question 86

# Given sets A₁, A₂,..., A_n How would you find the general cartesian product of these sets?

Answer 86

Symbolically: **A₁ × A₂ × ... × A_n = {(a₁, a₂,..., a_n) | a₁∈A₁, a₂∈A₂,...,a_n∈A_n}** | or alternatively you can read it as basically expanding sets into tuples

Question 87

# Let A = {x, y}, B={1, 2, 3} Find B × A

Answer 87

Question 88

# Let A = {x, y} Find A × A

Answer 88

Question 89

# Let A = {x, y}, B={1, 2, 3} How many elements are in A × B, B × A, and A × A.

Answer 89

- A × B: Has 6 elements - B × A: Has 6 elements - A × A: Has 4 elements *Note that the number of elements is the product of the number of each elements in the sets.*

Question 90

# Let A = {x, y}, B={1, 2, 3}, and C= {a, b} Find (A × B) × C

Answer 90

Question 91

# Let A = {x, y}, B={1, 2, 3}, and C= {a, b} Find A × B × C

Answer 91

Question 92

Given that: A = {m ∈ ℤ | m = 6r + 12 for some r ∈ ℤ} B = {m ∈ ℤ | n = 3s for some s ∈ ℤ} | **Prove that A ⊆ B**

Answer 92

Question 93

Given that: A = {m ∈ ℤ | m = 6r + 12 for some r ∈ ℤ} B = {m ∈ ℤ | n = 3s for some s ∈ ℤ} | **Disprove that B ⊆ A**

Answer 93

Question 94

Using the language of subsets, when is set A equal to set B?

Answer 94

Given sets A and B, A = B if and only if every element of A is in B and every element of B is in A

Question 95

Answer 95