Can you explain math proofs?

Post Reply New Topic

What's the simplest example of a math proof you can come up with? I'm thinking if I see a really simple example, I'll get the concept. Nothing higher than algebra, please. The simpler the better.

I've looked at proofs, and I can see they're a circular process, kind of leading back to the same place, but what I don't get is why each step is proving a damn thing or is more valid than the initial statement. Sometimes the initial statement seems more evident to me than the steps taken to prove it.

Help! I've always been considered very logical, but this just stumps me. A few percents of the questions in the course are proofs, and I want to understand. Since the math teacher sucks at explaining things, I was wondering if anyone here would like to give a stab at giving me an idea of what proofs are really about.

Thanks.

I felt like this at times when I saw mathematical proofs for the first time. In my course I think students are only expected to have a good sense of how to write proofs by the end of their second year in college. Basically, they're valid deductive arguments to convince people that a statement is true, relying on things you should already know.

I'll start by mentioning what a group is. A group is a set G with an operation * such that the following axioms are satisfied:
a) If x and y are elements of G, then so is x*y. (closure)
b) If x, y and z are elements of G, then (x*y)*z=x*(y*z). (associativity)
c) There exists an element e of G such that for all elements x in G, the equation e*x=x*e=x holds. e is called the identity element of G. (identity)
d) For each x in G, there exists an element y in G such that x*y=y*x=e, where e is the identity element. y is conventionally written x^-1 or "the inverse of x". (inverse)

An example of a group is the set Z of integers with the operation of addition. Clearly a) is satisfied, as is b), the identity element is 0 and the inverse element of x is -x (x+(-x)=0). An example of something which is not a group is the set N of natural numbers with the operation of multiplication. After all, only 1 has a multiplicative inverse in N (the multiplicative inverse is generally 1/n for any n not equal to zero).

Proposition: Given any group G, there exists only one identity element.

Proof: Consider e and f to be two identity elements of G. Since f is an element of G, e*f=f by c). Since e is an element of G, f*e=e*f=e by c). So e=e*f=f, or e=f.

One of the classic forms of proof is reductio ad absurdum (proof by contradiction). You make an initial claim and show that this initial assumption leads to a contradiciton. For example, I claim that there exists a number greater than zero smaller than all other numbers greater than zero (a "smallest" number if you will) and call it x. If I consider x/2, we see that it is still greater than zero, and also smaller than x. This is a contradiction as x cannot possibly be the smallest positive number and yet be bigger than another positive number. So my initial claim that there is a smallest positive number must be false.

Incidentally, I will be giving a presentation on reduction ad absurdum and its applications in Minesweeper next week

I just learned more maths in five minutes than I did in 3 years of high school... scary.

And yes, proofs suck. As do their contemporaries, profs. Both do the same thing, make you prove what you know.

But just maybe... you're not proving you know maths.

Having long explanations of simple concepts is only what they make you do early on. When you get past that stage you start proving things which are counterintuitive to many people when viewed naively, or more often just not that obvious to someone experienced with only high school maths.

Here's an example of one theorem you would see early on which has struck many people as counterintuitive.

Definition: The power set of a set X is the set of all subsets of X.
Definition: A total function f from X to Y is an ordered triple of sets (F, X, Y) where F is a set of ordered pairs (x, y) for x in X and y in Y, X only contains all x which feature in F, and each x in X corresponds in F to only one y in Y. Such a y is referred to as the image of x in Y, or f(x).
Definition: A total function f is said to be surjective if Y only contains all y which feature in F.

Theorem: Given any set X, no total function f from X to the power set of X can be surjective.

Proof: Consider any total function f from X to its power set. The set Z={x in X: x is not in f(x)} is a subset of X, and thus an element of the power set of X. However, it is not in the image of X. (Note that the empty set is in the power set of X) So any such total function f cannot be surjective.

> Proposition: Given any group G, there exists only one identity element.

Oh, dear, see, I don't understand what "identity element" means, so I can't follow this. When I said algebra, I meant the simple algebra you do before college. I suppose I should post an example.

Edit, okay, here's an example:

Okay, notation first: logb means base b but I don't have the proper codes to write a subscript here.

Prove that logb x/y = logb x - logb y, by letting logb x = M and logb y =N

Okay, a big problem here is that they told us at the beginning of that chapter that we have to know that log a/b = log a - logb. Is that the log of a quotient rule? Anyway, that's why the example to prove is right. So the rule is in base 10 and the question to prove is in any base. As long as the bases are the same for all the terms, the rule holds. I don't know what I'm supposed to do.

