The Hong Kong University of Science and Technology · FACULTY OF MATHEMATICS

MATH2001 Chap.1 Definitions, Theorems and Proofs

- one subject, every graph, every model, every mark
7 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 1 of 5 · MATH2001

Definitions, Theorems and Proofs

Start with the sentence, not the symbols

Proof writing begins by deciding what kind of claim is on the page. A statement has a definite truth value; an expression with an unbound variable does not. Domains and quantifiers turn variable-dependent expressions into claims. The order of those quantifiers matters because it decides whether a witness may depend on an earlier choice.

Once the sentence is closed, implication separates the assumption from the target, and the contrapositive supplies an equivalent route when the direct one is awkward.

Definitions create legal moves

Definitions are working tools. Expanding even, divisible, injective or Cauchy exposes the object that must be constructed or the condition that must be verified.

Direct proof assumes the hypothesis and reaches the conclusion. Contrapositive assumes the negated conclusion and derives the negated hypothesis. Contradiction assumes the claim fails and reaches an impossibility.

A universal claim starts with an arbitrary admissible object, while existence needs a witness that is checked against both the domain and the property.

Induction is a logical chain

Induction proves a statement across the natural numbers by establishing a starting case and closure under successor.

The induction hypothesis is an assumption about one arbitrary admissible index, not a fact available at every index without explanation. The step must use that assumption to prove the next case, and the conclusion must return to the exact declared range. This chapter trains the opening and closing sentences that keep those obligations visible.

In this chapter

What this chapter covers

  • 01

    Statements and free variables

  • 02

    Implication and contraposition

  • 03

    Quantifier order and negation

  • 04

    Direct and contrapositive proof

  • 05

    Contradiction and counterexamples

  • 06

    Mathematical induction

  • 07

    Proof repair and communication

Worked example · free

Prove a divisibility implication by contrapositive

Q [10 marks]. AskSia-authored practice. Prove that if an integer n squared is divisible by five, then n is divisible by five. The marks shown are an AskSia study allocation, not the University marking scheme.
The arrows move from a sentence with a truth value through its logical form and quantifier scope to the exact proof obligation.The arrows move from a sentence with a truth value through its logical form and quantifier scope to the exact proof obligation.statementtruth valueimplicationassume Pquantifierscope firstproofjustify QRead a theorem from grammar to obligationChanging a quantifier or an implication changes the proof you owe.
The arrows move from a sentence with a truth value through its logical form and quantifier scope to the exact proof obligation.
  • 3State the contrapositive using the possible nonzero remainders modulo five.
  • 4Square each remainder class and reduce the result modulo five.
  • 3Return from the contrapositive to the original implication.
Prove the contrapositive. If five does not divide n, division by five gives a remainder of one, two, three or four. Squaring these residues gives one, four, nine and sixteen, which reduce modulo five to one, four, four and one. None is zero, so five does not divide n squared. Therefore, whenever five divides n squared, five must divide n. The remainder cases are exhaustive, which is the step that makes the argument apply to every integer.
Sia tip — When a contrapositive uses residues, list every allowed remainder before calculating so that no case disappears.
Glossary

Key terms

Statement
A sentence that is either true or false after all variables have been assigned or quantified.
Implication
A claim that a conclusion follows whenever its hypothesis holds.
Contrapositive
The logically equivalent implication obtained by negating and reversing the conclusion and hypothesis.
Quantifier
A phrase such as for every or there exists that binds a variable over a stated domain.
Witness
An explicitly supplied object that establishes an existential claim after its required conditions are checked.
Counterexample
An admissible case that satisfies a universal claim's hypothesis and makes its conclusion fail.
Induction Hypothesis
The assumed statement at one arbitrary index used to prove the statement at its successor.
FAQ

Definitions, Theorems and Proofs FAQ

Why is testing examples not a proof?

Examples inspect only the chosen cases, while a universal statement covers every object in its domain. A single valid counterexample can disprove the statement, but many successful examples cannot rule out a later failure. Use examples to discover a pattern, then replace them with an arbitrary element, an exhaustive case split or induction.

When is contrapositive better than direct proof?

Use it when the negation of the conclusion has a concrete form that unlocks a definition, such as an integer being odd or a function failing a uniqueness condition. Write the equivalent contrapositive before starting. That declaration prevents the reversed direction from looking like an unsupported change of claim.

What makes an induction step complete?

Fix an arbitrary admissible k, assume the statement at k, and use that assumption to establish the statement at k plus one. Identify the line where the hypothesis is used. Then invoke induction over the declared starting range. A calculation that never uses the hypothesis does not establish the required dependency.

Study strategy

Exam move

Build a one-page decision chart keyed to logical form. For each practice theorem, write only the opening two lines and the closing line before filling the middle. This exposes whether the method matches the claim and whether the conclusion returns to the original direction. Keep separate error labels for converse, inverse, contrapositive, switched quantifiers, invalid counterexample and unused induction hypothesis.

Review the labels more often than the individual problems, because the same logical defect appears across many mathematical topics. After completing a proof, audit every introduced symbol: record its domain, whether it was arbitrary or chosen, and where its defining property was used. For induction, highlight the base value, the exact hypothesis and the next-index target in different colours.

This short audit catches hidden assumptions while the argument is still easy to repair.

Working through Definitions, Theorems and Proofs in MATH2001? Sia is AskSia’s AI Mathematics tutor — ask any MATH2001 Definitions, Theorems and Proofs question and get a clear, step-by-step explanation grounded in how MATH2001 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MATH2001 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works