Results 1 to 3 of 3

Math Help - Quantifier Help

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. for all quantifier
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 06:23 PM
  2. Quantifier Project
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 22nd 2011, 01:08 AM
  3. Quantifier question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 7th 2010, 10:45 AM
  4. Quantifier Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 18th 2010, 04:36 AM
  5. quantifier
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 28th 2007, 03:14 PM

Search Tags


/mathhelpforum @mathhelpforum