Side-stepping contradiction in the proof of ; ab = 0 then a or b is 0.

Suppose we need to show a field has no zero divisors - that is prove the title - then we head off exactly like the one common argument in the reals (unsurprisingly as they themselves are a field).

What I want to know is; how do we prove this not by contradiction?

I was talking to some philosophers about - again not so surprising - logic and they seemed to have an issue with argument by contradiction. I admit I'm not a huge fan (of it) myself, though the gist of it was that classical logic (where contradiction / law of excluded middle is valid) is a really, really, really strong form of logic; a much weaker type of logic is something called intuitist (?) logic (I only caught the name) but they said it did not hold here.

Now, if we take something like the field axioms - or the reals (e.g. order in the bag...) - how can we prove in this new logic that there are no zero divisors. Or, more precisely how can we avoid contradiction?

-
I guess I should also include; can we prove that contradiction is necessary for a method of proof? I'll be the first to admit I know no formal logic - in fact, if you have some useful texts feel free to include them in the comments. – Adam Dec 31 '11 at 2:26
Intuitionist Logic does not allow proof by contradiction. But there are many things which cannot be established if this method is thrown out. – Bill Cook Dec 31 '11 at 2:29
What exactly is the argument by contradiction in this case? I think the usual argument is: Suppose $ab=0$. If $a=0$ we are done. If $a\ne0$, then it has an inverse $a^{-1}$. Then $b=a^{-1}(ab)=a^{-1}0=0$. But perhaps you just mean excluded middle in this example? – Andrés E. Caicedo Dec 31 '11 at 2:32
I admit I don't really know much logic but I always thought contradiction and excluded middle were equivalent methods. Do you think logic is reasonable to learn for mathematics? My interest was slightly peaked when I thought about not using contradiction or exc. mid. but I'm unsure if it will be dull or interesting / useful. – Adam Dec 31 '11 at 2:39
@Adam: The law of excluded middle and the principle of double negation elimination are equivalent, in the context of intuitionistic logic. What people usually mean by proof by contradiction is a proof of $p \to q$ via a proof of $p \land \lnot q \to \bot$. This is a valid principle if and only if double negation elimination is valid. Regarding your original question: you need to give an explicit axiomatisation of the theory of fields, as there are (infinitely many!) intuitionistically inequivalent axiomatisations which are classically equivalent. – Zhen Lin Dec 31 '11 at 4:23

Let me expand on my comments. Suppose we have a structure with two constants $0$ and $1$, one unary operation $-$ and two binary operations $+$ and $\times$ satisfying

1. $0 + x = x + 0 = x$
2. $x + (y + z) = (x + y) + z$
3. $x + (-x) = (-x) + x = 0$
4. $x + y = y + x$
5. $1 \times x = x \times 1 = x$
6. $x \times (y \times z) = (x \times y) \times z$
7. $x \times y = y \times x$
8. $x \times (y + z) = x \times y + x \times z$
9. $(x + y) \times z = x \times z + y \times z$
10. $0 \ne 1$
11. $(x = 0) \lor \exists y . (x \times y = 1)$

A model of this theory is what some people call a discrete field. It is easy enough to prove that discrete fields have no non-trivial zero divisors: indeed, if $x \times y = 0$, then by (11) either $y = 0$ or there is a $z$ such that $y \times z = 1$; but if there is such a $z$, then $0 = 0 \times z = x \times y \times z = x \times 1 = x$, so $$(x \times y = 0) \implies ((x = 0) \lor (y = 0))$$ as required. This deduction does not make use of the law of excluded middle and is valid intuitionistically.

Unfortunately, the theory of discrete fields is somewhat unsatisfactory. Firstly, axiom 10 is somewhat unnatural: the usual axiom is $$(x \ne 0) \implies \exists y. (x \times y = 1)$$ which is intuitionistically strictly weaker than axiom 11. (Morally, this is because intuitionistic logic has the disjunction property.) If we had adopted this axiom instead, it would not be possible to prove the non-existence of non-trivial zero divisors.

Secondly, I think you will agree with me that however we axiomatise the theory of fields, we had better axiomatise it in such a way that a model of the Dedekind real numbers is a model for the theory of fields. However, one can easily produce models of the intuitionistic theory of Dedekind real numbers which are not discrete fields, by the following theorem:

Theorem. Let $X$ be a topological space. A model of the theory of Dedekind real numbers in the internal logic of the sheaf topos $\textrm{Sh}(X)$ is isomorphic to the sheaf of continuous real-valued functions on $X$.

Proof. See Sheaves in Geometry and Logic [Ch. VI, §8, Theorem 2].

