1
$\begingroup$

I'm a high schooler studying logic from a few discrete math books and I wish to show that $\forall x, (P(x) \rightarrow Q(x))$ is logically equivalent to $\forall x, (\neg Q(x) \rightarrow \neg P(x)),$ using universal generalization to show this logical equivalence.

I'm aware that to prove logical equivalence for quantified statements, I have to show that the biconditional between the two quantified statements is a tautology. So I'll have to first show that the conditional statement $$(\forall x, (P(x) \rightarrow Q(x))) \rightarrow (\forall x, (\neg Q(x) \rightarrow \neg P(x)))$$ is a tautology, then show that the converse of it is also a tautology.

But by using universal generalization, I feel like I could skip this and just prove that they're logically equivalent without needing to go through conditional statements but I'm not sure if this is the correct way to do it. Here is how the proof goes:

Suppose that $\forall x, (P(x) \rightarrow Q(x))$ is true, then whenever $P(x)$ is true, $Q(x)$ will also be true. Let $a$ be any arbitrary element from the domain, then $P(a) \rightarrow Q(a)$ is a true conditional statement. Since a conditional statement is logically equivalent to its contrapositive (proved by using truth table for statements), we have $$P(a) \rightarrow Q(a) \equiv \neg Q(a) \rightarrow \neg P(a)$$ And since $a$ was arbitrary, we can use universal generalization to generalize it to $$\forall x, (P(x) \rightarrow Q(x)) \equiv \forall x, (\neg Q(x) \rightarrow \neg P(x))$$

As you can see, I didn't show if the conditional statements were tautologies. Am I using universal generalization correctly here? Does this make my proof correct? If not, how will I need to correct my proof? I'm not so sure if I can use universal generalization to go from $$P(a) \rightarrow Q(a) \equiv \neg Q(a) \rightarrow \neg P(a)$$ to $$\forall x, (P(x) \rightarrow Q(x)) \equiv \forall x, (\neg Q(x) \rightarrow \neg P(x)).$$

I'm using the symbol in the metalanguage sense instead of as the material biconditional. I use the symbol to mean the material biconditional.

$\endgroup$
6
  • $\begingroup$ You have proven that the RHS is a logical consequence of the LHS, but I'm not seeing a proof of the converse. $\quad$ To be clear: $A\equiv B$ isn't asserting that both A and B are true, only that they must have the same truth value. $\endgroup$
    – ryang
    Commented Apr 15, 2023 at 10:42
  • $\begingroup$ @ryang So I didn't show that they're logically equivalent? I thought I did that because at the end, I used universal generalization to show that the LHS is logically equivalent to the RHS.I used universal generalization to show that the LHS is logically equivalent to the RHS. Like instead of showing the converse, I got straight to the logical equivalence. $\endgroup$ Commented Apr 16, 2023 at 4:01
  • $\begingroup$ @ryang because I can use universal generalization on the fact that a conditional is logically equivalent to its contrapositive, like I did there, which got me to immediately showing the logical equivalence. And by doing the same for the converse of the conditional, I'll only show the logical equivalence again... which is just repetition right? $\endgroup$ Commented Apr 16, 2023 at 4:20
  • $\begingroup$ @Mohammadmuazzamali Are you using the symbol to represent logical equivalence in the metalanguage or as the material biconditional? $\endgroup$
    – Nico
    Commented Apr 17, 2023 at 17:28
  • 1
    $\begingroup$ @Mohammadmuazzamali Assumed so, just wanted to make sure. $\endgroup$
    – Nico
    Commented Apr 18, 2023 at 0:01

1 Answer 1

1
$\begingroup$

Suppose that $\forall x\, (P(x) \rightarrow Q(x))$ is true

Let $a$ be any arbitrary element from the domain; then $P(a) \rightarrow Q(a)$

Since a conditional statement is logically equivalent to its contrapositive (proved by using truth table for statements), we have $$P(a) \rightarrow Q(a) \equiv \neg Q(a) \rightarrow \neg P(a)$$

This last line in symbols—which is merely a rephrasing of your explanation preceding it— can be used to derive the tautological consequence $$\neg Q(a) \rightarrow \neg P(a);$$ we then apply Universal Generalisation to derive the required RHS, giving $$\forall x\, (P(x) \rightarrow Q(x)) \vdash \forall x\, (\lnot Q(x) \rightarrow \lnot P(x)).$$

And since $a$ was arbitrary, we can use universal generalization to generalize it to $$\forall x\, (P(x) \rightarrow Q(x)) \equiv \forall x\, (\neg Q(x) \rightarrow \neg P(x))$$

Now, writing neither the metalogical assertion $$P(a) \rightarrow Q(a) \equiv\neg Q(a) \rightarrow \neg P(a)$$ nor the tautological consequence $$(P(a) \rightarrow Q(a)) \leftrightarrow (\neg Q(a) \rightarrow \neg P(a))$$ amounts to asserting that either of the two conditionals is true (i.e., actually deriving either of the two conditionals). Applying Universal Generalisation to the latter gives $$\forall x\, (P(x) \rightarrow Q(x)) \vdash \forall x\,\big( (P(x) \rightarrow Q(x)) \leftrightarrow (\neg Q(x) \rightarrow \neg P(x))\big),$$ which isn't what we want.

