# General form of a proof that $ab=0 \implies a=0 \lor b=0$

When proving that $ab = 0 \implies a = 0 \,\mbox{ or }\,b = 0$ for members $a$ and $b$ of a field, I used an argument like

1. Suppose $ab = 0$ and $a \ne 0$ ... then $b = 0$.
2. Now suppose $ab = 0$ and $b \ne 0$ ... then $a = 0$.
3. Therefore, if $ab = 0$, then $a = 0$ or $b = 0$.

The general form of that argument would, as far as I can tell, be

$$(p \land \lnot q \to r) \land (p \land \lnot r \to q) \to (p \to q \lor r)$$

Is that general form indeed a valid argument? How can I know for sure? (Is there a "for sure"?)

-
If the elements $a,b$ belong to a field, then the condition is already met, as one of the definitive properties of a field is that a field satisfies all the properties of an integral domain, including that of having no non-zero zero divisors... But I'm sure this isn't what you're looking for ;) – Emily Sep 4 '12 at 19:43
Just to be clear, building on Ed's comment, are you studying algebra or are you studying logic? If you're studying logic, this is fine. If you're studying algebra, but just trying to use logic to solve a problem, you're making things too complicated, as I explain in my answer below. – Graphth Sep 4 '12 at 19:48
@Graphth: I'm studying logic (I think). I just included the algebra to provide motivation for that expression I came up with. – Blue Sep 4 '12 at 19:51
@Blue: Then it looks like what you're looking for is proof systems in formal logic, which is concerned with syntactic manipulation to prove things. There are several different styles of doing this. In simple cases like this most of them are scarcely more enlightening than truth tables, but they become more interesting when you add rules for quantifiers. For a start take a look at Hilbert system, natural deduction, and Sequent calculus on WP. – Henning Makholm Sep 4 '12 at 20:08

There is a brute force method to check whether a logical formula like the one you indicate holds. Namely, make a truth table: http://en.wikipedia.org/wiki/Truth_table. In other words, consider all $8$ possibilities of $p,q,r\in\lbrace T, F\rbrace$.

-
I did that, but I didn't find it very enlightening. Perhaps a proof involving symbolic manipulation of that expression would help me understand more clearly. What symbolic manipulations are valid, and why? – Blue Sep 4 '12 at 19:40
@Blue It may help you to remember identities such as $T \lor F = T$ and $T \to F = F$. So, for instance, when $p,q,r$ are all $T$, $p \lor \lnot q \to r$ simplifies to $T$, and so on, the whole expression eventually simplifying to $T$. – Sean Eberhard Sep 4 '12 at 19:42
Or if you want to verify that the formula holds in a more algebraic way, try replacing every instance of $P \to Q$ with $\lnot P \lor Q$, and using the laws $\lnot(P\lor Q) = \lnot P \land \lnot Q$ and $\lnot(P\land Q) = \lnot P \lor \lnot Q$. – Sean Eberhard Sep 4 '12 at 19:48
You may be interested in en.wikipedia.org/wiki/Rules_of_inference – Sean Eberhard Sep 5 '12 at 16:07

A simpler approach is to argue that if $a\ne 0$, then $a$ has a multiplicative inverse, and $$0_F=a^{-1}0_F=a^{-1}(ab)=(a^{-1}a)b=1_Fb=b\;.$$ (I’m assuming that you’ve already proved that $a0_F=0_F$ for every $a\in F$.) The form of this argument is $$(p\land\lnot q\to r)\to(p\to q\lor r)\;,$$ without the second conjunct on the lefthand side. To check that it’s valid, just look at its truth table:

$$\begin{array}{c|c} p&q&r&p\land\lnot q\to r&p\to q\lor r&(p\land\lnot q\to r)\to(p\to q\lor r)\\ \hline T&T&T&T&T&T\\ T&T&F&T&T&T\\ T&F&T&T&T&T\\ T&F&F&F&F&T\\ F&T&T&T&T&T\\ F&T&F&T&T&T\\ F&F&T&T&T&T\\ F&F&F&T&T&T \end{array}$$

In fact, you can see that more is true:

