Lila at 21:12, 28 September 2021

2021-09-28T21:12:52Z

Lila: Created page with "==Proving a statement with a universal quantifier== To prove a statement of the form :For all $x$ , $P(x)$ first ask the reader to pick an arbitrary const..."

2021-09-28T20:31:26Z

Created page with "==Proving a statement with a universal quantifier== To prove a statement of the form :For all <math>x</math>, <math>P(x)</math> first ask the reader to pick an arbitrary const..."

New page

==Proving a statement with a universal quantifier==
To prove a statement of the form
:For all <math>x</math>, <math>P(x)</math>
first ask the reader to pick an arbitrary constant <math>a</math>, then prove the statement <math>P(a)</math>. The idea is that, since the constant <math>a</math> was chosen at random, with no assumptions other than that it's an object in the universe of discourse, the proof of <math>P(a)</math> is valid hold no matter the choice of <math>a</math>. Therefore <math>P(x)</math> is true for all <math>x.</math>

Note that for a proof if implication, the reader is asked to make an assumption, then you as the prover must derive a conclusion. Similarly, in the proof of a universal, the reader is asked to do something, namely pick a constant, then you as the prover must derive a conclusion. So we'll state the rule of inference in a way similar to the way the first rule inference for implication is stated.
:If by choosing <math>a</math> as an arbitrary constant one can derive <math>P(a)</math>, then deduce
::For all <math>x</math>, <math>P(x)</math>

It should be noted here that most books on logic follow a different convention. The rule is often stated as
:From <math>P(x)</math> deduce
::For all <math>x</math>, <math>P(x)</math>.
where <math>x</math> is an unbound variable in <math>P(x)</math> and subject to restrictions on where <math>x</math> appears elsewhere in the proof. This may be a valid form of reasoning, but it's not the way a proof is normally written in a mathematical context. For one thing, the expression <math>P(x)</math>, since it has an unbound variable, is really a predicate, not a statement. But proofs in mathematics, aside from the occasional imperative such as "Assume ... ," contain only statements. The rule also requires the distinction between bound and unbound variables. But we're avoiding that distinction and focusing on the difference between statements and predicates instead.)

==Example proof==
We now have all the rules of inference needed to proof statements involving universal quantifiers, so let's put them to work with another example. The classical syllogism
:All people are mortal.
:Socrates is a person.
:Therefore Socrates is mortal.
may be restated in our notation as
:For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>).
:<math>P(s)</math>
:Therefore <math>M(s)</math>
where <math>P(x)</math> is the predicate <math>x</math> is a person, <math>M(x)</math> is the predicate <math>x</math>, and <math>s</math> is the constant Socrates. This is supposed to be a syllogism, in other words the conclusion is supposed to be valid for any <math>P</math>, <math>M</math> and <math>s</math>, as long as the first two statements are valid. This amounts to

:'''Proposition''': For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>) and <math>P(s)</math> implies <math>M(s)</math>

This is an implication, so start with the standard outline for a direct proof.

It's probably a good idea to break up the 'and' into separate statements.

{| class="wikitable" style="text-align: left"
!Line
!Statement
!Justification
|-
|1
|style="padding-left: 2em;" | For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>) and <math>P(s)</math>
|Hypothesis
|-
|2
|style="padding-left: 2em;" | For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>)
|From 1
|-
|3
|style="padding-left: 2em;" | <math>P(s)</math>
|From 1
|-
| colspan=3 | (''something'')
|-
|''n''
|style="padding-left: 2em;" | <math>M(s)</math>
|?
|-
|''n''+1
| For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>) and <math>P(s)</math> implies <math>M(s)</math>
|From 1 and ''n''
|}

We have <math>P(s)</math> and need to derive <math>M(s)</math>, so something like <math>P(s)</math> implies <math>M(s)</math> will do the trick. But we can get that by applying s to the universal quantifier. Filling in the details gives:
{| class="wikitable" style="text-align: left"
!Line
!Statement
!Justification
|-
|1
|style="padding-left: 2em;" | For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>) and <math>P(s)</math>
|Hypothesis
|-
|2
|style="padding-left: 2em;" | For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>)
|From 1
|-
|3
|style="padding-left: 2em;" | <math>P(s)</math>
|From 1
|-
|4
|style="padding-left: 2em;" | <math>P(s)</math> implies <math>M(s)</math>
|From 2
|-
|5
|style="padding-left: 2em;" | <math>M(s)</math>
|From 2 and 4
|-
|6
| For all <math>x</math>, (<math>P(x)</math> implies <math>M(x)</math>) and <math>P(s)</math> implies <math>M(s)</math>
|From 1 and 5
|}

==Translating categorical propositions==
Historically, logic dealt with categorical propositions; these are statements that relate two predicates in specific ways. There are four types:
:All P are Q.
:No P are Q.
:Some P are Q.
:Some P are not Q.
The first type, which we've already seen in the previous section, becomes
:For all <math>x</math>, (<math>P(x)</math> implies <math>Q(x)</math>).
in our notation. The second type may be rephrased as
:All P are not Q.
So in our notation it becomes
:For all <math>x</math>, (<math>P(x)</math> implies not <math>Q(x)</math>).
Note that we have from propositional logic
:<math>P(a)</math> implies not <math>Q(a)</math> iff <math>Q(a)</math> implies not <math>P(a)</math>.
We leave it as an exercise to prove
:No P are Q iff No Q are P.

Now think about what it would mean for the first type
:All P are Q.
to be False. There would need to be some object which is a P but not a Q. In other words, the statement of the fourth type
:Some P are not Q.
would have to be True. On the other hand, if
:Some P are not Q.
is False, then there are no P which are not Q, or put another way,
:All P are Q.
So the fourth statement
:Some P are not Q.
can be translated as
:Not (all P are Q).
or
:Not (for all <math>x</math>, (<math>P(x)</math> implies <math>Q(x)</math>)).
Similarly, the third statement
:Some P are Q.
Can be translated as
:Not (no P are Q).
or
:Not (for all <math>x</math>, (<math>P(x)</math> implies not <math>Q(x)</math>)).

We'll introduce another quantifier in the next page which will make these expressions more tractable. In the mean time, we leave it as an exercise to translate two of the categorical syllogisms
:All P are Q.
:All Q are R.
:Therefore all P are R.
and
:All P are Q.
:No R are Q.
:Therefore No P are R.
into our notation and prove them using the rules of inference we've given up to now.

You may have noticed that results our attempts to translate categorical propositions to our notation have been both more verbose and less like natural language than the originals. So you might well wonder what is the advantage of our notation. One advantage is that our notation is expressive enough to include all mathematical statements while categorical propositions alone are too restrictive. Secondly, the categorical syllogisms do not cover all the valid forms of reasoning which are needed to prove theorems. Consider
:All triangles and rectangles are rectilinear figures.
:All squares are rectangles with all sides equal.
:Therefore all squares are rectilinear figures.
This seems to be a valid syllogism, but since the premises both involve three predicates instead of two, it's not one of the categorical syllogisms. In addition, categorical propositions deal only with predicates and not relations, and it would be impossible to do much mathematics with predicates only.

Proofs:Quantifiers - Revision history

Lila at 21:12, 28 September 2021

Lila: Created page with "==Proving a statement with a universal quantifier== To prove a statement of the form :For all x, P(x) first ask the reader to pick an arbitrary const..."

Lila: Created page with "==Proving a statement with a universal quantifier== To prove a statement of the form :For all $x$ , $P(x)$ first ask the reader to pick an arbitrary const..."