1
$\begingroup$

So I'm a little confused as to how to disprove the following statement using formal logic: Let x and y be integers. If $d\in \mathbb{Z}$ such that $d|(ax+by)$ for some $a,b\in \mathbb{Z}$, then $d|x$ and $d|y$.

Here's what I have so far: Rewrite the statement as $\forall x\in \mathbb{Z}, \forall y\in \mathbb{Z},\exists d\in \mathbb{Z} ((\exists a,b\in \mathbb{Z} (d|(ax+by))) \Rightarrow (d|x \wedge d|y))$.

But if I set x = y = 0, then the statement is true (it is false if a = b = 0 and $x\neq 0$ and $d = x+1$). Since the statement is a universal statement, will this counterexample suffice?

Question: is my rewritten version of the statement equivalent to the original statement?

$\endgroup$
1
$\begingroup$

It's mostly correct, except for the $\exists \, d \in \mathbb{Z}$. When we say something like let $d \in \mathbb{Z}$, it is implicitly understood that $d$ is an arbitrarily chosen integer. In other words, it's just another way to say, for all $d \in \mathbb{Z}$.

Notice that $x$ and $y$ share the exact same English description: "Let $x$ and $y$ be integers". You correctly determined that a universal quantifier was used for each. The integer $d$ is also employing the same universal quantifier for the same reason.

Typically, the reason why the $d$ was separate from $x$ and $y$ is to emphasize the role that this integer $d$ plays in the proposition; in this case, if $d$ divides $(ax + by)$ for some integers $x$ and $y$, then $d$ divides $x$ and $d$ divides $y$. Observe that $d$ is definitely more involved than $x$ and $y$ are, although all three of them were arbitrarily chosen integers--the integer $d$ is just more important in this case.

Therefore, the proper logical skeleton of the above proposition is as follows $$\forall x \in \mathbb{Z} \, \forall y \in \mathbb{Z} \, \forall \, d \in \mathbb{Z}\, \Big( \, \exists \, a \in \mathbb{Z} : \, \exists \, b \in \mathbb{Z} : d \,| \,(ax+by) \implies d \, | \, x \, \wedge \, d \, | \, y \, \Big)$$

or more compactly

$$\forall \, x ,y,z \in \mathbb{Z}\,\Big(\exists \, a,b \in \mathbb{Z} : d \, | \, (ax+by) \implies d \, | \, x \wedge d \, | \, y \, \Big)$$

Thus, if we wish to find a counterexample, we would consider the negation $$\exists \, x,y,z \in \mathbb{Z} : \,\Big[\exists a,b \in \mathbb{Z} : d \, | \, (ax+by) \, \wedge \big(d \, \nmid x \lor d\, \nmid y\big)\,\Big]$$

Given this structure, here is my counterexample below. You can expose the yellow area by hovering your mouse over it.

Let $a = 2, x = 5, b = 3, y = 2,$ and $d=2$. Then $d \, | \, (ax + by)$, since using our assignments yields $2 \, | \, 16$, but $d \nmid x$, because $2 \nmid 5$.

$\endgroup$
1
$\begingroup$

Your rewritten version is not quite correct (in fact, the rewritten statement is true while the original statement is false). Your rewritten version could be stated as "Let $x$ and $y$ be integers. Then there is some $d \in \mathbb{Z}$ such that, if there exists $a, b \in \mathbb{Z}$ such that $d \mid (ax + by)$, then $d \mid x$ and $d \mid y$." You should convince yourself that this statement is true, and not equivalent to the original statement!

You should have written something like "$\forall x,y,d \in \mathbb{Z} (\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y))$" instead. The important thing is that the question does not ask if there exists a $d$ such that $\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$. It asks if $\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$ is true regardless of the value of $d$. Thus, $d$ should be universally quantified.

To show that the statement $\forall x,y,d \in \mathbb{Z} (\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y))$ is false, you must provide specific values of $x, y, d \in \mathbb{Z}$ such that $\exists a,b \in \mathbb{Z} (d \mid (ax + by)) \implies (d \mid x \land d \mid y)$ is false; i.e. $\exists a,b \in \mathbb{Z} (d \mid (ax + by))$ and $\lnot (d \mid x \land d \mid y)$ are both true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy