Skip to main content

Subsection 8.4.1 The Key Ideas

Existential Claims: Suppose that we want to prove that there exists some object with some desired property. We’ve seen that sometimes we can do that by combining premises with inference rules to derive a claim of the form ∃x (P(x)).

But sometimes we can do something even simpler:

We can prove that something exists by exhibiting it.

Prove: \(\exists\)x (Prime(x) \(\wedge\) (x > 20))

23

Of course, it’s not quite that simple. We do have to show that the example we’ve provided does meet the requirements of the claim we’re trying to prove. Continuing with our example:

Since we are taking as theorems the claim of basic mathematics, we have that 23 > 20. And we can show that 23 is prime by showing that it is not evenly divisible by any positive integer that is less than it. (This works because there is a finite number of such integers. So we can simply try all of them.)

Universal Claims: We’ve already seen examples of the use of both direct and indirect (by contradiction) proof to prove claims of this sort.

But sometimes we can do something even simpler:

We can prove that a universal claim is false by exhibiting a single counterexample.

Video cover image

Consider the claim: \(\forall\)x ((x > 1000) \(\rightarrow \) Composite(x)). Maybe we think this is likely because large numbers have a lot of potential factors.

Proof that the claim is false: 1013, which we can show is prime by showing that it is not evenly divisible by any integer less than it.

Consider the claim: All birds can fly.

Proof that the claim is false:

Emus are birds.

Emus cannot fly.

Many nonflying emus have been observed (including this baby one).

Exercises Exercises

1.

Consider the following claim:

There exists a quadratic equation with a single root.

  1. This claim is true and can be proved by a single example.

  2. This claim is true but cannot be proved so with a single example.

  3. This claim is false and can be shown so by a single counterexample.

  4. This claim is false but cannot be proved so with a single counterexample.

Answer.
Correct answer is A.
Solution.

Explanation: A single example suffices to prove this existence claim. One such is:

x2 – 2x + 1 = (x- 1) (x -1)

Which has the single root 1.

2.

Consider the following claim:

x (\(\frac{x}{3}\) < x-3)

  1. This claim is true and can be proved by a single example.

  2. This claim is true but cannot be proved so with a single example.

  3. This claim is false and can be shown so by a single counterexample.

  4. This claim is false but cannot be proved so with a single counterexample.

Answer.
Correct answer is C
Solution.
Explanation. While it’s true that, once x gets large, x/3 is less than x-3, that’s not true for small values of x. So we can disprove the claim by exhibiting, for example the case x = 3. Then: ( x/3 = 1) > (x-3 = 0)