3
$\begingroup$

In the book "How to Prove It", by Velleman, appear these two examples.

  1. Prove that for every integer $x$, the remainder when $x^2$ is divided by 4 is either 0 or 1.
  2. Prove that for every real number x, if $x^2 \geq x$ then either $x \leq 0 \lor x \geq 1$.

Symbolization:

  1. $x \in \mathbb{Z} \to (x^2 \text{ has remainder } 0) \lor (x^2 \text{ has remainder } 1)$
  2. $\forall x(x^2 \geq x \to (x \leq 0 \lor x \geq 1)$

In both cases, the author symbolises the conclusion with a disjunction.

In my mind, the conclusion is an exclusive or. In the first example, if I write a number in the form $k \in \mathbb{Z}$, that same number can not be written in the form $4l$ for some number $l \in \mathbb{Z}$. In the second one, a number being 0 excludes the possiblity of it being greater than or equal to 1.

What would be the explanation for this issue, from a logic perspective ?

If my perspective is incorrect, how does a proof of an "exclusive or" look like ?

$\endgroup$
2
  • $\begingroup$ I think this covers the main aspects of the question. $\endgroup$ – Gae. S. Apr 25 '20 at 21:17
  • $\begingroup$ Why in the symbolization of 1. appears $\mathbb{R}$ instead of $\mathbb{Z}$? $\endgroup$ – Riccardo Apr 25 '20 at 21:35
1
$\begingroup$

Since in these cases the options are mutually exclusive, both kinds of or are equivalent. It's usually more convenient in mathematics to use $\lor$ if possible, because it's dual to $\land$, and many proofs easily obtain a result of the form $p\lor q$, where $p\oplus q$ is either harder to prove or in general false. For example, $xy=0\to x=0\lor y=0$ (unless we have zero divisors).

$\endgroup$
2
  • $\begingroup$ Could you expand a little bit on your example $xy=0\to x=0\lor y=0$ ? $\endgroup$ – F. Zer Apr 25 '20 at 22:22
  • 1
    $\begingroup$ @F.Zer The product of nonzero quantities is nonzero, so from $xy=0$ we can deduce $x=0\lor y=0$. But that's all we can deduce; we can't deduce $x=0\oplus y=0$. $\endgroup$ – J.G. Apr 25 '20 at 22:24

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.