Thread: 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

Code:

1. ∀x. P(x)			Assumption
2.   P(y)			∀E
3.   ∀y. P(y)			∀I
4. (∀x. P(x)) -> ∀y. P(y)	->I

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'

Originally Posted by sekaiyoma

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.

Originally Posted by sekaiyoma

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.