3.1 - 3.3

When is an integer x even?

If there is an integer k such that x = 2k

When is an integer, x, odd?

If there is an integer, k, such that x = 2k + 1

Parity

Parity is the classification of whether a number is odd or even

When do two numbers have the same parity?

if both numbers are both even or both odd

When do two numbers have the opposite parity?

When one number is odd and the other is even

When is a number a rational number?

If there exists integers x and y such that y does not equal 0 and r = x/y

When can an integer, x, divide integer y?

If and only if x does not equal 0 and y = kx, for some integer k

This is denoted as x | y, and as x∤y otherwise.

If x divides y, the y is a of x, and x is a __ or _ of y

multiple

factor

divisor

when is an integer a prime number?

if and only if n > 1, and the positive integers that divide n are 1 and n.

when is an integer a composite number?

If and only if n > 1, and there is an integer m such that 1 < m < n and m divides n

if x and c are real numbers, then how many inequalities can be true?

exactly one - <, =, or >

x >= c if and only if ___ or ___

x = c or x > c

x <= c if and only if ___ or ___

x = c or x < c

When is a number considered positive?

When x > 0

When is a number considered negative?

When x < 0

When is a number considered nonnegative?

When x >= 0

When is a number considered nonpositive?

When x <= 0

Theorem

A statement that can be proven to be true

Proof

A series of steps that follow logically from assumptions or from previously proven statements, with a final step that results in the statement of the theorem being proven.

Axioms

Statements that are assumed to be true

Proof by Exhaustion

Proving the statement by checking each element individually

Universal Generalization

A proof that names an arbitrary object in the domain and proves the statement for that object

When is an integer consecutive?

If one of the numbers is equal to 1 plus the other number

Counterexample

An assignment of values to variables that shows that a universal statement is false

What is the only way to be certain that a universal statement is true?

To individually test each object in the domain

Counterexamples in conditional statements

The counterexample must satisfy all the hypotheses and contradict the conclusion. If it cannot satisfy those requirements, then it is not a counterexample.

Existence Proof

A proof that shows an existential statement is true

Constructive proof of existence

An existential statement that asserts there is at least one element in a domain that has some particular properties.

Nonconstructive proof of existence

proves that an element with the required properties exists without giving a specific example.

How do you disprove an existential statement?

You have to show that every single element of the domain does not have the required properties. Usually, De Morgan’s Law will show the opposite, which is how you can show this.

What are the 6 allowed assumptions?

Thus and therefore

Can be used to start statements that follow from the previous statement

Let

The word used to introduce new variable names

Suppose

Can be used to introduce a new variable

ex. Suppose that x is odd

Since

Used if a statement depends on a fact that appeared earlier in the proof or assumptions - remind the reader of that fact before the statement

ex. Since x > 0 and y > z, then xy > xz

We will prove / we will show

Gives indication at the start of where the proof will end up

By definition

A fact known because of the definition

ex. The integer m is even. By definition, m = 2k for some integer k.

By assumption

A fact that is known because of an assumption

ex. By assumption, x is positive. therefore x > 0

In other words

Used to rephrase a statement in a more specific way

ex. We must show that the average of x and y is positive. In other words, we must show that (x +y) / 2 > 0

Gives / Yields

Show that one equation or inequality follows from another

ex. Substituting m = 2k into m² yields (2k)²

Name the five practices when writing proofs

1. Indicate when the Proof starts (Proof:) and when it ends (Square symbol)

2. Write proofs in complete sentences

3. Give the reader a roadmap of what has been shown, what is assumed, and where the proof is going.

4. Introduce each variable when the variable is used for the first time.

5. A block of equations should be introduced with English text and each step that does not follow from algebra should be justified.

Existential Instantiation

Law of logic that says if an object is known to exists, then that object can be given a name, so long as it is not being used to denote something else.

What are the four common mistakes in proofs?

1. Generalizing from examples - If a fact holds for some particular elements in a set, that does not imply that the fact holds for all elements of a set

2. Skipping Steps - Every step must be justified using allowed assumptions. Assuming a fact is true with showing reason is an error

3. Circular Reasoning - Using the fact to be proven in the proof itself

4. Assuming facts that have not yet been proven - Every fact used in a proof must be previously proven and referenced or must be established within the proof.