# Mathematical Proof and the Principles of Mathematics/Logic/The existential quantifier

If the universal quantifier is an extended version of conjunction, then what about an extended version of disjunction? This is the only other connective for which this type of extension makes sense, as you should be able to convince yourself.

## The existential quantifier

We define the existential quantifier in terms of the universal quantifier by taking
    For some $x$, $P(x)$
to mean
    Not (for all $x$, not $P(x)$).
The second statement is a bit complicated so lit's unpack it to see if the definition makes sense. For the statement
    For all $x$, $Q(x)$
to be False there would be need to a value of $x$ for which $Q(x)$ is False. Applying this when $Q(x)$ is not $P(x)$, this says that For the statement
    For all $x$, not $P(x)$
to be False there would be need to a value of $x$ for which $P(x)$ is True. In other words
    Not (for all $x$, not $P(x)$)
is the same as saying there is a value of $x$ for which $P(x)$ is True, or more briefly
    For some $x$, $P(x).$
There is another thing to notice about the statement
    Not (for all $x$, not $P(x)$)
namely that it depends on the order of the quantifier and the two negations. More specifically,
    Not not (for all $x$, $P(x)$)
and
    For all $x$, not not $P(x)$
are both equivalent to
    For all $x$, $P(x)$
which is not what we want.
One way to interpret the existential quantifier logically is to say that For all x, P(x) is the same as the disjunction of all the statements P(a), where a takes on every value in the universe of discourse. If the universe is discourse is finite then this can be written out explicitly. So if the universe of discourse consists of two objects 'a' and 'b', then
    For some $x$, $P(x)$
is the same as
    $P(a)$ or $P(b).$
This makes sense in terms of our definition since
    $P(a)$ or $P(b)$
is equivalent to
    not (not $P(a)$ and not $P(b)$)
If our universe of discourse has no objects, then the definition says that
    For some $x$, $P(x)$
is False no matter what $P(x)$ is. This may seem a bit odd, but it does make sense since if you rephrase the statement as
    There is some $x$ for which $P(x)$
then it would have to be False if the
    There is some $x$
part were False.
If our universe of discourse has one object, $a,$ then the definition says that
    For some $x$, $P(x)$
is the same as
    Not (for all $x$, not $P(x)$)
or
    Not not $P(a)$
or
    $P(a)$
Coincidentally, it turns out that
    For some $x$, $P(x)$
is equivalent to
    For all $x$, $P(x)$
in a universe with one object.

## Proving an existential quantifier

As usual with this type of definition, we get two rules of inference:
    From
       Not (for all $x$, not $P(x)$)
    deduce
       For some $x$, $P(x)$)
and
    From
       For some $x$, $P(x)$
    deduce
       Not (for all $x$, not $P(x)$)
These are very practical for doing proofs though so we'll add some others based on these. First, we'll prove, as an example:
    Prop. 1: $P(a)$ implies for some $x$, $P(x).$
Set up the proof of an implication in the usual way to get
| Line | Statement | Justification |
| 1 | $P(a)$ | Hypothesis |
| (something) |||
| n | For some $x$, $P(x)$ | ? |
| n+1 | $P(a)$ implies for some $x$, $P(x)$ | From 1 and n |
At this point we don't have anything but the definition to prove
    For some $x$, $P(x)$
so use that for the previous line.
| Line | Statement | Justification |
| 1 | $P(a)$ | Hypothesis |
| (something) |||
| n−1 | Not (for all $x$, not $P(x)$) | ? |
| n | For some $x$, $P(x)$ | From n−1 |
| n+1 | $P(a)$ implies for some $x$, $P(x)$ | From 1 and n |
Now we need to prove a negation, so assume the statement is true and derive a contradiction.
| Line | Statement | Justification |
| 1 | $P(a)$ | Hypothesis |
| 2 | For all $x$, not $P(x)$ | Hypothesis |
| (something) |||
| n−2 | $False$ | ? |
| n−1 | Not (for all $x$, not $P(x)$) | From 2 and n−2 |
| n | For some $x$, $P(x)$ | From n−1 |
| n+1 | $P(a)$ implies for some $x$, $P(x)$ | From 1 and n |
But from 2 we can deduce not $P(a)$, which leads to the needed contradiction and the proof can be completed.
| Line | Statement | Justification |
| 1 | $P(a)$ | Hypothesis |
| 2 | For all $x$, not $P(x)$ | Hypothesis |
| 3 | not $P(a)$ | From 2 |
| 4 | $False$ | From 1 and 3 |
| 5 | Not (for all $x$, not $P(x)$) | From 2 and 4 |
| 6 | For some $x$, $P(x)$ | From 5 |
| 7 | $P(a)$ implies for some $x$, $P(x)$ | From 1 and 6 |
Combining Prop. 1 with the other rules of inference we get
    From $P(a)$ derive
       For some $x$, $P(x).$

