Final Exam

Question 1

a|b

Answer 1

a divides b
b is a multiple of a

Question 2

c = a(mod b)

Answer 2

c-a=bm

Question 3

Direct Proof

Answer 3

Start with the assumption of the premise
Use known facts, definitions, and previously proven theorems to logically deduce the conclusion.
Each step should be justified and should follow logically from the previous steps.
Conclude by stating that the conclusion logically follows from the premise.

Question 4

Proof by Contradiction

Answer 4

Assume the negation of the statement you want to prove (i.e., assume the statement is false).
Deduce logical consequences from this assumption.
Eventually, reach a contradiction with known facts or axioms.
Since a statement and its negation cannot both be true, the original assumption (that the statement is false) must be false, implying that the original statement is true.

Question 4

Proof by Contrapositive

Answer 4

Begin by negating the conclusion of the theorem or statement.
Then, rewrite the negated conclusion in an equivalent form, which is the contrapositive of the original statement.
Prove the contrapositive using a direct proof.
Since the contrapositive is logically equivalent to the original statement, proving the contrapositive proves the original statement as well.

Question 4

Proof by Division into Cases

Answer 4

Identify different cases that cover all possibilities related to the statement.
Prove each case separately using direct or another suitable method of proof.
Make sure that the cases are exhaustive (cover all possibilities) and mutually exclusive (no overlap between cases).
Conclude by showing that each case being true leads to the truth of the overall statement.

Question 5

Proof of a Biconditional

Answer 5

Prove the implication in one direction (if part) using any suitable proof method (direct, contrapositive, contradiction, etc.).
Prove the implication in the other direction (only if part) using the same or another suitable proof method.
Conclude by stating that both implications have been proven, thus establishing the biconditional statement.

Question 6

To prove a universal statement, we must…

Answer 6

show that it is true for all elements in the domain under consideration. This typically involves using a direct proof, mathematical induction, or proof by contradiction, depending on the nature of the statement

Question 7

To prove an existential statement, we must…

Answer 7

provide at least one example or instance where the statement holds true. This demonstrates that there exists at least one element in the domain for which the statement is true. Proof by example, constructive proof, or proof by contradiction are common methods for proving existential statements.

Question 8

To disprove a universal statement, we must…

Answer 8

find a counterexample, i.e., a specific element in the domain for which the statement is false. This shows that the statement does not hold true for all elements in the domain.

Question 9

To disprove an existential statement, we must…

Answer 9

we must show that the statement is false for all elements in the domain. This can be accomplished by demonstrating that there is no element in the domain that satisfies the given conditions or by showing a contradiction.

Question 10

Statement

Answer 10

In mathematics, a statement (also called a proposition)
is a declarative sentence that is either true or false, but not both.

Question 11

Conditional P → Q

Answer 11

False only when P is true and Q is false

Question 12

Tautology

Answer 12

A tautology is a compound statement S that is true for
all possible combinations of truth values of the component
statements that are part of S

Question 12

Contradiction

Answer 12

A contradiction is a compound statement S that is false
for all possible combinations of truth values of the component
statements that are part of S.

Question 13

negation of the conditional statement

Answer 13

¬(P → Q) ≡ P ∧ ¬Q

Question 14

the contrapositive of a conditional statement is

Answer 14

¬Q → ¬P
A conditional statement is logically equivalent to its
contrapositive

Question 15

The converse of a conditional statement

Answer 15

P→Q is Q → P

Question 16

Set

Answer 16

a well-defined collection of objects that can be thought of
as a single entity itself

Question 17

Element

Answer 17

one of the objects in a set

Question 18

Set-roster notation

Answer 18

writing all of a set’s elements between
braces

Question 19

variable

Answer 19

a symbol representing an
unspecified object that can be chosen from a given set U

Question 20

constant

Answer 20

a specific member of the universal set.

Question 21

open sentence (or predicate)

Answer 21

a sentence
P(x1, x2,· · · , xn) that contains a finite number of variables and
becomes a true or false statement when specific values are
substituted for the variables.

Question 22

Truth set

Answer 22

the truth
set of P(x) is the set of all elements in the universal set that
can be substituted for x to make P(x) true

Question 23

set builder notation

Answer 23

use a predicate to define a rule that must
be satisfied by all elements in the set

Question 24

empty set

Answer 24

a set with no elements, usually denoted ∅

Question 25

The Universal quantifier

Answer 25

∀
(for all, for every, for each, given any, …)

Question 26

The Existential quantifier

Answer 26

∃
(there exists, there is a, there is at least one, for some, for at
least one, ···)

Question 27

Negations of
Quantified
Statements

Answer 27

The negation of a statement of the form
(∀x ∈ U) (P(x))
is logically equivalent to a statement of the form
(∃x ∈ U) (¬P(x))

Question 28

Argument

Answer 28

a sequence of statements called
premises, followed by a final statement called the
conclusion

Question 29

Proof

Answer 29

a convincing argument that some mathematical
statement is true

Question 30

Axiom

Answer 30

some mathematical statement that is generally
accepted without proof

Question 31

Definition

Answer 31

an agreement about the meaning of a term

Question 32

Conjecture

Answer 32

a statement that we believe might be true, but
that we have not yet proved.

Question 33

Theorem

Answer 33

a mathematical statement for which we have a
proof

Question 34

Lemma

Answer 34

a mathematical statement that was proven mainly to
help with proving some theorem.

Question 35

Corollary

Answer 35

a theorem that follows almost immediately from
the proof of some other theorem.

Question 36

A ∩ B

Answer 36

The intersection of A and B is the set of
all elements x in U such that x is in A and x is in B.

Question 37

A ∪ B

Answer 37

The union of A and B is the set of all
elements x in U such that x is in A or x is in B (or both).

Question 38

A-B

Answer 38

The set difference of A and B is the set
of all elements x in U such that x is in A, but x is not in B.

Question 39

A^c

Answer 39

The complement of A, is the set of all
elements x in U such that x is not in A.

Question 40

Injection

Answer 40

a one-to-one function, is a function where every element of the domain maps to a distinct element in the codomain. In other words, no two different elements in the domain map to the same element in the codomain.

Question 41

Surjection

Answer 41

an onto function, is a function where every element in the codomain is mapped to by at least one element in the domain. In other words, the range of the function coincides with its codomain

Question 42

Function

Answer 42

A function from a set A to a set B is a rule that associates
each element of the set A with exactly one element of the set
B. A function from A to B is called a mapping from A to B.

Answer 43

If a ∈ �, then the element of � that is associated with a is
denoted by (�(�)) is called the image of � under �.
If � � = � with � ∈ �, then � is the preimage of � for �.

Question 44

Composite function

Answer 44

(g ∘ f )= g(f(x))

Answer 45

For the inverse of a function to be a function, the original
function must be a bijection

Answer 46

Let n be an integer. If a and b are integer, then we
say that a is congruent to b modulo n provided that n
divides a – b