$$(p\land\lnot q\to r)\leftrightarrow(p\to q\lor r)\;.$$

-

Hint $\$ Your first step suffices: $\rm\: p\to q\lor r\, \equiv\, \lnot p\lor q\lor r \,\equiv\, \lnot (p\land \lnot q)\lor r\,\equiv\, p\land \lnot q\to r$

-

Yes, it is valid. You could use a truth table.

Note that $p \land \lnot q \to r$ is equivalent to $\lnot (p \land \lnot q \land \lnot r)$, and thus to $\lnot(p \land \lnot (q \lor r))$, which is equivalent to $p \to (q \lor r)$. Thus $(p \land \lnot q \to r) \to (p \to (q \lor r))$, so $$(p \land \lnot q \to r) \land (p \land \lnot r \to q) \to (p \land \lnot q \to r) \to (p \to (q \lor r))$$

-

What really needs to be proved is that a field does not have zero divisors. That follows from field, by definition, containing the inverses of all of its elements other than 0. I understand that you are asking about logic, but a proof about algebra has to stand on algebra.

-

This is valid, but much more complicated than you need. You already took care of the only part that takes any work in your step 1.

Suppose $ab = 0$ and $a \neq 0$ ... then $b = 0$.

Otherwise, if it is not true that $a \neq 0$, then $a = 0$. So, in either case ($a \neq 0$ or $a = 0$), at least one of $a$ and $b$ is 0. I might write out the argument starting by saying "If $a = 0$, then we are finished. So, assume $a \neq 0$." Now, do the steps to get $b = 0$.

Or, another way to think about why you don't need your Step 2, by commutativity and relabeling, it is exactly the same as your Step 1.

-

We can easily prove that the formula is a tautology. Let's replace the inner implications using the equivalence $a\rightarrow b \equiv \lnot a \lor b$. Then we get $$(\lnot(p\land\lnot q)\rightarrow p)\land(\lnot(p\land\lnot r)\rightarrow q)\rightarrow(\lnot p\lor q\lor r)$$ and after applying De-Morgan rules $$(\lnot p \lor q \lor r)\land(\lnot p\lor r\lor q)\rightarrow (\lnot p\lor q\lor r)$$ Now we see that both the antecedents and the consequent are the same. So since $(a\land a)\rightarrow a$ is equivalent to $a\rightarrow a$ and it's true for any $a$, the original formula is also true.

-

The principle you want is valid. Here is a natural deduction / sequent calculus proof of $$(p \land \lnot q) \to r \vdash p \to (q \lor r)$$ in classical logic.

1. We invoke the law of excluded middle: $$\vdash q \lor \lnot q$$

2. By conjunction introduction and modus ponens, $$(p \land \lnot q) \to r, p, \lnot q \dashv r$$ and by disjunction introduction, $$(p \land \lnot q) \to r, p, \lnot q \vdash q \lor r$$

3. By identity and disjunction introduction, $$(p \land \lnot q) \to r, p, q \vdash q \lor r$$

4. By disjunction elimination, $$(p \land \lnot q) \to r, p \vdash q \lor r$$ and by conditional proof, $$(p \land \lnot q) \to r \vdash p \to (q \lor r)$$ as required.

Amusingly, the converse $$p \to (q \lor r) \vdash (p \land \lnot q) \to r$$ is true even in intuitionistic logic. Indeed:

1. By conjunction elimination and modus ponens, $$p \to (q \lor r), p \land \lnot q \vdash q \lor r$$

2. By conjunction elimination and identity, $$p \to (q \lor r), p \land \lnot q \vdash \lnot q$$ so by modus ponens, $$p \to (q \lor r), p \land \lnot q, q \vdash \bot$$ but ex falso quodlibet, so: $$p \to (q \lor r), p \land \lnot q, q \vdash r$$

3. By identity, $$p \to (q \lor r), p \land \lnot q, r \vdash r$$

4. By disjunction elimination, $$p \to (q \lor r), p \land \lnot q \vdash r$$ whence, by conditional proof, $$p \to (q \lor r) \vdash (p \land \lnot q) \to r$$ as claimed.

-