So let us consider the space $X = [-1, 1]$. Let $\mathscr{O}_X$ be the sheaf of continuous real-valued functions on $X$. We have a continuous map $i : \{ 0 \} \hookrightarrow X$, and by general sheaf theory we know that the inverse image sheaf $i^* \mathscr{O}_X$ is just the local ring of germs of continuous functions at $0$ in $X$. The inverse image functor $i^* : \textrm{Sh}(X) \to \textrm{Sh}(\{ 0 \})$ preserves the interpretation of geometric formulae, and the theory of discrete fields is geometric, so if $\mathscr{O}_X$ were a discrete field, so would $i^* \mathscr{O}_X$. But a sheaf on a point is just a set, so the internal logic of $\textrm{Sh}(\{ 0 \})$ is classical, and $i^* \mathscr{O}_X$ is not a field: the germ of, say, $x \mapsto x^2$ is not invertible in $i^* \mathscr{O}_X$, yet is not zero either. So $\mathscr{O}_X$ could not have been a discrete field to begin with.

So is there an intuitionistic theory of fields which does admit the Dedekind real numbers as a model? It turns out we should add a binary relation $\newcommand{\hash}{\mathrel{\#}}$ $\hash$, called a tight apartness relation, satisfying the axioms one would expect for inequality $\ne$:

• $\lnot (x \hash x)$
• $(x \hash y) \implies (y \hash x)$
• $(x \hash z) \implies (x \hash y \lor y \hash z)$
• $\lnot (x \hash y) \implies (x = y)$

Then, if we replace axioms 10 and 11 above by the axioms

• $(x \hash y) \Longleftrightarrow \exists z . (x \times z = y \times z + 1)$

we obtain the theory of Heyting fields. In words, $x \hash y$ precisely when $x - y$ is invertible. It turns out that a model of the Dedekind real numbers is indeed a Heyting field, and the intuition here is that $x \hash y$ when $x$ and $y$ are functions such that $x - y$ is nowhere zero: thus, the graphs of $x$ and $y$ do not intersect anywhere if $x \hash y$. (Hence the name ‘apartness relation’.) (One may object that just because $x - y$ is somewhere zero doesn't mean $x = y$, but the interpretation of $\lnot$ is quite subtle in this context and $\lnot (x \hash y)$ turns out to mean exactly that $x = y$.)

Specialising the Heyting field axiom above, we obtain $$(x \hash 0) \Longleftrightarrow \exists y . (x \times y = 1)$$ and so by contraposition we have $$\nexists y . (x \times y = 1) \implies \lnot (x \hash 0)$$ but $\lnot (x \hash 0) \implies x = 0$, so $$\nexists y . (x \times y = 1) \implies x = 0$$ exactly as in the classical theory of fields. Moreover, since $$1 \times 1 = 0 \times 1 + 1$$ we must have $1 \hash 0$.

Now, let us turn our attention to zero divisors. It seems there is an unavoidable tradeoff: now that we've allowed the Dedekind real numbers to be a field, we must allow fields to have zero divisors. Indeed, consider the function $f : [-1, 1] \to \mathbb{R}$ $$f(x) = \begin{cases} 0 & x \le 0 \\ \exp (-1 / x^2) & x > 0 \end{cases}$$ This is continuous (and even smooth!), but if we set $g(x) = f(-x)$, then $f(x) g(x) = 0$ for all $x$. Yet, for all open covers $\{ U_i \}$ of $X = [-1, 1]$, there must be a neighbourhood $U$ of $0$ such that $$f|_U \ne 0 \text{ and } g|_U \ne 0$$ so thus $$X \not\Vdash (f = 0) \lor (g = 0)$$ (in the sense of sheaf semantics) and therefore $$X \not\Vdash (f \times g = 0) \Rightarrow ((f = 0) \lor (g = 0))$$ but sheaf semantics validates intuitionistic logic, so this implies $$(x \times y = 0) \implies ((x = 0) \lor (y = 0))$$ cannot be proven in intuitionistic logic.

-
I want to understand what you mean by "if we had chosen this axiom, then it would not be possible to prove there are no zero-divisors". You say that $x \neq 0 \Rightarrow \exists x^{-1}$ is not sufficient... but given $xy = 0$, if $x=0$ we are done, and if $x \neq 0$, we can use this axiom to say that $0 = x^{-1}\times 0 = x^{-1} x y = y$. Is it because I considered that either $x = 0$ or $x \neq 0$ that my proof is not valid for intuitionnists? Or is it something more? And when you started talking about the tight apartness, I think you meant "non-equality" instead of inequality... – Patrick Da Silva Dec 31 '11 at 13:11
Yes, you have assumed the law of excluded middle there. – Zhen Lin Dec 31 '11 at 13:28
Is it wrong because intuitionnists think "there's something in the middle" or is it just because they don't accept this kind of statement as an axiom? – Patrick Da Silva Dec 31 '11 at 14:13
@Patrick: What's the difference between the two? It is not an accepted principle of intuitionistic reasoning. To give a concrete example, if you have a function $f$ which is zero on an open set, then neither $f = 0$ nor $f \ne 0$ hold. – Zhen Lin Dec 31 '11 at 14:47
Uh, I don't understand your example ; in my head the zero function is the function that is zero everywhere, if $f$ is zero on the open set then it is the zero function on that set. What I mean is that I think there's a difference between admitting that neither $x = 0$ or $x \neq 0$, and just saying that we don't assume so. For instance, it is one thing to say that there exists $x \in \mathbb Z$ with neither $x =0$ or $x \neq 0$, and it is another thing to say that we don't allow ourselves (using sufficiently relaxed axioms) to assume that there exists no such $x$. Do you see my point? – Patrick Da Silva Dec 31 '11 at 15:00

Let's prove the contrapositive: if $a\neq0$ and $b\neq0$ then $ab\neq0$.

Since we're in a field, any nonzero element has an inverse: $aa'=1$, $bb'=1$. Then $(ab)(a'b')=(aa')(bb')=1\cdot1=1$. This implies that $ab\ne0$ because $0$ times anything is $0$.

For this last step, I've used: $xy\ne0$ for some $y$ $\implies x\ne0$, which is the contrapositive of $0y=0$ for all $y$.

-
Again, I thought contrapositive is equivalent to contradiction ( consider p -> q). Then look at not(q) -> not(p). This has to be true as if it weren't we'd have not(q) -> p -> q a contradiction. – Adam Dec 31 '11 at 2:52
@Adam, that's a common misunderstanding. There are many proofs which are presented as proof by contradiction when they're actually by contrapositive. – lhf Dec 31 '11 at 2:55
BTW, the direct argument given by Andres Caicedo in a comment is much clearer. – lhf Dec 31 '11 at 2:58
@Adam Proof by contradiction usually involves assuming some hypothesis ~q, and then showing that it leads to a falsity of some sort, and inferring q. Often, this means that we can infer that we have the conjunction of some proposition p and its negation ~p, (p^~p). So, we have ~q leading to (p^~p) (or it seems clear enough that we can infer this falsity or potentially some other one, even if such a conjunction of a proposition and its negation isn't stated). So, ~q gets discharged and we infer q the equivalent of its negation. Contrapositive works as you say, where you infer a conditional. – Doug Spoonwood Dec 31 '11 at 3:43

A way to prove that a field has no zero divisors without using a contradiction method : Suppose $ab = 0$. Then there is two possibilities : either $a = 0$ (in which case we are done) or $a \neq 0$ and $a$ is a unit, therefore $b = a^{-1}ab = a^{-1}0 = 0$. I have never used any form of contradiction hypothesis. I've only dealt with cases. This also works in non-commutative fields.

Hope that helps,

-

You could approach this case by case:

$a$ and $b$ are either positive, negative, or zero.

• $a>0$, $b>0$ then $ab>0$ (positive times positive is positive). Thus $ab \not=0$.
• $a>0$, $b<0$ then $ab<0$ (positive times negative is negative). Thus $ab \not=0$.
• $a>0$, $b=0$ then $ab=0$.

etc.

Therefore, the only way we get $ab=0$ is if $a=0$ or $b=0$.

Edit: Admittedly, I guess I'm still using the law of excluded middle (and thus contradiction) here :(

For any field:

Suppose $ab=0$. Then if $a=0$, we are done. If $a \not=0$, then $a^{-1}$ exists and so, $a^{-1}ab=0$ thus $1b=0$ and so $b=0$. Therefore, either $a=0$ or $b=0$.

-
Don't we tuck contradiction under the rug in that argument (I went down this way also). You're really saying If ab = 0 and a,b are non-zero then ... case by case ... so ab =/= 0 in each case? – Adam Dec 31 '11 at 2:45

Let $m,n\in\mathbb{N}$ such that $m,n>0$ (I subscribe to $0\in\mathbb{N}$ but it really doesn't matter here). It can be shown by induction that $mn\neq 0$. That is, that $mn>0$.

Now, let $a,b\in\mathbb{Z}$. If $ab=0$, then $|ab|=|0|=0$. Therefore $|ab|>0$ implies $ab\neq 0$.

Suppose $a,b\neq 0$. Then $|a|=m>0$ and $|b|=n>0$. By the above, $|a|\,|b|=|ab|=mn>0$. Hence $ab\neq 0$. Then if $ab=0$, we have $a=0$ or $b=0$.

-