2
$\begingroup$

I am currently a Philosophy student taking a logic course and I am confused about the concept of null quantification. And the LPL textbook, which we are using in class, introduces the idea, but it does not show much beyond basic examples such as the following: $$∀x \,P ⇔ P \text{ or } ∀x\, (P ∨ Q(x)) ⇔ P ∨ ∀x\, Q(x).$$ I can understand both of those examples as they are fairly intuitive, however, in the homework that my teacher assigned, I came across two proofs with the following format:

1st

Premise: $∃x\, (P(x) → Q(a))$

Goal: $∀x\, P(x) → Q(a)$

2nd

Premise: $∀x\, P(x) → Q(a)$

Goal: $∃x\, (P(x) → Q(a))$

I have no idea how to begin filling out the second proof. I did some research online and I found that this proof follows the form $∃x\, (ϕ(x) → ψ) ⇔ ∀x\, ϕ(x) → ψ$ (where $x$ does not occur as a free variable in $ψ$). I have been able to prove the first problem pretty easily in about 7 steps, but I have no idea how to approach the second one.

I know that I will have to prove that $P(x) → Q(a)$ so I can introduce the existential quantifier, but I am lost as to how I can go about doing that. The second problem seems substantially harder than the first problem, am I missing something?

Edit: I am one step away from solving this problem, however, why does my proof for De Morgan's not work? I thought this was the correct usage of the universal signifier intro.

enter image description here

$\endgroup$
7
  • $\begingroup$ Perhaps the following link will be helpful => m.logic-text.eu/3.7.LogicalTransformationInPL.html $\endgroup$
    – Ten O'Four
    Dec 1 '21 at 4:18
  • 1
    $\begingroup$ Yes, the second proof is harder: I used $7$ lines for Proof 1 too, but $14$ lines for Proof 2. $\endgroup$
    – ryang
    Dec 1 '21 at 6:02
  • $\begingroup$ @ryang how did you do it in 14 steps? I am currently on like step 30 and I am not sure if I am getting anywhere. $\endgroup$ Dec 1 '21 at 6:35
  • $\begingroup$ Perhaps show your aforementioned seven or thirty steps? I'm not sure how similar our proof systems are. $\endgroup$
    – ryang
    Dec 1 '21 at 8:14
  • $\begingroup$ @ryang I am using Fitch, and I am not sure how to add pictures to this, I am new to StackExchange. $\endgroup$ Dec 1 '21 at 8:42
4
$\begingroup$

This is a well known result regarding implication during prenex normal form conversion:

these rules require that the variable quantified in one subformula does not appear free in the other subformula.

The rules for removing quantifiers from the antecedent are (note the change of quantifiers):

$(\forall x\phi) \rightarrow \psi$ is equivalent to $\exists x(\phi \rightarrow \psi )$...

So your 2nd direction can be easily shown correct too per above rule. Finally how to rigorously prove such rule? The same reference talks about the idea right above it:

These rules can be derived by rewriting the implication $\phi \rightarrow \psi$ as $\lnot \phi \lor \psi$ and applying the rules for disjunction above.

$\endgroup$

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.