The last explanation by the teacher of a question required numerous emails, a couple of hours, and a dead end whereby he mentioned "transcendental functions" which I had never heard of before, which is why I am turning to you all for help.

Note, we finished the log chapter a while back. This was just on my list of stuff I couldn't understand. There's no marks involved. I just want to understand.

Say x=b^u, y=b^v
Then logb(x/y)=logb((b^u)/(b^v))=logb(b^(u-v))=u-v=logb(x)-logb(y)

So, where you put x and y, I put M and N?

And how does that prove something? I don't have a feel for this. With ordinary logic, I have a strong sense of clarity and parts relating to wholes or being excluded. Here, I don't really see the assumptions, assertions, exclusions, whatever is making this meaningful.

I know what you mean. I remember when I was at university feeling qute confused by an example where ‘proof by induction’ was used to show that there is an infinite number of integers!

But one of my favourite simple proofs is the proof that there is an infinite number of prime numbers. It’s a proof by contradiction: you first assume that there is NOT an infinite number of prime numbers, and then show that that assumption is false. Here’s the proof (copied pretty much from a Newman-Nagel book).

1. Assume there is only a finite number of prime numbers. Call the largest prime number X
2. Form the product of all primes less than or equal to X, and add 1 to the product. This gives a new number Y, where Y = (2 x 3 x 5 x 7 x … x X)
3. If Y is itself a prime, then X is not the greatest prime, for Y is obviously greater than X
4. If Y is composite (i.e., not a prime), then Y must have a prime divisor Z; and Z must be different from each of the prime numbers 2, 3, 5, 7, …, X smaller than or equal to X; hence Z must be a prime greater than X, hence if Y is composite then X is not the greatest prime
5. But Y is either prime or composite
6. Hence X is not the greatest prime
7. Hence there is no greatest prime

The thing is, even this proof misses out certain formal steps. And I think it’s the formality that gets frustrating when you’re first learning about proofs.
The proof above was know to Euclid, but his explanation for where, say, line 5 came from would probably not have satisfied a 19th Century logician, even though it would have seemed self-evident to him.

A proof is NOT circular. Starting with the axioms, postulates, definitions and the specific hypotheses of the theorem one progresses by logic until the desired conclusion is reached. There is no circularity.

Here is a simple example. If n is odd then n*n is odd.

Proof:

hypothesis n is odd
there exists k such that n = 2*k + 1 definition of odd

(2*k + 1)*(2*k + 1) = 4*k*k + 4*k + 1 using distributive low

therefore n*n is odd definition of odd

QED.

This is a trivial theorem but it serves as an example.

Now show that is n is even then n*n is even



ruveyn

We might find it easier if the proof were written more explicitly.
Claim:
Suppose logb(x) and logb(y) exist
Then logb(x/y) = logb(x)-logb(y)

Proof:
1. Let M=logb(x) and N=logb(y) (we can make this step because logb(x) and logb(y) exist)
2. Then x = b^M and y=b^N (by definition of a log base b)
3. Then x/y = (b^M)/(b^N) (just divide the one into the other)
4. Then x/y = b^(M-N) (a basic property of exponents)
5. Then logb(x/y) = log(b^(M-N)) (just take the logb of both sides)
6. Then logb(x/y) = M-N (by definition of a log base b).
7. But M = logb(x) and N=logb(y) (by assumption in (1))
8. Therefore, logb(x/y) = logb(x)-logb(y) (provided that logb(x) and logb(y) exist)

When written like this, it is much clearer what is being proved and what isn't and how. I find it helps to write out very explicitly what is being done each step of the way when I prove things.

I mentioned what it was in my definition of a group. Perhaps I should have been more clear.

An element e in a group G with operation * is said to be an identity element of G if given any element x of G, x*e=e*x=e. By the definition of a group, an identity element must exist.

With the proposition I mentioned, you now can say "the identity element" instead of just "an identity element" because there exists only one of them.

You just need to get used to reading them. The assumptions and assertions are all there.

"Given any group G, there exists only one identity element."

Essentially, the only "assumption" is that G is a group. So all we have to work from is the definition of a group, essentially. And we look at the properties that a group has.

Hector, thanks for trying, but for now I'm going to stick with algebra or logs because that's what I'm working on and it's a bit of a stretch to learn an example in something I'm not used to. I want to boil it down to something very simple so I can see what's being done. Even though you describe "identity element" it actually means nothing to me, but maybe I'll be able to understand it later if and when the dust clears.

Let u1 and u2 be identity elements of G.

Then u1*u2 = u2 because u1 is an identity element.
Likewise u1*u2 = u1 because u2 is an identity element
therefore u1 = u2.

qed.