Higher Level Math Gurus--I need you!

[mom2bee]

I need some help, how do I check my proofs? Are there like...guidelines or something that I can use to go back over my proofs?

 

With applied situations, the answer will be

1) reasonable (ie no negative time)

2) realistic (ie a person can't be 213ft tall) and

3) re-checkable. (ie You can work backwards or take a different route and still arrive at the same answer if you did it correctly)

 

But what about a proof? When you are proving (or trying to prove) something from Real Analysis/Advanced Calculus how can you tell if 1) you are really finished, 2) you are correct?

 

[kiana]

Well, I don't have a nice little checklist, but here are some things that need to be checked.

 

1) Make sure all of your assumptions are justified. A lot of times people will assume something is true which results in the proof being trivial. One of my most frequent comments is "You don't know this is true!"

 

2) Make sure that you are not arguing in circles. You cannot use part b of a problem to prove part a and then use part a to prove part b. You CAN use part b to prove part a if you have a proof for part b that does not depend at all on part a.

 

3) Make sure that you've included every case. It is very common that students will use an argument which only works when e.g. |x|>1 and not realize that they need another argument or two for the rest of the problem.

 

As a side note, here's a book on proof techniques that is freely available online as a PDF: http://www.people.vcu.edu/~rhammack/BookOfProof/index.html

 

ETA: When I get back to my office in a couple of weeks I will look up some more examples of student work and proof-writing tips I give, but I'm out of the office right now and don't have them all memorized.

[Kathy in Richmond]

Everything Kiana said above.

 

Is it homework? If not, give it to someone else to read over. Seriously, sometimes it's difficult to catch your own lapses in reasoning. Proof writing is one of those things that you learn by doing, making mistakes, doing again. You just have to jump in & give it a try.

 

Sometimes putting my proof aside for a few days & then re-reading with a fresh mind helps me.

 

Some of my favorite free resources:

 

Polya's classic book: How To Prove It

MathPath:  Proof in Mathematics

Mathcamp: Hints on Writing Mathematical Proofs

AoPS: How To Write a Solution (not only for proofs, but still applies)

[mom2bee]

Its not homework as I am self studying, but I don't have anyone to check it over as I'm the only "mathematically inclined" person in my social circle. By and large, I never know if I have an incorrect "proof" that I am adjusting but am leaving incorrect, a correct proof that I am messing up because of my self doubt, or what!

 

Sometimes I just feel like I'm going in circles!

 

Thanks for the links, that PDF looks especially helpful!

[kiana]

Its not homework as I am self studying, but I don't have anyone to check it over as I'm the only "mathematically inclined" person in my social circle. By and large, I never know if I have an incorrect "proof" that I am adjusting but am leaving incorrect, a correct proof that I am messing up because of my self doubt, or what!

 

Sometimes I just feel like I'm going in circles!

 

Thanks for the links, that PDF looks especially helpful!

 

What Kathy said about re-reading them is very relevant in that case.

 

Also, if there's any specific problem you're really uncertain of, you could post a scan of your work on the thread.

 

I also recommend the Schaum's outline of advanced calculus for self-study. While if you get a different (but valid) proof than the worked problems in the book, you may not be 100% sure, if you get the same or a very similar proof you will know you are correct. Furthermore, sometimes looking at proofs will get you the "Oh! that's cute! I didn't see that!" reaction.

 

If you do go this route, though -- cover up the solutions to the problems so you don't get even a glimpse to hint you on your way.

[Kathy in Richmond]

Also, if there's any specific problem you're really uncertain of, you could post a scan of your work on the thread.

 

Yes, this. Lots of folks here would be glad to help.

 

I also recommend the Schaum's outline of advanced calculus for self-study. While if you get a different (but valid) proof than the worked problems in the book, you may not be 100% sure, if you get the same or a very similar proof you will know you are correct. Furthermore, sometimes looking at proofs will get you the "Oh! that's cute! I didn't see that!" reaction.

 

If you do go this route, though -- cover up the solutions to the problems so you don't get even a glimpse to hint you on your way.

 

Oh yeah! I self taught out of Schaum's outlines series back in the day. Fond memories. :001_smile:

 

[kiana]

 

Oh yeah! I self taught out of Schaum's outlines series back in the day. Fond memories. :001_smile:

 

 

I have a collection of Schaum's outlines for pretty much anything an engineer would need, used by my parents in college in the late '60s/early '70s. While the FORTRAN book is pretty irrelevant, most of them are just fine! :D

[MarkT]

While the FORTRAN book is pretty irrelevant, most of them are just fine! :D

 

Computed gotos will come back in style :)

 

[kiana]

Computed gotos will come back in style :)

 

Probably not on punch cards, though :P

[Mike in SA]

Agree with everything here.  I find errors in my own proofs all the time.  If I were to publish one, I would want to spend weeks poring over it.

 

It's a bit like writing an essay.  How do you know it's "right?"  For the most part, you just sort of know when you have it right.  It takes lots of practice and review time. 

 

