Free degree-level computing lessons for careful independent study.
Aplailasain by Static Carnival

Degree Level Programmes · Formal Computing Foundations · Lesson 20

Proof Techniques: Direct Proof and Counterexample

Construct basic arguments and disprove universal claims.

Back to coursePreviousNext lesson

Lesson overview

Construct basic arguments and disprove universal claims.

CourseFundamentals of Computing
Topic strandProof
Assessment styleDigital exam practice
EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

  • Write a direct proof for a simple implication.
  • Use a counterexample to disprove a universal statement.
  • Separate evidence from proof.

Learning outcomes

  • By the end of this lesson, you can write a direct proof for a simple implication.
  • By the end of this lesson, you can use a counterexample to disprove a universal statement.
  • By the end of this lesson, you can separate evidence from proof.

Key vocabulary

direct proofcounterexampleuniversal claimimplication

What this lesson is about

A direct proof starts from assumptions and definitions, then derives the conclusion step by step. A counterexample disproves a universal claim by showing one case where the claim fails.

Many examples can suggest a claim, but one valid counterexample can destroy it.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Direct proofNamed proof technique. A proof that starts with the assumptions and definitions, then derives the conclusion in justified steps.
CounterexampleNamed proof technique. A single valid case that makes a universal claim false.
Universal claimPhrase. A claim about every object in a domain. It requires proof for the whole domain, not many examples.
DivisibilityPhrase. The statement d divides n means n = dk for some integer k.

Formal notation and definitions

To prove ∀x(P(x) ⇒ Q(x)), assume arbitrary x with P(x), then derive Q(x).To disprove ∀x P(x), find one x such that ¬P(x).

How to read the symbols

∀x(P(x)⇒Q(x))\forall x(P(x)\Rightarrow Q(x))For every x, if property P holds then property Q must hold.
¬P(x)\neg P(x)Not P of x; the property P fails for x.
counterexampleOne valid case that makes a universal claim false.

Use proof notation to distinguish a general argument from a single example. Counterexamples disprove universal claims.

Degree-level reasoning

A proof is a general argument over a whole domain, not a persuasive example. The domain and assumptions must be visible.

The strongest answers identify the structure of the claim first: universal, existential, implication, equality, recurrence or invariant.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

To disprove 'all sorted lists contain no duplicates', one sorted list such as [1, 1, 2] is enough.

Objects: the universal claim, an arbitrary object x for proof, and a specific counterexample for disproof.

Model cue: Use a proof route: assume P(x), apply definitions, derive Q(x). For disproof, use a single counterexample box.

2. Mathematical working

Claim: ∀n∈Z, 4∣n⇒2∣n\text{Claim: }\forall n\in\mathbb{Z},\ 4\mid n\Rightarrow 2\mid n4∣n⇒n=4k for some k∈Z4\mid n\Rightarrow n=4k\text{ for some }k\in\mathbb{Z}n=4k=2(2k)⇒2∣nn=4k=2(2k)\Rightarrow2\mid n
Plain text version
To prove ∀x(P(x) ⇒ Q(x)), assume arbitrary x with P(x), then derive Q(x).
To disprove ∀x P(x), find one x such that ¬P(x).

Worked use: To disprove 'every sorted list has no duplicates', the sorted list [1, 1, 2] is enough. It is sorted, but it has a duplicate, so the universal claim is false.

3. How to read the working

  1. Read the claim as universal: it is about every integer n, not several tested examples.
  2. Use the definition of divisibility: 4 | n means n = 4k for some integer k.
  3. Rewrite n = 4k as n = 2(2k) to match the definition of divisibility by 2.
  4. For counterexamples, one valid object in the domain that breaks the claim is enough to disprove it.

4. Computing meaning and check

A counterexample is decisive because a universal claim covers every case. A direct proof must work for an arbitrary object, not a favourite example.

Now check: Write a direct proof that if n is divisible by 4, then n is even. State the arbitrary integer and the definition you use.

Worked example

From scenario to formal reasoning

Scenario: To disprove 'all sorted lists contain no duplicates', one sorted list such as [1, 1, 2] is enough.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

To disprove 'every sorted list has no duplicates', the sorted list [1, 1, 2] is enough. It is sorted, but it has a duplicate, so the universal claim is false.

Worked solution structure

How a strong answer should be written

  1. Define: State the domain and the objects under discussion. For this lesson, begin from To prove ∀x(P(x) ⇒ Q(x)), assume arbitrary x with P(x), then derive Q(x).
  2. Apply: Use the relevant definition from proof; do not rely on the diagram, wording or intuition alone.
  3. Check: Test a boundary case, counterexample candidate or representation limit.
  4. Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is thinking many examples prove a universal claim. Examples support intuition; proof covers the whole stated domain.

Guided practice

  1. Write a direct proof that if n is divisible by 4, then n is even.
  2. Name the arbitrary integer, the assumption and the definition of divisibility.
  3. Disprove the claim 'every sorted list has no duplicates' with one sorted list.
  4. Explain why five positive examples of a universal claim are still not a proof.

Quick checks

1. To prove a universal implication directly, you should start with:

2. What disproves a universal claim?

Digital exam practice

Example exam task

Prove directly that if n is divisible by 4 then n is even, then disprove 'every sorted list has no duplicates' with a counterexample.

Notation toolkit

a∣ba\mid b

Means: a divides b exactly

How to use: Use it to unpack divisibility assumptions.

∀x P(x)\forall x\ P(x)

Means: a universal claim about every x

How to use: Use it when deciding whether proof or counterexample is needed.

∃x ¬P(x)\exists x\ \neg P(x)

Means: there exists a counterexample

How to use: Use it to disprove a universal claim.

What a good answer is expected to show

A strong answer for this lesson defines the universal claim, an arbitrary object x for proof, and a specific counterexample for disproof, applies the proof method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read the claim as universal: it is about every integer n, not several tested examples.
  2. Use the definition of divisibility: 4 | n means n = 4k for some integer k.
  3. Rewrite n = 4k as n = 2(2k) to match the definition of divisibility by 2.
  4. For counterexamples, one valid object in the domain that breaks the claim is enough to disprove it.

Model answer

Reveal model answer
4∣n⇒∃k∈Z (n=4k)4\mid n\Rightarrow \exists k\in\mathbb{Z}\ (n=4k)n=4k=2(2k)⇒2∣nn=4k=2(2k)\Rightarrow2\mid n∀x P(x) is false if ∃x ¬P(x)\forall x\ P(x)\text{ is false if }\exists x\ \neg P(x)

If 4 | n, then n = 4k for some integer k. Therefore n = 2(2k), so 2 | n and n is even. The claim 'every sorted list has no duplicates' is disproved by [1,1,2], which is sorted but contains a duplicate. A counterexample defeats a universal claim.

Practise next

  1. Write a direct proof that if n is divisible by 4, then n is even.
  2. Name the arbitrary integer, the assumption and the definition of divisibility.

Self-marking criteria

  • Uses an arbitrary integer n.
  • Applies the definition 4 | n means n = 4k.
  • Rewrites 4k as 2(2k).
  • Gives [1,1,2] or equivalent as a sorted duplicate counterexample.
  • Separates proof from supporting examples.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Proof by Contradiction and Contrapositive.