Reasoning: An Introduction to Logic, Sets, and Functions

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))

Proof.

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.

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).