1

enter image description here

Prove each of the following statements.
(a) For all $b \in \mathbb{Z}$ if for all $k \in \mathbb{N}$, $b \not\mid k$, then $b = 0$.

By hypothesis: $b \not\mid k \implies b\ell \neq k, \ell \in \mathbb{Z}$.
Note: $b \in \mathbb{Z} \wedge \ell \in \mathbb{Z} \implies b\ell \in \mathbb{Z}$

  • If $b$ was a negative integer, $\ell$ would simply have to be $-1$ and $b\ell$ would equal $k$.
  • If $b$ was a positive integer, $\ell$ would simply be a positive integer also, and $b\ell$ would equal $k$.
  • However, if $b$ was $0$, then no matter what $\ell$ was, $b\ell$ would not equal $k$, or a natural number.

$\therefore$ $b \not\mid k = b \not\mid \mathbb{N} \implies b\ell \neq k \implies \boxed{b = 0}$

Am I correct in my steps, especially that of proclaiming that b has to 0 and not l?

senshin
  • 503
Guest
  • 323
  • 1
    your proof is not very readable caan you type it over (using latex see http://math.stackexchange.com/editing-help and what do you mean by $ b \not| k $ – Willemien May 28 '14 at 17:45
  • @Willemien I'm trying to prove that for b to be indivisible by k, b has to be 0 – Guest May 28 '14 at 17:48
  • I would be careful. $b \not\mid k$ means that there is no such $l$ such that $bl = k$. It does not mean that $bl \neq k$ generally; however it does mean that for all $l$, $bl\neq k$. I know that this is what you're getting at, but you should be more careful to write it out. – Emily May 28 '14 at 18:16
  • Furthermore, attempting to prove the statement directly requires that you exhaustively show that $bl \neq k$ for every possible $l$. This is not recommended. – Emily May 28 '14 at 18:17

3 Answers3

1

Suppose $b \neq 0$. Then, choose $k = b$ if $b > 0$, or $k = -b$ if $b < 0$. So, $b \mid k$, contradicting the hypothesis.

Emily
  • 35,688
  • 6
  • 93
  • 141
1

You seem to have the right idea, but your proof is somewhat awkwardly phrased. Perhaps a better approach is to note/prove that, for any $b\in\Bbb Z,$ we have that $b\mid b$ and $b\mid-b,$ so for any such $b$ there is always some $l\in\Bbb Z$ such that $bl=|b|.$ Since $|b|\in\Bbb N$ for all non-zero $b\in\Bbb Z,$ the result readily follows.

NB: This result relies on $\Bbb N$ being defined as the set of positive integers, which may vary from text to text.

Cameron Buie
  • 102,994
0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\notag \\ #1 \quad & \quad \text{"#2"} \notag \\ \quad & } \newcommand{\endcalc}{\notag \end{align}} $This is not a direct answer, but here is an alternative proof which might be helpful.

Put slightly more formally, and implicitly assuming that all variables range over $\;\mathbb Z\;$, you're asked to prove $$ \langle \forall k : k > 0 : b \not\mid k \rangle \;\Rightarrow\; b = 0 $$ for all $\;b\;$.

So let's calculate: $$\calc \langle \forall k : k > 0 : b \not\mid k \rangle \calcop{\equiv}{definition of $\;\mid\;$} \langle \forall k : k > 0 : \lnot \langle \exists n :: n \times b = k \rangle \rangle \calcop{\equiv}{logic: DeMorgan; merge $\;\forall\;$ quantifications} \langle \forall k,n : k > 0 : n \times b \not= k \rangle \calcop{\equiv}{logic: transpose; split $\;\forall\;$ quantifications -- preparing for next step} \langle \forall n :: \langle \forall k : n \times b = k : k \leq 0 \rangle \rangle \calcop{\equiv}{logic: one-point rule} \langle \forall n :: n \times b \leq 0 \rangle \calcop{(*) \;\;\;\ \equiv}{arithmetic -- split cases to separate $\;n,b\;$} \langle \forall n :: (n \leq 0 \lor b \leq 0) \;\land\; (n \geq 0 \lor b \geq 0) \rangle \calcop{\equiv}{logic: $\;\forall\;$ distributes over $\;\land\;$} \langle \forall n :: n \leq 0 \lor b \leq 0 \rangle \;\land\; \langle \forall n :: n \geq 0 \lor b \geq 0 \rangle \calcop{\equiv}{logic: pull part not using $\;n\;$ outside of $\;\forall n\;$, twice} (\langle \forall n :: n \leq 0 \rangle \lor b \leq 0) \;\land\; (\langle \forall n :: n \geq 0 \rangle \lor b \geq 0) \calcop{\equiv}{$\;\langle \forall n :: n \leq 0 \rangle\;$ and $\;\langle \forall n :: n \geq 0 \rangle\;$ are false; simplify} b \leq 0 \;\land\; b \geq 0 \calcop{\equiv}{arithmetic} b = 0 \endcalc$$

Notes. Many readers will probably find this proof overly long and formal, however, I consider it to be straightforward to design, because the design is guided by the shape of the formulas, together with the goal that we work towards.

This is an example of a proof which minimizes the number of surprises or 'rabbits pulled out of a hat': almost every step is really the simplest thing that one could do. And it would have been shorter, if I could assume that all readers would be familiar with using logic, as promoted by people like Edsger W. Dijkstra and David Gries and Fred B. Schneider.

The step where we have the most choice is $(*)$. There I could also have chosen the alternative $$ n \times b \leq 0 \;\equiv\; (n \leq 0 \land b \geq 0) \;\lor\; (n \geq 0 \land b \leq 0) $$ However, I chose $$ n \times b \leq 0 \;\equiv\; (n \leq 0 \lor b \leq 0) \;\land\; (n \geq 0 \lor b \geq 0) $$ because the latter has the form $\;P \land Q\;$, so that I could distribute $\;\forall\;$ over it in the next step. The alternative would have required to introduce a $\;\Rightarrow\;$ step, making the proof less general.

Finally, note that three notation decisions were helpful: assuming all variables are integers avoids $\;\in \mathbb Z\;$ throughout, reducing the visual noise; writing out the $\;\forall k\;$ quantification explicitly made it possible to manipulate it explicitly and apply the one-point rule; and expressions of the form $\;\ldots > 0\;$ are a lot easier to manipulate than $\;\ldots \in \mathbb N\;$ (or $\;\mathbb N^+\;$).

MarnixKlooster ReinstateMonica
  • 5,576