Ultimately, to be sure about your proof, there is no substitute for a second or third reviewer.

[mom2bee]

Can I get some feedback for this attempt at a proof. This is homework, so I don't want the explicit answer per se, but I need another set of eyes on it, I just want to know if it makes sense, is poorly written, etc. I have a lot of trouble expressing things mathematically. I failed my 2nd quiz for "wordiness" and lost points on my 3rd quiz for "insufficient explanation".

.

The Problem:

Prove that if h² is even, then h is even

The setup

a--an even number is any number that can be written in the form of 2k where k is in Z (integers)

b--let h be some even number so that h can be written in the form of 2k

c--h²= h * h = 2k * 2k = 4k = 2(2k)....[_]

 

So, is that it? Is that complete? Does it look logical? Too little? Too much?

[Cosmos]

Can I get some feedback for this attempt at a proof. This is homework, so I don't want the explicit answer per se, but I need another set of eyes on it, I just want to know if it makes sense, is poorly written, etc. I have a lot of trouble expressing things mathematically. I failed my 2nd quiz for "wordiness" and lost points on my 3rd quiz for "insufficient explanation".

.

The Problem:

Prove that if h² is even, then h is even

The setup

a--an even number is any number that can be written in the form of 2k where k is in Z (integers)

b--let h be some even number so that h can be written in the form of 2k

c--h²= h * h = 2k * 2k = 4k = 2(2k)....[_]

 

So, is that it? Is that complete? Does it look logical? Too little? Too much?

 

You proved the converse. The problem asked you to prove:

IF h^2 is even, THEN h is even.

 

Here's what you proved:

IF h is even, THEN h^2 is even.

 

See in step b, where you said "let h be some even number . . ." You are assuming the conclusion rather than the given premise.

 

By the way, has your teacher instructed you to label your steps a, b, c, etc.? That is not standard practice in writing proofs, so unless it's something your teacher requires, I would leave those labels out.

[mom2bee]

You proved the converse. The problem asked you to prove:

IF h^2 is even, THEN h is even.

 

Here's what you proved:

IF h is even, THEN h^2 is even.

 

See in step b, where you said "let h be some even number . . ." You are assuming the conclusion rather than the given premise.

Oh, wow, I feel like an idiot! Okay, thank you for that. I'll fix it stat!

 

By the way, has your teacher instructed you to label your steps a, b, c, etc.? That is not standard practice in writing proofs, so unless it's something your teacher requires, I would leave those labels out.

No, I was just trying to organize my thoughts on the screen, I didn't (and don't) use those labels on my work in class.

 

[Cosmos]

You aren't an idiot. That's no way to talk. :) It's a very common mistake when students are first learning to write proofs.

[mom2bee]

Cosmos, you gave me an idea. Is this fair? If I put  the problem in the form of a logic statements, and work it out, I get that

P --> Q = ~Q --> ~P. (~ is the negation)

 

So that the argument "if P then Q" can become "If NOT Q, then NOT P"

So for my purposes:

P is the statement: H² is Even

Q is the statement: H is even

 

~Q is the statement:  H is odd

~P is the statement: H² is odd

 

So, I tried it again from this place and got...

 

Let H be an odd number

H = 2k + 1

H² = H * H = (2k + 1) * (2k + 1) = 4k² + 4k + 1 = 2(2k² + 2k) + 1 (**should I factor out 2k instead of 2? What is considered better form?**)

and thus H² is odd.

 

So that I have if H is not even then H² is not even either. Or ~Q --> ~P

[_]

[Cosmos]

Yes! That's perfectly lovely. There's a small error in your factoring which I'm sure you can find easily, but I think factoring out just the 2 is the clearest way.

 

Have you learned the term for (not Q -> not P)? It's called the contrapositive of (P -> Q). And this is a perfect example of a situation for which it's easier to prove the contrapositive than the original statement.

 

The only thing I would add is that instead of starting with "Let H be an odd number", you might add a sentence that indicates you are planning to prove the contrapositive. That way a person reading the proof would understand why your next step is to "Let H be an odd number . . ."

[mom2bee]

Yes! That's perfectly lovely. There's a small error in your factoring which I'm sure you can find easily, but I think factoring out just the 2 is the clearest way.

 

Have you learned the term for (not Q -> not P)? It's called the contrapositive of (P -> Q). And this is a perfect example of a situation for which it's easier to prove the contrapositive than the original statement.

 

The only thing I would add is that instead of starting with "Let H be an odd number", you might add a sentence that indicates you are planning to prove the contrapositive. That way a person reading the proof would understand why your next step is to "Let H be an odd number . . ."

Thank you! I couldn't remember that word, but yeah, I took a course in discrete math about a year back. Its the 1st lesson on the 1st day and I'd pretty much forgotten it until you mentioned converse! Thank you for the help. I appreciate it!

[mom2bee]

This is not homework, but it is from my Advanced Calculus book, we were told that we could skip it, but if we want to discuss it, we can go to the teachers office hours and discuss it with him. But I have an appt. and can't go see him. Anyone want to hash this out with me

 

