Last edited 6/5/2009 11:04:00 AM
EXISTENCE
STATEMENTS
An existence statement is a statement about an assertion
P(x) containing a variable x that claims that there is at least
one value of x that makes the
assertion P true.
Examples
¨
There is a real number bigger than 2. True.
¨
There is a real number x for which 
. True.
¨
There is a real number x for which . False.
The existential quantifier symbol
For an assertion P, a statement of the form 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 exist(s)" and is called the existential
quantifier. Also discussed in the section on symbols.
How existential statements are
worded.
Let n be of
type integer and suppose P(n) is the
assertion " n is divisible
by 6". Then the statement can be expressed in Mathematical English in
these ways:
There is an integer divisible by
6.
There exists an
integer divisible by 6.
There are integers divisible
by 6.
Some
integers are divisible by 6.
For some integer n, 6 divides n.
Remarks
If the assertion 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.
These
interpretations are different from ordinary English usage.
In particular, in mathematical discourse, the statement
"Some primes are less than 3" is true, even though there is exactly one prime less than 3,
and the statement “Some primes are integers” is true, even though all primes
are integers. The Handbook (under
existential quantifier) has more discussion about this and references.
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 ` ∨' in the propositions in place of ` '.
Exercise
Do the same as for
Problem [andQ] with ` ' in the
propositions in place of ` '.
Usage
75.3 Definition:
existential quantifier
Let Q(x) be a predicate. The statement ( x)Q(x)
means there is some value of x for
which the predicate Q(x) is true. The symbol is called an existential quantifier, and a statement of the form ( x)Q(x) is called
an existential statement. A
value c for which Q(c) is true is called a witness
to the statement ( x)Q(x).
75.3.1
Remark One may indicate the type of
the variable in an existential statement in the same way as
in a universal statement.
75.3.2 Example Let x
be a real variable and let Q(x) be the predicate 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 ( x:R)Q(x) is true, and 62 is a
witness.
75.3.3
Exercise Find an existential statement
about real numbers with exactly 42 witnesses.
75.3.4 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.
a)( n)(E(n) AP(n))
b)(Vn)
(E(n) P(n))
c)( n)(E(n) = P(n))
d)(Vn)(E(n) = P(n))
(Answer
on page 247.)
75.3.5 Exercise Which
of these statements are true for all possible one-variable predicates
P(x) and Q(x)? Give counterexamples for those which
are not always true.
a)(Vx)(P(x) A Q(x)) = (Vx)P(x) A (Vx)Q(x)
b)(Vx)P(x)A(Vx)Q(x) = (Vx)(P(x)AQ(x))
c)( x)(P(x) A Q(x)) = ( x)P(x) A ( x)Q(x)
d)( x)P(x) A ( x)Q(x) = ( x)(P(x) A Q(x))
(Answer
on page 247.)
75.3.6
Exercise Do the same as for Problem
75.3.5 with ‘’in the statements in place of ‘A’.
75.3.7 Exercise Do the same as for Problem 75.3.5 with‘
=’in the statements in
place of ‘A’.
75.3.8 Usage The
symbols V and are called quantifiers. The
use of quantifiers makes an extension of the propositional calculus called the predicate calculus which allows one to say things about an infinite number of instances in
a way that the propositional calculus does not.