Last edited 9/26/2008 10:16:00 AM
|
|
EXISTENCE ASSERTIONS
Not written yet. Meanwhile, check out existential quantification in Wikipedia
existential
quantifier
For a assertion
P, an assertion
of the form x
P(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
n
P(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 x
P(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 ` ∨' in the propositions in place of ` '.
Exercise
Do the same as for
Problem [andQ] with ` ' in the
propositions in place of `
'.