# $(\forall{a,b,c \in \mathbb{N}})[(a|b) \rightarrow (ac|bc)]$ Divisibility Proof

Could someone verify this proof?

Given the following definition of divisibility $(\forall{a,b \in \mathbb{N}})[a | b \equiv (\exists{c \in \mathbb{N}})(ac=b)]$.

Statement: $(\forall{a,b,c \in \mathbb{N}})[(a|b) \rightarrow (ac|bc)]$ .

Proof:

Let $a,b \in \mathbb{N}$ be arbitrary. Assuming that $a|b$, we can conclude that $\exists{d \in \mathbb{N}}$ such that $ad = b$. By Algebra we can deduce the following sequence of statements. If $(ad)=b$, then $(ad)c=bc$. Therefore $(ac)d=bc$. Hence by the definition of divisibility we know that $ac|bc$.

-
Looks good to me –  Tomer Vromen Aug 20 '10 at 15:07
it looks correct to me. the only comment is that you could be more precise when you say 'by algebra we can deduce...' –  WWright Aug 20 '10 at 15:09
@maud The reason I posted it, is that unless you have a computer to check the proof, you need to have other people look at it for mistakes. You can check it yourself, but there is always a chance of a mistake. I made it particularly verbose so for the sake of clarity. –  Tony Johnson Aug 20 '10 at 15:17
Also, it's more of a philosophical question than a math question. It's a very simple proof, but by the responses I get, you see how people actually define what makes a valid proof and an invalid one. –  Tony Johnson Aug 20 '10 at 15:20
Where you write "By Algebra, ...", I would write "Multiplying both sides by $c$, we find that $(ad)c = bc$. Therefore ...", continuing exactly as you do. I would do this for the same reason that WWright suggested being more precise: the precise reason that $(ad)c = bc$ is because we are multiplying both sides of an equality by the same number. This is more specific than just saying "By Algebra", and so more helpful to the reader. (In general, when trying to explain how the steps in an argument follow one from the other, it is good to be as specific as possible, to make them easy to follow.) –  Matt E Aug 20 '10 at 15:54

The proof is valid.

-
That's great to hear, but perhaps the OP would love to see a bit more elaboration here... :) –  Ｊ. Ｍ. Aug 20 '10 at 17:08
Don't know what else to say - it's a simple proof and I would give it 5/5. Also the Universe may have one magnetic monopole somewhere, which explains why magnetic 'charge' is discretized. –  KalEl Aug 20 '10 at 20:16

Yes, your proof is correct. Since it employs only the associative and commutativite axioms for multiplication it remains true in any commutative semigroup. The proof employs only the inference rules of first-order equational logic, namely that equality is an equivalence relation (reflexive, symmetric, transitive) and the rules of substitution: $p(x) = q(x) \rightarrow p(a) = q(a)$ and replacement: $a = b \rightarrow p(a) = p(b)$.

By a famous theorem of Birkhoff, for any algebraic structure that can be defined by axioms - like comutativity, associativity, etc - that are all universally quantified equations, said inference rules are complete, i.e. an equation is provable from the axioms using said inference rules iff it is true in every structure that satisfies the axioms. However, finding such a purely equational proof can be highly difficult. For example, consider the famous Jacobson theorem that rings satisfying the axiom $x^n = x \;$ are commutative $xy = yx$. it's notoriously difficult for $n>2$ to find equational proofs of this theorem.

Returning to the specific problem: generally scaling a polynomial $f(x)$ by a cancelable element $c$ does not change its solution set since $c f(d) = 0 \iff f(d) = 0$. In particular the solvability of $f(x) = 0$ is not altered - which is what you are concerned with in the definition of divisibility, i.e. the solvability of $ax = b$. E.g. consider the less trivial case of quadratic $f(x)$. Note that the formula $g(a,b,c)$ for the solutions of a quadratic $ax^2+bx+c$ remains unaltered by nonzero coefficient scalings $g(ad,bd,cd) = g(a,b,c)$. As for solvability, scaling the polynomial by $d$ multiplies the discriminant $b^2-4ac$ by $d^2$ so it does not affect the solvability criterion - that the discriminant be a perfect square. But we don't need to know these explicit formulas to deduce this. Rather, we can deduce it at a conceptually higher-level, simply from the cancelability of $c$, i.e the invertibility of scaling transformations $x\to cx$.

-

We know that $\displaystyle\frac{b}{a}$ is an integer. Therefore $\displaystyle\frac{bc}{ac}=\frac{b}{a}\in \mathbb{Z}$ i.e. $ac|bc$. Otherwise $c=0$ and then the result is trivial.

-