These proof exercises would be far more productive if the statement to be proved was something less trivial than an exercise in common sense. Otherwise, we end up demanding a proof for things like 1+1=2.
Deveno,
An equivalent response to yours would be: Your response is meaningless because you haven’t defined what an integer is.
After reproducing my proof in a very wordy and obtuse manner which no instructor would use, you ask:
"Why must an integer be either even or odd? Why can't it be BOTH, or nether?",
Fair enough. By the Euclidean algorithm any integer on division by 2 must leave a remainder of 0 or1. If 0, even; if 1, odd, by definition.
ie, I=2m or I=2n+1, which I thought would be accepted at a high school level. I see no point in belaboring it.
I am still confused as to why this endless rehashing of my original proof, except for the question above, which I am glad to answer.
These proof exercises would be far more productive if the statement to be proved was something less trivial than an exercise in common sense. Otherwise, we end up demanding a proof for things like 1+1=2.
Since you brought it up. 1 + 1 = 2 is not as simple as it might appear. You can use the Peano axioms to do so. It only takes about half a page.
Since the problem is posted in Discrete Math I would lean toward the more technical side. But as you say we don't know just how many of the "simpler" axioms we would be allowed to use.
-Dan
In my opinion, the “technical side” would be to begin by listing the axioms and definitions one wished to apply to the problem and proof, and then use them exclusiveley, which no one has done. Absent that, the only thing that makes sense is a college algebra interpretation and proof.
I don’t consider verbose rehashing of a simple proof “techniccal.”
This is how I understand 1+1 = 2 to be derived from the Peano axioms:
1 = S(0) (definition)
2 = S(S(0)) (definition)
1 + 1 = 1 + S(0) (applying the definition of 1)
1 + S(0) = S(1 + 0) ((recursive) definition of addition)
1 + 0 = 1 ((recursive) definition of addition)
S(1 + 0) = S(1) (because S is a function)
1 + 1 = S(1) (transitivity of equality, applied thrice)
1 + 1 = 2 (transitivity of equality using the definition of 2)
Note this derivation uses the notion of function, and recursive function, which of course must be spelled out before-hand.
*********
One of the problems with answering questions such as the OP has asked, is deciding what is "legal" for them to take as "given". The addition of extra "verbosity" as you call it, is purely to remove doubt. If the assumptions Hartlw makes in HIS post are taken as "given", sure, there is no need to be so explicit, we can be a bit more pithy. This is an on-going problem at ANY level of mathematics, upon what foundation do we base "accepted truth"? I have read MANY college-level and beyond textbooks that steadfastly refuse to define what a "set" is, and go on to blithely use the concept as if everyone understood it. The same often goes for the concept of a function, which is intimately bound up with the concept of a set:
A function f: A→B is a subset of AxB with the property that if (a,b) and (a',b') are in f, then whenever a = a', b = b' (each "input" a has a UNIQUE "output" b, but there is nothing to prevent two different a's from mapping to the same b).
Note that this definition already pre-supposes that one has an idea of the domain (A) and co-domain are (namely, two sets), and also that one is familiar with the cartesian product (or the set of all ordered pairs (a,b) with a in A, and b in B).
To go even further, the "division algorithm (Euclidean algorithm)" you quote is already dependent on a large number of properties of integers (such as the distributive law of multiplication over addition), and perhaps removes your proof even further from your original argument.
You seem to take personal umbrage as if you feel someone has intimated your proof is somehow flawed, which in fact, it isn't. An argument by contradiction (implicit in post #6, and elaborated on in post #14) is perfectly sound logical thinking. However, some of your statements, such as:
even*odd = even
which is TOLD to us as very young children, can actually be established as consequences of the Peano axioms (or more loosely, as a consequence of properties of INTEGERS). Does this NEED to be proved? It depends. The "arithmetic" of parity, namely the rules:
even + odd = odd
even + even = even
odd + odd = even
even*even = even
even*odd = even
odd*odd = odd
leverage quite a few "prior" rules (enough, in fact, to establish that the integers form a euclidean domain, the "proto-typical" such structure). for example:
odd*odd = odd:
One demonstration of this might go as follows:
(2k + 1)(2m + 1) = 2k(2m + 1) + 1(2m + 1) (distributive law)
2k(2m + 1) + 1(2m + 1) = 2k(2m + 1) + (2m + 1) (1 as the multiplicative identity)
2k(2m + 1) + (2m + 1) = (2k)(2m) + (2k)(1) + (2m + 1) (distributive law, again)
(2k)(2m) + (2k)(1) + (2m + 1) = (2k)(2m) + 2k + (2m + 1) (1, as the multiplicative identity, again)
(2k)(2m) + 2k + (2k + 1) = 2(k*2)m + 2k + (2m + 1) (associativity of multiplication)
2(k*2)m + 2k + (2m + 1) = 2(2k)m + 2k + (2m + 1) (commutativity of multiplication)
2(2k)m + 2k + (2m + 1) = 2(2(km)) + 2k + (2m + 1) (associativity of multiplication, again)
2(2(km)) + (2k) + (2m + 1) = [2(2(km)) + 2k + 2m] + 1 (associativity of addition)
[2(2(km)) + 2k + 2m] + 1 = 2(2(km) + k + m) + 1 (the distributive law, again)
2(2(km) + k + m) + 1 = 2z + 1, for some integer z = 2(km) + k + m (closure of the integers under multiplication and addition)
(I may have glossed over a few steps, but you get the idea)
Is there a NEED for such "itty-bitty" explicit declaration of each logical step we take? It DEPENDS. In some courses, maybe not. Proofs vary from the informal (usually easy to read), such as yours, to the extremely formal (such as those found on the site:
Proof Explorer - Home Page - Metamath), which are often quite difficult to parse in "natural language". One man's "obvious" is another man's "I don't see it".
Hartlw is apparently used to thinking "informally" (which is, paradoxically, on a higher level than "formal thinking" which is much like "machine language"). What is appropriate here? It depends (on things we do not know, and which the OP might not ever make very clear). Perhaps his explanation is crystal-clear to the original poster, and if he was taking a Discrete Math course from some (unknown, to us, perhaps even hypothetical) instructor, his reply would receive "full marks". Perhaps not.
so 1+1 = 1+1?
You haven't defined the successor function. You only defined it for 1 and 2. What is your definiton of the successor function. All you have said so far is 2 is the successor of 1 by definition.
1 and 2 is a notation convention for the natural numbers which is independent of the Peano Postulates.
Having defined the natuaral numbers, you can then define a notation convention such as binary, decimal, hexadecimal, etc. But informally it's ok.
Edit: To save some back and forth, my definition of the successor function for the natural numbers is S(n)=n+1. What's yours?
Edit: Peano's potulates don't define addition. But if you want to assume it's been defined somewhere, informally that's ok.
Ummm...Okay guys. I mentioned the 1 + 1 = 2 thing as a pithy little comment. Apparently it's turned into something of a discussion point, but it's not on topic. My bad.
Please feel free to continue the discussion in a new thread.
-Dan