Find the error: "All positive integers are equal to each other."

Proof:

i) 1 = 1

ii) Suppose that all integers, up to and including n are equal. Then n  = n - 1.

    Adding 1 to both sides, we get n + 1 = n. Since n is equal to all lower numbers, so is n =1.

 

Clearly, obviously, this is not true.

Should this type of question be answered with a counter example? So should I respond with something like: "Take the case n = 3. Then is  3 = 2? No, 3 =!= 2 Therefor the premise all positive integers are equal to each other is faulty."?

 

Or should I respond to this in English sentences, just stating why the premise is unsound?  So should I respond: The premise "All positive integers are equal" directly contradicts Peano Axioms ii and iii, which state ii) that each natural number has a unique successor and iii) that if two natural numbers have the same successor, then they are the same.

 

What is the best way to respond to this type of question?

 

We are expected to somehow just "know" how to write mathematics formally, but it is never taught--each professor says that you learn it from taking the Real Analysis classes, but the Real Analysis professors just keep docking students grade based on bad form, saying that you learn from experience but I'm not learning anything, I'm just losing points!  I'm really struggling with knowing how to write this stuff. I either get things like "-10, insufficient explanation" or " -15 too wordy"  "-10 This is not ENG 101, no need for essays" When I go to office hours, my teacher writes proofs in 1 or 2 lines and says that all that needed, but if I do a simple proof in 2 lines then he asks for "more detail"

 

Anyone?

[Cosmos]

No, they don't want a counterexample. They want you to find the error in the proof. Obviously there must be one!

 

Now, I'm going to assume that you have studied mathematical induction. If you have not done that yet, then I think this problem is too difficult to do.

 

So, think about how mathematical induction works. First you prove the statement for n = 1 (or some other base case). Then you *assume* it to be true for all integers up to some arbitrary n and *show* that it's true for the case n+1.

 

Well, this proof looks like it's doing just that. To see what's wrong, try applying the inductive step to a specific number, say n = 7. Then, it would go like this:

 

(1) ASSUME that all positive integers less than or equal to 7 are equal.

(2) SHOW that all positive integers less than or equal to 8 are equal.

 

What do you think? First assume as in (1). Never mind how anyone could ever prove that to be true. Just take as a given that 1 = 2 = 3 = 4 = 5 = 6 = 7.

 

Does it then follow that 1 = 2 = 3 = 4 = 5 = 6 = 7 = 8? Yes, it does! Since 6 = 7 in our assumption, then 6 + 1 = 7 + 1, so 7 = 8, and so all of them are equal again.

 

Okay, so that does seem to work as a valid argument when n = 7. That tells you that the error must be earlier in the integers, because if you were able to prove it up to n = 7, then it would keep working for all the other positive integers 8, 9, 10, etc.

 

Go all the way back to the first inductive step. The statement was proved for n = 1, so the first inductive step is when n = 1 and n + 1 = 2. Here's what it would look like:

 

(1) ASSUME that all positive integers less than or equal to 1 are equal to each other.

(2) SHOW that all positive integers less than or equal to 2 are equal to each other.

 

Does that follow? This is where the logic breaks down. The base case only tells you that 1 = 1. That doesn't give you any way to prove that 1 = 2, which is what you need to do. The "proof" says that n = n - 1 by induction, but in this case n - 1 = 0  and our base case did NOT say that 1 = 0. It only said that 1 = 1.

 

So to be precise the error in the proof is in this statement:

 

 

Suppose that all integers, up to and including n are equal. Then n  = n - 1.

 

 

First of all, it should say "suppose that all positive integers". Secondly, the statement n = n - 1 is only valid when n ≥ 2. So induction breaks down at the very first inductive step.

[kiana]

You will find the same error here: http://en.wikipedia.org/wiki/All_horses_are_the_same_color

 

 

[Cosmos]

Oh good grief. I should have guessed there's a write-up somewhere on the web and saved myself all that typing. I suppose I should have procrastinated on writing my post because kiana was coming with a quick and easy link. Of course, I was typing up that post in the first because I was procrastinating on other things I should be doing here at home. :lol:

[kiana]

Oh good grief. I should have guessed there's a write-up somewhere on the web and saved myself all that typing. I suppose I should have procrastinated on writing my post because kiana was coming with a quick and easy link. Of course, I was typing up that post in the first because I was procrastinating on other things I should be doing here at home. :lol:

 

Well, you included a lot more information than I did :D

 

Now, bee, you've been struggling with proofs this semester (this is VERY VERY common in the first proof class) -- you might consider one of the free textbooks on proof here: http://aimath.org/textbooks/approved-textbooks/

 

I think some of the notes on writing and organizing proofs in Sundstrom's book might be especially useful.

 

Also, when they tell you your proofs are wrong, is there a "model solution" for you to compare to? I write these for my students when more than a certain percent of the class makes a terrible hash of a problem. Also, do you have a study group?