# Quantifier Help

• Apr 11th 2010, 05:02 PM
rogernorth
Quantifier Help
Currently in my logic class we are learning about quantifiers, and I have a question that our book doesn't fully explain.

It says that if you have a formula like:

for all x : (f x)

then you can prove it by simply proving:

(f x)

but it then says that they are not propositional equivalent, and I do not understand why they are not propositional equivalent. If someone could explain why that would be great.
Thanks
• Apr 12th 2010, 12:47 AM
emakarov
Quote:

It says that if you have a formula like:

for all x : (f x)

then you can prove it by simply proving:

(f x)
Yes, but with an important condition: the variable "x" must be "fresh", i.e., not used in the current derivation before. Consider two arguments.

1. "Every man has two parents. Indeed, take any man; let's call him Joe. Then ... " This is the beginning of a proper logical argument.

2. "Every man is a drunkard. Indeed, take our neighbor Joe. ..." This is more like old wives' tales.

So, to prove $\forall x.\, P(x)$ the typical way is to introduce a fresh $x$ and prove $P(x)$. After that, the $x$ that was introduced, disappears.

Quote:

but it then says that they are not propositional equivalent
They are not propositional equivalent, first, because (f x) is not a proposition since it has a free variable x. The truth value of (f x) depends on x.

Now, thinking about this a bit more, I would say that they are not propositional equivalent because they can't be proved equivalent using propositional rules. One can prove $\forall x.\,P(x)$ from $P(x)$, but only by eliminating $x$ from the discourse and only if $x$ was fresh. This inference rule is from first-order, not propositional, logic.
• Apr 12th 2010, 07:39 AM
MoeBlee
One way to summarize the situation is this:

For any formula 'F' and any variable 'x' we have
|- AxFx -> Fx.

It is not the case that for any formula 'F' and any variable 'x' we have
|- F -> AxFx.
Counterexample:
Let 'F' be 'x=y'. In the model of natural numbers, assign 0 to 'x' and 0 to 'y'. Then x=y is true, but Ax x=y is not true, since it is not true that every natural number is 0.

However, for any formula 'F' and any variable 'x' we have
|- F iff |- AxF.