Produced by Charles Wells.  Home    Website TOC    Website Index 

Last edited 9/3/2007 2:53:00 PM

EXISTENCE ASSERTIONS  STUB

existential quantifier

For a assertion  P, an assertion of the form xP(x) means that there is at least one mathematical object  c of the type of  x for which the assertion P(c) is true. The symbol  is pronounced "there is" or "there are" and is called the existential quantifier. See Remark  under such that.

Example

Let  n be of type integer and suppose P(n) is the assertion " n is divisible by  6". Then the assertion nP(n) can be expressed in the mathematical register in these ways:

There is an integer divisible by  6. Citation: LewPap9820, Mea93387.

There exists an integer divisible by  6. Citation: Che88744, Kre94903.

There are integers divisible by  6. Citation: HenLarMarWoo94213, Ros93293.

Some integers are divisible by  6. Citation: Mea61152.

For some integer n, 6 divides n. Citation: Kle99678, Sto952614.

Remark

If the assertion xP(x) is true, there may be only one object  c for which P(c) is true, there may be many  c for which P(c) is true, and in fact P(x) may be true for every  x of the appropriate type. For example, in mathematical English the assertion, "Some of the computers have sound cards", allows as a possibility that only one computer has a sound card, and it also allows as a possibility that all the computers have sound cards. Neither of these interpretations reflect ordinary English usage.

In particular, in mathematical discourse, the assertion

"Some primes are less than  3."

is true, even though there is exactly one prime less than  3. However, I do not have an unequivocal citation for this. It would be a mistake to regard such a statement as false since we often find ourselves making existential statements in cases where we do not know how many witnesses there are.

In general, the passage from the quantifying English expressions to their interpretations as quantifiers is fraught with difficulty. Some of the basic issues are discussed in [], Chapter 3; see also [], [] and [], page 12 (written for students).

See also universal quantifier, order of quantifiers, and Example  under indefinite article.

existential instantiation

When (x)P(x) is known to be true (see existential quantifier), one may choose a symbol c and assert P(c). The symbol c then denotes a variable mathematical object that satisfies P. That this is a legitimate practice is a standard rule of inference in mathematical logic. Citations: HasRee93774.

[ label: exqdef] Let Q(x) be a assertion. The proposition xQ(x) means there is some value of x for which the assertion Q(x) is true. The symbol  is called an existential quantifier, and a proposition of the form xQ(x) is called an existential proposition. A value c for which Q(c) is true is called a witness to the proposition xQ(x).

Remark

One may indicate the type of the variable in an existential proposition in the same way as in a universal proposition.

Example

Let x be a real variable and let Q(x) be the assertion x>50. This is certainly not true for all integers x. Q(40) is false, for example. However, Q(62) is true. Thus there are some integers x for which Q(x) is true. Therefore xRQ(x) is true, and 62 is a witness.

Exercise

Find an existential proposition about real numbers with exactly 42 witnesses.

Exercise

In the following sentences, the variables are always natural numbers. P(n) means n is a prime, E(n) means n is even. State which are true and which are false. Give reasons for your answers.

Exercise

, n(E(n)P(n) )

Exercise

n (E(n)∨P(n) )

Exercise

n(E(n)P(n))

Exercise

n(E(n)P(n))

Answer: a: True. Witness: 2. b: False. Counterexample: 9. c: True. Witness: 2. d: False. Counterexample: 3.

Exercise

[ label: andQ]  Which of these propositions are true for all possible one-variable assertions P(x) and Q(x)? Give counterexamples for those which are not always true.

,, x(P(x)Q(x))xP(x)xQ(x)

,, xP(x)xQ(x)x(P(x)Q(x))

,, x(P(x)Q(x))xP(x)xQ(x)

,, xP(x)xQ(x)x(P(x)Q(x))

Answer: (a) True. (b) True. (c) True. (d) False; a counterexample is given by taking P to be x>7 and Q to be x<7.

Exercise

Do the same as for Problem  [andQ] with ` &vee;' in the propositions in place of ` '.

Exercise

Do the same as for Problem  [andQ] with ` ' in the propositions in place of ` '.

Usage