QUOTE(Elnendil @ Oct 10 2010, 03:03 PM)
I'll just make this point I guess. The book that i'm using in question doesn't call what we've been discussing definitions, and goes out of its way to prove the statements (If a|b and a|c, then a|(bx+cy) for some x and y is defined as a theorem in my book and has a proof for it). There are actual "definitions" in the book, like d=(a,b), and thats stupid to prove because its a definition of what the greatest common divisor is, its just the notation you're supposed to use. Thats really about in on me using the definition here. If you're saying that the concept is so simple that its practically the definition, I suppose I can agree there.
Well, the a|(bx+cy) thing is definitely not definitions. You're not using any new symbols, you're just using the same old ones (+, *, |), so you have to prove that the statement is compatible with your definitions (i.e. prove it). However, the definition of the symbol | is something you can't prove.
d = (a,b) is not really a definition in the way that's meant for math. You're just temporarily assigning d the value of (a,b), and the symbol (,) is defined to be the greatest common divisor, and "greatest" is determined by the order, and "common divisor" is defined to be q such that \exists x s.t. qx = a and \exists y s.t. qy = b.
For the natural numbers with arithmetic (N, 0, 1, +, *) (note there's no / or -, so you can't use those), your assumptions are something like (for all a, b, c \in N):
(definition of addition)
- a+b = b+a
- (a+b)+c = a+(b+c)
- a+0 = a (definition of 0)
(definition of multiplication and compatibility with addition)
- ab = ba
- (ab)c = a(bc)
- 1a = a (definition of 1)
- a(b+c) = ab+bc
(some other crap that's uncommon)
- a+b = a+c iff b = c
- for any set S, if 0 \in S, and for every k \in S we have k+1 \in S, then N \subset S
(I think that's enough, but you can check it against
http://en.wikipedia.org/wiki/Peano_arithmetic and see if the definition is equivalent)
So using those, we DEFINE a|b to mean \exists x s.t. ax = b. Once we define that, we can prove anything that uses those symbols, but not anything that uses other words and symbols.