## Using an existential quantifier

The rule for using an existential quantifier is relatively complex. It's based on the following proposition which will be our second example proof.
    Prop. 2: (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$
First set up the proof of an implication in the normal way, and break up the hypothesis in separate statements.
Set up the proof of an implication in the usual way to get
| Line | Statement | Justification |
| 1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) | Hypothesis |
| 2 | For some $x$, $P(x)$ | From 1 |
| 3 | For all $x$, ($P(x)$ implies $Q$) | From 1 |
| (something) |||
| n | $Q$ | ? |
| n+1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$ | From 1 and n |
Use the definition to expand line 2 since that's the only way to use an existential so far.
| Line | Statement | Justification |
| 1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) | Hypothesis |
| 2 | For some $x$, $P(x)$ | From 1 |
| 3 | For all $x$, ($P(x)$ implies $Q$) | From 1 |
| 4 | Not (for all $x$, not $P(x)$) | From 1 |
| (something) |||
| n | $Q$ | ? |
| n+1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$ | From 1 and n |
Now we need to prove $Q$, and since there doesn't seem to be a direct proof, so set up an indirect proof.
| Line | Statement | Justification |
| 1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) | Hypothesis |
| 2 | For some $x$, $P(x)$ | From 1 |
| 3 | For all $x$, ($P(x)$ implies $Q$) | From 1 |
| 4 | Not (for all $x$, not $P(x)$) | From 1 |
| 5 | Not $Q$ | Hypothesis |
| (something) |||
| n−1 | $False$ | ? |
| n | $Q$ | From 5 and n−1 |
| n+1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$ | From 1 and n |
In order to get to a contradiction, we prove that line 4 is False, in other words
    For all $x$, not $P(x)$