I'm not so sure if I can use universal generalization to go from $$P(a) \rightarrow Q(a) \equiv \neg Q(a) \rightarrow \neg P(a)$$ to $$\forall x (P(x) \rightarrow Q(x)) \equiv \forall x (\neg Q(x) \rightarrow \neg P(x)).$$ I'm using the symbol in the metalanguage sense instead of as the material biconditional. I use the symbol to mean the material biconditional.

It doesn't make sense during a sequence of syntactical derivations to suddenly teleport to the metalanguage to apply Universal Generalisation—a syntactical rule that transforms sentences in the object language—there.

Nor does it make sense to claim that Universal Generalisation transforms $$M(a)\leftrightarrow N(a)\tag1$$ to $$\forall x\;M(x)\leftrightarrow \forall x\;N(x),$$ since its rule explicitly says to append the quantifier around the entirety of formula $(1).$

Furthermore (rephrasing my parenthetical comment above), remember, formula $(1)$ does not mean $$M(a)\land N(a);$$ and Universal Generalisation per se does not transform even this formula to $$\forall x\;M(x)\land \forall x\;N(x).$$ P.S. For reference: $$\forall x\;M(x)\land \forall x\;N(x)\quad\equiv\quad \forall x\;\big(M(x)\land N(x)\big)\\ \forall x\;M(x)\leftrightarrow\forall x\;N(x)\quad\not\equiv\quad \forall x\;\big(M(x)\leftrightarrow N(x)\big).$$

$\endgroup$
6
  • $\begingroup$ The question was, "can we get from $(P(a) \to Q(a)) \leftrightarrow (\lnot Q(a) \to \lnot P(a))$ (which is already a tautology of propositional calculus) to $\forall x(P(x) \to Q(x)) \leftrightarrow \forall x(\lnot Q(x) \to \lnot P(x))$?". I understand that applying universal generalization directly to $(P(a) \to Q(a)) \leftrightarrow (\lnot Q(a) \to \lnot P(a))$ won't work, but perhaps you could point the OP in the right direction of how to start deriving $\forall x(P(x) \to Q(x)) \leftrightarrow \forall x(\lnot Q(x) \to \lnot P(x))$ from it? $\endgroup$
    – Nico
    Commented Apr 17, 2023 at 16:42
  • $\begingroup$ @Nicolino The OP's proof began with the assumption ∀x(P(x)→Q(x)); they then thought that they had derived P(a)→Q(a)≡¬Q(a)→¬P(a); I'm pointing out that this line is merely a meta explanation surrounding their proof attempt and a justification (Tautological Consequence) for deriving the useful next line ¬Q(a)→¬P(a); in summary, this half of the proof says ∀x(P(x)→Q(x))⊢∀x(¬Q(x)→¬P(x)). The OP's proof did not actually derive (P(a)→Q(a))↔(¬Q(a)→¬P(a)); this line is actually valid to derive, however, the point is that it's not useful to do so. $\endgroup$
    – ryang
    Commented Apr 17, 2023 at 17:12
  • $\begingroup$ The OP said their goal is to derive ∀x(P(x)→Q(x))↔∀x(¬Q(x)→¬P(x)). I fail to see how your answer gets them there. $\endgroup$
    – Nico
    Commented Apr 17, 2023 at 17:27
  • $\begingroup$ So I believe using generalization to go from $P(a) \rightarrow Q(a) \equiv \neg Q(a) \rightarrow \neg P(a)$ to $\forall x, (P(a) \rightarrow Q(a)) \equiv \forall x, (\neg Q(a) \rightarrow \neg P(a))$ isn't correct, right? As you've shown, universal generalization will only get us to $\forall x, (P(a) \rightarrow Q(a)) \vdash \forall x, (\neg Q(a) \rightarrow \neg P(a))$. Why can't I use universal generalization to get to the logical equivalence $\forall x, (P(a) \rightarrow Q(a)) \equiv \forall x, (\neg Q(a) \rightarrow \neg P(a))$? I understand that I've only shown half of the proof though. $\endgroup$ Commented Apr 17, 2023 at 23:12
  • $\begingroup$ @Nicolino The final sentence of my Answer's middle section points out that deriving ∀x(P(x)→Q(x))↔∀x(¬Q(x)→¬P(x)) (or (P(a)→Q(a))↔(¬Q(a)→¬P(a))) from the OP's proof attempt's starting assumption ∀x(P(x)→Q(x)), which cannot be discharged, is not useful. The OP in fact knows how to legitimately show the validity of ∀x(P(x)→Q(x))↔∀x(¬Q(x)→¬P(x)) (in other words, to show ∀x(P(x)→Q(x))≡∀x(¬Q(x)→¬P(x)), and is asking not how to do so but about their alternative-proof attempt. $\endgroup$
    – ryang
    Commented Apr 18, 2023 at 8:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .