The question in my text is :

Identify the error or errors in this argument that supposedly shows that if $\forall x (P (x ) \lor Q(x ))$ is true then $\forall x P(x) \lor \forall x Q(x)$ is true.

\begin{array}{l l l} (1) & \forall x(P (x) \lor Q(x)) & \text{Premise} \\ (2) & P (c) \lor Q(c) & \text{Universal instantiation from }(1) \\ (3) & P (c) & \text{Simplification from }(2) \\ (4) & \forall x P (x ) & \text{Universal generalization from }(3) \\ (5) & Q(c) & \text{Simplification from }(2) \\ (6) & \forall xQ(x) & \text{Universal generalization from }(5) \\ (7) & \forall x(P (x) \lor \forall x Q(x)) & \text{Conjunction from } (4) \text{ and } (6) \end{array} According to me the errors occur at step 3, 5 and step 7. Step 3 because the rule for simplification is $$(p \land q) \rightarrow p$$ and in step 7, it isn't conjunction but addition? Because rule of addition is $$ p \rightarrow (p \lor q)$$ Also step 5 because we can't assume that the $c$ that makes $P$ true is the same $c$ that makes $Q$ true.

Am I right?

  • 1
    $\begingroup$ Step 3 is wrong: we cannot safely infer from the fact that: "either the cat is balck or the cat is red" that "the cat is black". As you correctly noted, simplification holds for conjunction ($\land$). $\endgroup$ – Mauro ALLEGRANZA Jul 6 '17 at 6:47
  • $\begingroup$ ah! thanks for the example. I can now see this is really simple,but I got confused by the question. @MauroALLEGRANZA $\endgroup$ – momo Jul 6 '17 at 6:50
  • $\begingroup$ After step 3 you can use disjunction eliminiation to start a "proof by cases"... but then you cannot "generalize". $\endgroup$ – Mauro ALLEGRANZA Jul 6 '17 at 6:52
  • $\begingroup$ The mistake of step 5 is the same as the one from step 3. $\endgroup$ – 5xum Jul 6 '17 at 7:08
  • $\begingroup$ You are right; step 7 is wrong: "conjunction" rules introduces a conjunction: $\land$. $\endgroup$ – Mauro ALLEGRANZA Jul 6 '17 at 7:53

Depending on how the rules in your formal proof system are defined, steps 4 and 6 could be incorrect as well: when the $c$ is used for the universal instantiation, some formal proof systems consider that to be a specific individual and, as such, you can't apply universal generalization on that. Instead, these systems demand that either $c$ be 'marked' as an arbitrary individual from the domain, or that a temporary subproof structure be used, or that variables be used.

So, how is universal generalization defined? What text are you using?

  • $\begingroup$ I am using the book by Kenneth Rosen. $\endgroup$ – momo Jul 6 '17 at 14:08
  • 2
    $\begingroup$ @momo Hmm, that book, while a great book on Discrete Structures, pays little attention to formal proofs. In it, the Universal Generalization rule is stated as being able to infer $\forall x P(x)$ if you know that $P(c)$, and $c$ is an arbitrary individual. Which all makes sense ... but it is not clear how exactly the 'arbitrariness' of $c$ is formally fleshed out in a formal proof. However, looking at the answer in the back of the book of problem 27, it seems like what is happening in lines 4 and 6 of your 'proof' is in fact formally correct. $\endgroup$ – Bram28 Jul 6 '17 at 14:40
  • $\begingroup$ As Bram28 said, I don't recommend you study logic by that book. It leads you to wrong direction, and useless knowledge in modern logic.... That book didn't pay attention on the semantics and syntax nature of logic, and messed up the object language and meta-language. You will totally be frustrated if you want to study logic rigoursly in the future. I was a victim by beginning studying logic by that book..., but safe from study Robert Causey's Logic, Sets and Recursion. :) $\endgroup$ – Eric Jul 15 '17 at 5:22

You're correct, but your objection to step 7 is more about nomenclature (and cosmetics) which may differ somewhat. The step is otherwise correct since if we have $p$ then we can conclude $p\lor q$ (however we actually don't need to prove $q$ too for this step).

Also the instantiation means that you pick a specific $c$ from which you can't generalize later. However there are formalizations where one can do something similar (in which case $c$ isn't considered specific, but general).

I think the last comment is the most important and somewhat captures why the conclusion is not correct. It's about that in the first statement the variable $x$ work in unison in both $P$ and $Q$ while in the last they work independly (that is the last is the same as $\forall x\forall y(P(x)\lor Q(y))$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.