is True. This is a universal so introduce an arbitrary constant $a$ and derive not $P(a)$
| Line | Statement | Justification |
| 1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) | Hypothesis |
| 2 | For some $x$, $P(x)$ | From 1 |
| 3 | For all $x$, ($P(x)$ implies $Q$) | From 1 |
| 4 | Not (for all $x$, not $P(x)$) | From 1 |
| 5 | Not $Q$ | Hypothesis |
| 6 | Choose $a$ | Arbitrary constant |
| (something) |||
| n−3 | not $P(a)$ | ? |
| n−2 | for all $x$, not $P(x)$ | From 6 and n−3 |
| n−1 | $False$ | From 4 and n−2 |
| n | $Q$ | From 5 and n−1 |
| n+1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$ | From 1 and n |
At this point $a$ can be plugged into line 3 and the rule of inference for statements can be used to complete the proof.
| Line | Statement | Justification |
| 1 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) | Hypothesis |
| 2 | For some $x$, $P(x)$ | From 1 |
| 3 | For all $x$, ($P(x)$ implies $Q$) | From 1 |
| 4 | Not (for all $x$, not $P(x)$) | From 1 |
| 5 | Not $Q$ | Hypothesis |
| 6 | Choose $a$ | Arbitrary constant |
| 7 | $P(a)$ implies $Q$ | From 3 |
| 8 | Not $P(a)$ | From 5 and 7 |
| 9 | For all $x$, not $P(x)$ | From 6 and 8 |
| 10 | $False$ | From 4 and 9 |
| 11 | $Q$ | From 5 and 10 |
| 12 | (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$ | From 1 and 11 |
In prose format:
    Prop. 2: (For some $x$, $P(x)$) and (for all $x$, ($P(x)$ implies $Q$)) implies $Q.$
    Proof: Assume for some $x$, $P(x).$ Also assume for all $x$, ($P(x)$ implies $Q.$ We prove $Q$ by contradiction so assume not $Q.$ To get a contradiction, it is enough to prove for all $x$, not $P(x)$, since it the negation of the first assumption. Choose $a.$ From the second assumption, $P(a)$ implies $Q.$ But this and not $Q$ imply not $P(a).$ This holds for any $a$, so for all $x$, not $P(x)$ and this, with the first assumption, is the required contradiction.
By combining this proposition with the other rules of inference, including the rule for proving a universal, we can recast it as a rule of inference:
    If one has
       For some $x$, P(x)
    and if by choosing $a$ as an arbitrary constant one can derive
       $P(a)$ implies $Q$
    then deduce $Q$.
In order to prove the implication, one would then assume $P(a)$ and derive $Q$. It's easier to combine the
    Choose $a$
with the
    Assume $P(a)$
steps into one to get
    Choose $a:P(a).$
Read this as:
    Choose $a$ such that $P(a).$
With this bit of streamlining, the rule of inference becomes
    If one has
       For some $x$, $P(x)$
    and if by choosing $a:P(a)$ one can derive $Q$, then deduce $Q$.

## For each and for every

The two quantifiers can be combined it two ways:
    For some $x$, for all $y$, $P(x,y).$
    For all $y$, for some $x$, $P(x,y)$
and
For clarity, it is better to rephrase the first as
    There is some $x$ so that for every $y$, $P(x,y).$
    For each $y$, there is some $x$ so that $P(x,y)$
and the second as
Despite just being a change in the order of the quantifiers, these two statements are different. To see this, let the universe of discourse consist of magical rings and let $P(x,y)$ stand for "$x$ rules $y$". The second statement merely states that every ring is ruled by some ring. One could easily imagine that every ring rules itself, so this wouldn't be saying much. But the first statement says there is a ring, which we might call the One Ring, which rules all the other rings; that's quite a ring. Note that we're using the word 'every' in the first statement to emphasis that the $x$ works for every $y$, while in the second statement we're using the word 'each' to emphasize that the value of $x$ depends on $y.$
So the second statement does not imply the first, but we can proof, as our third example, that the first statement implies the second.
    Prop. 3: There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$
Set up a direct proof in the usual way, then use the existential according to the new rule.
| Line | Statement | Justification |
| 1 | There is some $x$ so that for every $y$, $P(x,y).$ | Hypothesis |
| 2 | Choose $a$: for all $y$, $P(a,y).$ | Constant satisfying condition |
| (something) |||
| n−1 | For each $y$, there is some $x$ so that $P(x,y).$ | ? |
| n | For each $y$, there is some $x$ so that $P(x,y).$ | From 1, 2 and n−1 |
| n+1 | There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$ | From 1 and n |
We now need to prove
    For each $y$, there is some $x$ so that $P(x,y)$
which is a universal, so prove it for an arbitrary $b$
| Line | Statement | Justification |
| 1 | There is some $x$ so that for every $y$, $P(x,y).$ | Hypothesis |
| 2 | Choose $a$: for all $y$, $P(a,y).$ | Constant satisfying condition |
| 3 | Choose $b$ | Arbitrary constant |
| (something) |||
| n−2 | There is some $x$ so that $P(x,b).$ | ? |
| n−1 | For each $y$, there is some $x$ so that $P(x,y).$ | From 3 and n−2 |
| n | For each $y$, there is some $x$ so that $P(x,y).$ | From 1, 2 and n−1 |
| n+1 | There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$ | From 1 and n |
Now we can plug $b$ into line 2 and the proof is done.
| Line | Statement | Justification |
| 1 | There is some $x$ so that for every $y$, $P(x,y).$ | Hypothesis |
| 2 | Choose $a$: for all $y$, $P(a,y).$ | Constant satisfying condition |
| 3 | Choose $b$ | Arbitrary constant |
| 4 | $P(a,b)$ | From 2 |
| 5 | There is some $x$ so that $P(x,b).$ | From 4 |
| 6 | For each $y$, there is some $x$ so that $P(x,y).$ | From 3 and 5 |
| 7 | For each $y$, there is some $x$ so that $P(x,y).$ | From 1, 2 and 6 |
| 8 | There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$ | From 1 and 7 |
In the prose version there's no need to repeat lines 6 and 7, so it becomes:
    Prop. 3: There is some $x$ so that for every $y$, $P(x,y)$ implies for each $y$, there is some $x$ so that $P(x,y).$
    Proof: Assume there is some $x$ so that for every $y$, $P(x,y).$ Choose $a$ so that for every $y$, $P(a,y)$ and let $b$ be arbitrary. Then $P(a,b)$ and so for some $x$, $P(x,b).$ This holds for arbitrary $b$, therefore for each $y$ there is $x$ so that $P(x,y).$