Existence and Universality

by George E. Hrabovsky, President, MAST

Where We Have Been

In the last column we explored how to construct proofs. We even managed to construct several to show how the system works and to establish the rules of logic under which we are operating.

Where Will We Go in This Column

In this column we will expand upon the proof methods of last column to describe how to consider things in general and in specific.

The Basic Ideas of Existence, Universality, and Uniqueness

In the first column of this series we explored propositional statements and their connectives. In this column we will explore another kind of statement. This statement is neither true nor false until some specific thing is provided. Such a statement is called an open sentence. The specific thing that needs to be specified is called a variable. Only when the variable is specified does the open sentence become a proposition. For example,

becomes a proposition only when we specify what x is. Another name for an open sentence is a predicate. The set of all possible values that the variable can have is called the universe of discourse. Some values for a variable will make the predicate true, while others will make it false. The set of all values from the universe of discourse that make the open sentence true is called the truth set of the predicate. In our example the truth set has one element, {2}. We can denote an open sentence whose variable is x with the symbol .
If we can make the statement that a truth set is the entire universe of discourse for a given open sentence then we say that the proposition is universal. We can also state that for all instances of the variable the open sentence is true. The symbol for universality is and means, "For all... ." Thus if we make the statement for all x then , we can write,

If we can make the statement that a truth set is nonempty for a given open sentence we say that the variable exists. The symbol for existence is and means, "There exists... ." So, if we make the statement that there exists x such that , we can write,

If we can make the statement that the truth set contains only one element we say that the variable has a unique value. Uniqueness is denoted and means, "There exists a unique... ." Thus if we make the statement that there exists a unique x such that , we can write,

There are two important theorems about quantifiers that will be important later,

Theorem 4-1:

Proof: is true only if is false. Another way of saying this is that is true only if there are no elements of the solution set in the universe of discourse. Another way of saying that is is true only when the solution set is nonempty. This is another way of saying . Thus the two propositions are equivalent.

Theorem 4-2:

Proof: is true only if is false. Another way of saying this is that is true only when the solution set is empty. Another way of saying that is the is true only when there are no elements of the solution set in the universe. This is another way of saying . Thus the two propositions are equivalent.

Proving Existence

The most direct kind of proof of existence is to specify some element of the universe of discourse that makes the proposition true. Such a proof is called a constructive proof. For example, if we state that there exists an even number in the set of counting numbers from 1 to 10, a constructive proof would be the statement that 2 is even. A similar approach is to show that there has to be some element of the universe of discourse that makes the proposition true, instead of showing that such an element actually exists
Another approach is described by the following steps

Assume that ¬ (∃ x) p(x) is true, by Theorem 4 - 2 this is equivalent to (∀ x ... ds to a contradiction, ==> ¬ (∃ x) p(x) is false, ==> (∃ x) p(x) is true .

This is an application of the reductio ad absurdum approach to proofs.

Proving Universality

To begin with you must always specify the universe of discourse. Then make the statement that x is a member of this universe without making any special statements about x. Then you must show by a series of logical arguments that is true for x. Since x has no special properties, it is an arbitrary member of the universe, then the statement must be true. This is a form of direct proof.
We can also apply reductio ad absurdum,

Assume that ¬ (∀ x) p(x) is true, by Theorem 4 - 1 this is equivalent to (∃ x ... ds to a contradiction, ==> ¬ (∀ x) p(x) is false, ==> (∀ x) p(x) is true .

Counterexamples

Sometimes we need to prove . By theorem 4-1 this is equivalent to . If you can find such an instance of x it is termed a counterexample.

Proving Uniqueness

There are two steps for proving uniqueness. The first is to prove existence by whatever means are available. Assume two values from the universe of discourse, and . Show that the proposition is true for both. Show by a series of logical arguments that this implies that . Thus there exists a unique x that makes the proposition true.