Results 1 to 4 of 4

Math Help - Like below: Natural Deduction for Predicate Calculus

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    Setagaya-ku, Tokyo-shi, Japan
    Posts
    4

    Like below: Natural Deduction for Predicate Calculus

    Hi, I've been practising predicate calculus I am struggling with this question and as I have seen below it would be good if the response is in Fitch-style. Thank you very much.

    It is proving:

    (∀x. P(x)) -> (∀y. P(y))

    I know that this involves generalisation etc. but I am quite sure about how to do it (probably assuming a ? if a is one of the x's)

    As far as I know, I've learnt Universal and existential instantiation, universal and existential generalisation (and probably natural deduction rule in predicate logic).

    Thank you very much for your support!

    Regards

    Sekaiyoma
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Like below: Natural Deduction for Predicate Calculus

    Code:
    1. ∀x. P(x)			Assumption
    2.   P(y)			∀E
    3.   ∀y. P(y)			∀I
    4. (∀x. P(x)) -> ∀y. P(y)	->I
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    Setagaya-ku, Tokyo-shi, Japan
    Posts
    4

    Re: Like below: Natural Deduction for Predicate Calculus

    Thanks for your response. I would like to ask you one more thing. The question says that provide or provide a counterexample for the following statement ((p-> q) -> p) -> p and I have constructed truth table and it results in tautology. In this case, did I prove the statement? If there is one False, then is that a counterexample?

    I don't know because the question says 'clearly indicate whether the statement has a proof or a counterexample' and I am not too sure what does it mean by 'clearly indicating'
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Like below: Natural Deduction for Predicate Calculus

    Quote Originally Posted by sekaiyoma View Post
    Thanks for your response. I would like to ask you one more thing. The question says that provide or provide a counterexample for the following statement ((p-> q) -> p) -> p and I have constructed truth table and it results in tautology. In this case, did I prove the statement? If there is one False, then is that a counterexample?
    This formula is known as Peirce's law and, yes, it is a tautology. A counterexample would be some truth values of p and q under which the formula's truth value is false. Here, of course, there is no counterexample.

    Quote Originally Posted by sekaiyoma View Post
    I don't know because the question says 'clearly indicate whether the statement has a proof or a counterexample' and I am not too sure what does it mean by 'clearly indicating'
    The word "proof" has several meanings. One can construct a derivation of Peirce's law in natural deduction. (It's a little tricky and involves the law of double-negation elimination.) This would be an object-level proof. The object level consists of the objects we study in mathematics. In this case, we study propositions and their derivations, which are syntactic objects built according to certain well-defined rules. I prefer calling object-level proofs derivations.

    The other level is called metalevel. Proofs in metalevel are regular mathematical proofs about objects from the object level. These proofs are usually written in English and may have different level of detail. For example, the completeness theorem, which says that every tautology has an object-level derivation, is a metalevel theorem.

    By checking the truth table for Peirce's law you constructed a metalevel proof that the formula is valid (a tautology). However, this is different from constructing an object-level natural deduction derivation. Which meaning of "proof" is intended by the question depends on the course, instructor and textbook.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Natural Deduction problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 6th 2012, 05:14 AM
  2. natural deduction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 12th 2011, 08:31 AM
  3. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2011, 03:15 AM
  4. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 11:47 AM
  5. Help with Logic (Natural Deduction)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 12th 2010, 02:07 PM

Search Tags


/mathhelpforum @mathhelpforum