Results 1 to 5 of 5

Math Help - Quantifier Proofs

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    6

    Quantifier Proofs

    x
    Last edited by chebyshev1; August 17th 2010 at 11:57 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm not so sure you're being as accurate as you might be. Check out the prenex normal form wiki to double-check your parentheses manipulation.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    I am not sure I can help here because I don't know what type of proof you are looking for.

    In mathematical logic, there is a distinction between syntax and semantics. Syntax specifies which strings of characters are well-formed formulas and how to derive new formulas from old ones. It is relatively straightforward to encode syntax into a computer. In the end, it is just string manipulation subject to precise rules.

    Semantics, on the other hand, is about meaning and truth/falsity of formulas. For example, a theorem from calculus can be written as a finite string that a computer can manipulate, but its meaning may involve real numbers, which is a (very) infinite set that cannot fit inside a computer.

    If you are looking for a syntactic proof, then you must work with precise inference rules. Saying which formal system you are using is essential in order to get help because there are dozens of such systems, similar to how there are dozens of programming languages. If one asks for help with writing a program but does not specify the programming language, then the most he/she can get is some informal pseudocode.

    This formula is known as the "Drinker's paradox". If one interprets the domain as the set of people in a bar and P(x) as "x drinks", then the formula claims that there is a person such that if he/she drinks, then everybody does. (It is called a paradox because at first glance it is surprising that every bar has such a "leader".) So the semantical proof of the formula goes like this. Either there is a person that does not drink, or there isn't. If x does not drink, then take him/her as the witness of ∃x. Indeed, P(x) is false and therefore the implication is true. If, on the other hand, there are no non-drinking people, then everybody drinks. In this case, take any person as x; the conclusion of the implication is true, and so the whole implication is.

    I have the following proof to solve with 0-premises.
    It is not correct to say "solve a proof". One can solve a problem or come up with a proof. By the way, what does "with 0-premises" mean?

    Which is otherwise written as

    ∃xP(x) v ∃x∀yP(y)
    This formula is indeed semantically equivalent to the original one. However, if you are looking for a syntactic proof, you can't just shift from one to the other. Imagine that you need to explain to a dumb computer, who knows only primitive inference rules, how you do the transition.

    Also, in studying first-order logic, one usually assumes that domains are non-empty. In this case, ∃x∀yP(y) is semantically equivalent to ∀yP(y). Indeed, x does not occur (freely) in ∀yP(y), so one can instantiate it with any domain element.

    So I would start by assuming its negation and use the instance of excluded middle
    ∃xP(x) v ∃x∀yP(y)
    This is not an instance of the excluded middle. Both disjuncts here are semantically equivalent to ∀yP(y).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by chebyshev1 View Post
    I have the following proof to solve with 0-premises.

    ∃x(P(x) → ∀y(P(y))

    Which is otherwise written as

    ∃xP(x) v ∃x∀yP(y)
    They'r equivalent because they're both logical theorems anyway.

    Show Ex(Px -> Ay Py):
    Toward a contradiction, suppose ~Ex(Px -> Ay Py).
    So Ax(Px & ~Ay Py).
    So Px & ~Ay Py.
    Since x not free in any premise, we have Ax Px.
    So Ay Py, which contradicts ~Ay Py.

    Show Ex~Px v ExAy Py:

    Suppose ~Ex~Px. Show: ExAy Py.
    Since ~Ex~Px, we have Ax Px.
    So Ay Py.
    So ExAy Py.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    chebyshev1: You appear to have edited the OP. That is against Rule # 7. Please restore the OP.
    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 Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 12th 2010, 07:39 AM
  3. Quantifier Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 20th 2007, 09:48 AM
  4. quantifier
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 28th 2007, 03:14 PM
  5. Predicate and Quantifier
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 17th 2007, 05:49 PM

Search Tags


/mathhelpforum @mathhelpforum