# Proving an implication by proving its dual

My textbook "Discrete and Combinatorial Mathematics, an Applied Introduction" by Ralph P. Grimaldi contains the following definition:

Let $s$ be a statement. If $s$ contains no logical connectives other than $\wedge$ and $\vee$, then the dual of $s$, denoted $s^d$, is the statement obtained from $s$ by replacing each occurrence of $\wedge$ and $\vee$ by $\vee$ and $\wedge$, respectively, and each occurrence of $T_0$ and $F_0$ by $F_0$ and $T_0$, respectively.

(I apologize for not knowing the formatting conventions here)

and the following theorem:

The Principle of Duality . Let $s$ and $t$ be statements that contain no logical connectives other than $\wedge$ and $\vee$. If $s \leftrightarrow t$, then $s^d \leftrightarrow t^d$.

Is anyone familiar with these? Can I use them to reason as follows:

2. take its dual
3. manipulate the dual
4. arrive at the dual of our conclusion
5. take its dual

This would allow me to do something like:

to prove that $\forall x\ P(x)\vee \forall\ Q(x) \rightarrow \forall x\ [P(x)\vee Q(x)]$

1. Ax,P(x) V Ax,Q(x)  premise
2. Ax,P(x) ^ Ax,Q(x)  the dual of (1)
3. Ax,P(x)            conjunctive simplification
4. P(c)               universal specification
5. Ax,Q(x)            conjunctive simplification from (2)
6. Q(c)               universal specification
7. P(c) ^ Q(c)        rule of conjunction from (4) and (6)
8. Ax[P(x) ^ Q(x)]    universal generalization
9. Ax[P(x) V Q(x)]    the dual of (8)


When I wrote this proof I didn't know that you could use universal specification to go from (1) to the dual of (7), so I needed a way to separate (1) into two parts. Taking the dual seemed to be a thing I can do. I worry though, because it seems like I could prove the converse this way, and the converse is false.

So what's wrong? Why can't I use the concept of the dual of a statement in this way?

Thanks everyone!

a.

PS oh and I solved the question in another way, so this is just my curiosity. PPS thank you for being patient with my ugly post, I'll try to learn your mark up.

-
Would you like to share your answer? – draks ... Jun 25 '12 at 19:21
Someone told me the next day that it is OK to go from Ax,P(x) V Ax,Q(x) to P(c) V Q(c) by universal specification. From there I generalized to Ax[P(x) V Q(x)]. But I want to know about the dual of a statement, and whether its OK to use it to reason like I have above. – Ziggy Jun 25 '12 at 19:24

Your steps (1)-(2) and (8)-(9) don't work. The dual is defined in your quote only under the condition

If $s$ contains no logical connectives other than $\land$ and $\lor$,

but here you also have quantifiers appearing in addition to $\land$ and $\lor$, and then the definition does not apply as written.

The principle behind the dual is that instead of the the formula $\phi(A,B,C,\ldots)$ where $A$, $B$, $C$ are propositional variables, you look at $\neg\phi(\neg A,\neg B,\neg C)$ and then use De Morgan's laws to push the negations down through the formula until they eliminate each other. On the way they change every $\land$ to $\lor$ and vice versa. You can then do some transformations and dualize again, giving you something equivalent to $\neg \neg \phi(\neg \neg A,\neg \neg B, \neg\neg C,\ldots)$, which of course is just $\phi(A,B,C,\ldots)$.

When there are quantifiers involved, you need to handle those using their appropriate De Morgan rules: $$\neg(\forall x\,\phi) \leftrightarrow \exists x\,(\neg \phi) \qquad \qquad \neg(\exists x\,\psi) \leftrightarrow \forall x\,(\neg \psi)$$ so when you dualize $(\forall x\,P(X)) \lor (\forall x\,Q(X))$ you should get $(\exists x\,\bar P(x)) \land (\exists x\,\bar Q(x))$, where $\bar P$ and $\bar Q$ are the duals of $P$ and $Q$.

-
Thanks! That is very clear, and very useful! My proof after that point can still be similar, I think, but with backwards E instead of upside down A, since when I return from the land of duals I will get my Universal back. Woo! – Ziggy Jun 25 '12 at 20:51
More generally, the principle behind the dual comes as that instead of the formula ϕ(A,B,C,…) where A, B, C are propositional variables, you look at &ϕ(&A,&B,&C,…), where & is an isomorphism between the dual structures (S, A), (S', A') where S, S' indicate the sets involved, and A, A' the operations involved, and then one uses the homomorphism laws (De Morgan's laws come as a special case where negation comes as the isomorphism) for the isomorphism & to push the &'s down until they eliminate each other. Conjunction-disjunction duality holds, because negation is an isomorphism. – Doug Spoonwood Jun 26 '12 at 0:08