I encountered this question in an online textbook (page 51) I was using to self study. The proof given considered two cases: when x=0 and y=1, then the hypothesis gives a|($0\cdot b$ + $1\cdot c$) = a|c and when x=1 and y=0, a|($1\cdot b$ + $0\cdot c$) = a|b. At this point the book says the result is proven. But to me this proof seems incomplete because the hypothesis has a universal quantifier not an existential one, so shouldn't we prove a | b and a | c for all integers x and y?
9
-
6$\begingroup$ I don't see your objection. If $a$ divides $bx+cy$ for all choices of integers $x,y$, then it must divide $bx+cy$ when $(x,y)=(1,0)$. But that means that $a$ divides $b$ and so on. If a claim holds generally, then it must hold in each instance. $\endgroup$– luluCommented Aug 7 at 23:10
-
$\begingroup$ Sorry I'm still confused. The proof only considered two cases (x,y) = (1, 0) and (0, 1) where the conclusion is reached, but not all integers x, y though. So there could be values of x, y where hypothesis is true and conclusion is false. $\endgroup$– WeWillConquerCommented Aug 7 at 23:22
-
$\begingroup$ The conclusion doesn't depend on the values of $x$ and $y$. So if it is true for some values of $x,y$, it wil be true for all values of $x,y$. $\endgroup$– LucenapositionCommented Aug 7 at 23:26
-
1$\begingroup$ I meant the truth of the statement $a\mid b\land a\mid c$ doesn't depend on the values of $x,y$. $\endgroup$– LucenapositionCommented Aug 7 at 23:42
-
2$\begingroup$ It is clearly false to say that the fact that $a$ divides $bx+cy$ for some choice of integers $(x,y)$ implies that $a$ divides both $b,c$. The point here really is that we are assuming that $a$ divides $bx+cy$ for all choices of integers $(x,y)$. Thus we can assume that $a$ divides $3b-17c$ and so on. We are, in particular, free to take $(x,y)=(1,0)$ or $(0,1)$. Since the assumption holds for all choices, it must hold for those two. $\endgroup$– luluCommented Aug 7 at 23:53
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
3
It's like the scene from the first episode of Red Dwarf:
Lister : Where is everybody, Hol?
Holly : They're dead, Dave.
Lister : Who is?
Holly : Everybody, Dave.
Lister : What, Captain Hollister?
Holly : Everybody's dead, Dave.
Lister : What, Todhunter?
Holly : Everybody's dead, Dave.
Lister : What, Selby?
Holly : They're all dead. Everybody's dead, Dave.
Lister : Peterson isn't, is he?
Holly : Everybody is dead, Dave.
Lister : Not Chen?
Holly : Gordon Bennett! Yes, Chen, everybody, everybody's dead, Dave!
Lister : Rimmer?
Holly : He's dead, Dave, everybody is dead, everybody is dead, Dave.
Lister : Wait. Are you trying to tell me everybody's dead?
Holly : I wish I'd never let him out in the first place.
Here we have a universal quantifier - for all crew on the ship, that crew member is dead. If we then are trying to prove something and we need to start with the premise "Kochanski is dead", then "Everybody is dead" definitely provides that.
In your proof, we are told that $a | (bx + cy)$ for all $x$ and $y$. So we can make a very bad version of the Red Dwarf script from that.
Lister: What, even when $x = 1$ and $y = 0$?
Holly: $a$ divides $bx + cy$ for all $x$ and $y$, Dave.
Lister: Not $x = 0$ and $y = 1$, surely?
Holly: For all $x$ and $y$, Dave.
On the other hand, if we were trying to prove the universal quantifier, it is true that just proving individual cases is insufficient. If Lister found out that Rimmer was dead and used that to infer that the whole crew was gone, he would be guilty of a logical error.
(As it turns out, it is true that if $a | b$ and $a | c$ then $a | (bx + cy)$ for all integers $x$ and $y$, but not every statement is bidirectional like that.)
-
-
$\begingroup$ I understand that a divides bx + cy for all x and y, but I’m saying (x,y) = (1,0) and (0,1) is insufficient to prove a divides both only b and only c for ALL x and y. $\endgroup$ Commented Aug 8 at 22:17
-
$\begingroup$ We're not proving it's true for all $x$ and $y$, we're assuming it's true and using that to prove something else. $\endgroup$– ConManCommented Aug 8 at 23:42