BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 4 — Questions and Answers
Question 1: Which of the following is an example of a vacuously true statement?
- All prime numbers greater than 2 are odd
- All integers divisible by 4 are even
- All members of the empty set satisfy every property (Correct answer)
- All real solutions of x²+1=0 are positive
Correct answer: All members of the empty set satisfy every property
A universally quantified statement over an empty domain (or empty set) is vacuously true because there are no elements to serve as counterexamples.
Question 2: What is the principal difference between an axiom and a theorem?
- Axioms are always true; theorems may be false
- Axioms are assumed without proof; theorems are derived by proof (Correct answer)
- Axioms apply only to numbers; theorems apply generally
- Theorems are simpler than axioms
Correct answer: Axioms are assumed without proof; theorems are derived by proof
Axioms are foundational statements accepted without proof, while theorems are statements derived from axioms and prior results through logical deduction.
Question 3: Which of the following proof strategies is best suited to show that a mathematical object with a certain property does NOT exist?
- Constructive proof
- Proof by exhaustion
- Proof by contradiction (Correct answer)
- Proof by example
Correct answer: Proof by contradiction
To show non-existence, assume the object exists and derive a contradiction, thereby disproving its existence.
Question 4: In set theory, the symmetric difference A △ B is defined as:
- A ∩ B
- (A ∪ B) \ (A ∩ B) (Correct answer)
- A \ B
- A ∪ B
Correct answer: (A ∪ B) \ (A ∩ B)
The symmetric difference A △ B consists of elements in A or B but not in both, i.e., (A ∪ B) \ (A ∩ B).
Question 5: Gödel's first incompleteness theorem states that any consistent formal system strong enough to express arithmetic:
- Is complete and decidable
- Contains unprovable truths (Correct answer)
- Can prove its own consistency
- Has no true statements
Correct answer: Contains unprovable truths
Gödel showed every sufficiently powerful consistent formal system contains true statements that cannot be proved within the system.
Question 6: Which logical equivalence is expressed by the absorption law?
- P ∧ (P ∨ Q) ≡ P (Correct answer)
- P ∨ (P ∧ Q) ≡ P ∧ Q
- P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ R
- P ∨ Q ≡ Q ∨ P
Correct answer: P ∧ (P ∨ Q) ≡ P
The absorption law states P ∧ (P ∨ Q) ≡ P (and dually P ∨ (P ∧ Q) ≡ P), 'absorbing' the compound expression.
Question 7: If f: A → B and g: B → C are both bijective functions, what can be said about g ∘ f?
- g ∘ f is injective but not necessarily surjective
- g ∘ f is surjective but not necessarily injective
- g ∘ f is bijective (Correct answer)
- g ∘ f may not be a function
Correct answer: g ∘ f is bijective
The composition of two bijections is always a bijection; injectivity and surjectivity both compose.
BMath Bachelor of Mathematics Bachelor of Mathematics: Mathematical Proof and Logic 4
Which of the following is an example of a vacuously true statement?