2
$\begingroup$

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$.

  • 0
    Looks good to me2010-08-20
  • 0
    1) is there too much hand waiving going on, and 2) is it a valid proof.2010-08-20
  • 2
    it looks correct to me. the only comment is that you could be more precise when you say 'by algebra we can deduce...'2010-08-20
  • 0
    This is more verbose than one would normally see. Why are you unsure whether it's a valid proof or not?2010-08-20
  • 1
    @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.2010-08-20
  • 1
    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.2010-08-20
  • 1
    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.)2010-08-20
  • 0
    It's not clear to me why you have said "it's more of a philosophical question than a math question" and then accepted the 'the proof is valid' answer.2010-08-21

3 Answers 3

0

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.

1

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$.

0

The proof is valid.

  • 2
    That's great to hear, but perhaps the OP would love to see a bit more elaboration here... :)2010-08-20
  • 0
    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.2010-08-20