# Quantifiers and equivalence

1. Philosophy Forum
2. » Logic
3. » Quantifiers and equivalence

Sun 16 May, 2010 07:15 am
Rules of passage are given in FOPL for the operators (v, &, ->) but not
for (<->).

Ex means (some x) and Ax means (all x).

i.e.
Ax(Fx v p) <-> (AxFx v p), Ex(Fx v p) <-> (ExFx v p).

Ax(Fx & p) <-> (AxFx & p), Ex(Fx & p) <-> (ExFx & p).

Ax(Fx -> p) <-> (ExFx -> p), Ax(p -> Fx) <-> (p -> AxFx).

Ex(Fx -> p) <-> (AxFx -> p), Ex(p -> Fx) <-> (p -> ExFx).

Dr. W. V. Quine in his METHODS OF LOGIC (1982) claims that there are no
rules of passage for equivalence see exercise 2, page 148.

Quine:
"Exercise 2. There are no rules of passage for '<->' ..."

Contradicting Dr. Quine, I give the following theorems (rules of passage for equivalence).

1. Ax(Fx <-> p) <-> ((p -> AxFx) & (ExFx -> p)).

2. Ex(Fx <-> p) <-> ((AxFx -> p) & (p -> ExFx)).

3. (AxFx <-> p) <-> AyEx((Fx -> p) & (p -> Fy)).

4. (ExFx <-> p) <-> AyEx((Fy -> p) & (p -> Fx)).

Each of these theorems is verified by first setting p true and reducing,
then setting p false and reducing.

"The rules of passage work in either of two directions: to widen the
scope of a quantifier or to narrow it. The one direction ends by
bringing the formula into prenex form, where all quantifiers stand in a
an initial row governing the rest of the formula. The other direction
ends by purifying the formula, by causing the scope of each quantifier
to be a truth function only of components each of which shows free
occurrences of the variable of the quantifier." Quine, Methods of Logic
(1982),
page 148 chapter 24 PRENEXITY AND PURITY.

Any opinions ?

jack phil

Mon 17 May, 2010 01:42 pm
@Owen phil,
I find the sign of equality beautiful.

So, 3 = 1 + 1 + 1? Or can more be done to simplify the symbolism?

Is the latter quote from Quine metaphysical in your view?

step314 phil

Sun 23 May, 2010 08:40 pm
@jack phil,
Perhaps Quine doesn't consider your rules rules of passage per se in that what you end up with isn't an equivalence with a (possibly different) quantifier that has passed inside--it's not a simple rule that just involves merely "passing" the quantifier inside and then maybe changing the quantifier (while leaving the logical operator alone). It is a very well-known theorem that every first-order formula (even equivalences) is equivalent to one in prenex normal form; as for the reverse direction, well, I have seen less arguments needing to go that direction. I must admit your rule (2)

Quote:
2. Ex(Fx <-> p) <-> ((AxFx -> p) & (p -> ExFx)).
though right is not something I recall seeing or thinking about before; it is interesting enough that perhaps it should be taught more. If one were interested in a formula with no quantifier binding more than one instance of a variable, and wanted to get an equivalent formula with all the quantifiers pushed in next to the function symbol involving that variable, your rules would be useful, showing the method would work even with formulas involving equivalences.

Let "<" denote "entails" (or implication if you don't know the difference), "\x/" denote "exists an x" and "/x\" denote "for all x". An interesting observation about the prenex rules (the phrase "rules of passage" annoys me) for implication concerns B -> \x/ C < \x/ (B -> C) and /x\ B -> C < \x/(B -> C). Breaking the implication prenex rules into their eight separate parts, these two parts are the only difficult ones to prove (assuming reasonable axioms of logic chosen to make the axioms of logic analogous to the natural ones of a lattice), requiring one to consider exactly what truth values there are, and yet they are the only parts that hold regardless of what formulas are substituted for B and C--no need to worry in these two parts about what variables are free where, etc.

Since the forward part of your rule (2) is trivial, what you did that was interesting (the backwards direction of your rule (2)) was to combine the two interesting parts of the prenex rules for implication into one rule; but maybe it isn't so great after all since unlike the two interesting parts, it really needs p to not involve x. E.g., if Fx is x = 0, then changing p to ~ x = 0 makes rule fail.

Owen phil

Mon 24 May, 2010 01:56 pm
@step314 phil,
step314;167884 wrote:
Perhaps Quine doesn't consider your rules rules of passage per se in that what you end up with isn't an equivalence with a (possibly different) quantifier that has passed inside--it's not a simple rule that just involves merely "passing" the quantifier inside and then maybe changing the quantifier (while leaving the logical operator alone). It is a very well-known theorem that every first-order formula (even equivalences) is equivalent to one in prenex normal form; as for the reverse direction, well, I have seen less arguments needing to go that direction. I must admit your rule (2)

though right is not something I recall seeing or thinking about before; it is interesting enough that perhaps it should be taught more. If one were interested in a formula with no quantifier binding more than one instance of a variable, and wanted to get an equivalent formula with all the quantifiers pushed in next to the function symbol involving that variable, your rules would be useful, showing the method would work even with formulas involving equivalences.

Let "<" denote "entails" (or implication if you don't know the difference), "\x/" denote "exists an x" and "/x\" denote "for all x". An interesting observation about the prenex rules (the phrase "rules of passage" annoys me) for implication concerns B -> \x/ C < \x/ (B -> C) and /x\ B -> C < \x/(B -> C). Breaking the implication prenex rules into their eight separate parts, these two parts are the only difficult ones to prove (assuming reasonable axioms of logic chosen to make the axioms of logic analogous to the natural ones of a lattice), requiring one to consider exactly what truth values there are, and yet they are the only parts that hold regardless of what formulas are substituted for B and C--no need to worry in these two parts about what variables are free where, etc.

Since the forward part of your rule (2) is trivial, what you did that was interesting (the backwards direction of your rule (2)) was to combine the two interesting parts of the prenex rules for implication into one rule; but maybe it isn't so great after all since unlike the two interesting parts, it really needs p to not involve x. E.g., if Fx is x = 0, then changing p to ~ x = 0 makes rule fail.

I think these rules for equivalence should be added to the list just to complete the list of rules of passage.

All of these theorems assume that p has no free x.

We cannot substitute ~x = 0 for p.

1. Philosophy Forum
2. » Logic
3. » Quantifiers and equivalence