Proof mathematics subjects at University

[pivoxa15]

I have done all the first year mathematics subjects at University and now doing some higher level ones such as a couse called Number Theory - although this course is only an introduction to the subject, I still find it tough mainly from following the proofs in the course. In the past, I have got through math pretty much by computations but now I realize that proofs are much more significant in mathematics so I really want to master it.

The trouble is, I find it difficult. Anyone have any advice to how I can become more comfortable with them? Is it simply the case of practice or are there certain methods of learning?



Thanks

 

[quasar987]

If I were you, I wouldn't worry if you can't follow the proofs of your teachers. The thing with doctors and older teachers in general*, is that they forgot where they had difficulties when they were learning the subject, ans thus don't emphasize the important points. For them, their proofs are self evident and they have trouble imagining that they are not cristal clear to everyone. They tend to skip explaining the logic btw each step of their proof, which makes each of them kind of little puzzles to solve for the students. Of course, this solving cannot be done LIVE in the course, so after a while, most students are loss and just copy what's on the blackboard mindlessly.

Of course you have better chances of sucess trying to follow in class if you've read on the subject before class, but this is almost always impossible to do given the overloaded schedules we have.

*This is of course only how I perceive things based on my own life experiences.

 

[matt grime]

If I were you, I wouldn't worry if you can't follow the proofs of your teachers. The thing with doctors and older teachers in general*, is that they forgot where they had difficulties when they were learning the subject,

i doubt any of them had any difficulty in mastering proofs in basic courses, which may be more of a problem.

in any case, you aren't supposed to understand all proofs when you first read them and if you think you ought to be able to then you will only ever have headaches. you need to go away, read, reread, write out the notes again (if not rewrite the rewrite) and attempt to understand the logic yourself.

It is primarily a case of practising and noting that there aren't that many proofs available to you. For instance, if you are doing a problem in number theory and it starts: suppose x and y are coprime integers... then it is almost certain that if you start by noting that this implies there are integers u and v such that ux+vy=1 you will probably find the answer quite quickly. (basic analysis proofs are even easier though few undergraduates ever believe me).

it is also important to note the difference between something being an 'if' statement and an 'if and only if' statement (aka 'iff').

 

[mathwonk]

My guess is that many students have never studied basic mathematical logic.

Proofs use these fundamental principles over and over.

e.g. to prove that a statement like: " every continuous function is differentiable" is false, it is adequate to find a single continuous function which is not differentiable.

on the other hand, to prove that every differentiable function is continuous, one must show how the property of differentiability forces the property of continuity.

to show that every continuous function on a closed finite interval is bounded, it is enough to show that an unbounded function on a closed finite interval cannot be continuous.

In my own personal case, I have not forgotten the difficulties involved here, but was lucky enough to have studied logic in high school from a basic book on foundations of math then used in colleges, "Principles of Mathematics" by Allendoerfer and Oakley.

This, "leg up" enabled me to start college calculus on the right foot, but it was still very hard.

I do tend to forget that many students have never learned logic, as it seems so intuitive. E.g. the student who says that "I'll jump off the 10 meter board if you will", thinks he is telling the truth even if neither jumps off.

But that same student claims not to understand how a mathematical statement whose hypothesis is false can be true. Why is this so common?

 

[honestrosewater]

Maybe proving some things you already know are true would help you become more comfortable with the process. For instance, you're already familiar with the real field, so you could try to prove some basic things about it. You can find the field axioms several places:
http://mathforum.org/library/drmath/view/51925.html
http://mathworld.wolfram.com/FieldAxioms.html

Using those, try to prove the statements in sections 4 and 5:
http://www.math.uiuc.edu/~rezk/number-systems.pdf

Maybe someone else has better resources. These are just the first ones I found in a quick search.

I just happened upon a http://www.math.uchicago.edu/~eugenia/proofguide/proofguide.pdf .

 

[mathwonk]

for instance to prove every function cont on a finite closed interval is bounded, one might begin by saying: " suppose it is not bounded.." This already puzzles some students.

The basic rule that "A implies B" is true if anfd only if the statement "notB implies notA" is true, is not familiar to them. It was the old proof by contradiction that used to be taught for thousands of years in euclidean geometry in high school, where most profs studied (some of us thousands of years ago).

Diatribe begins roughly now:

But today's brilliant pedagogues in high school have replaced this kind of reasoning with vacuous courses on computation of areas of circles, or AP courses in which people try to memorize all the answers to some standard test, rather than learning how to reason.

Older college profs are perhaps to some extent still slightly unaware of how empty is the current high school curriculum in the US.

Even AP courses for example focus on memorizing factual content rather than understanding principles for solving problems.

On a typical AP AB calc test a few years ago, there was not a single proof question.

So as college professors have spent 20-30 years teaching, the high schools have spent that time watering down the high school math curriculum, so that entering students have nothing like what used to be standard knowledge.


The fundamental prerequisite for doing a proof is to be able to understand:

1) what does the statement to be proved actually say?

2) what would it mean for that statement to be true, or false?


how can a student grasp these things if he/she cannot even write a sentence with a verb in it? this is a real challenge for some of our charges. our stats show that scores in our basic math courses are correlated not with math SAT scores, but with scores on verbal SAT. So which SAT has been targeted for refurbishing? The verbal SAT, from which the most useful section, namely analogies, is to be removed I understand.

It is very difficult for us to keep up with the demands of teaching new students when the traditional background is watered down in high school almost every year and replaced by worthless lists of topics to be covered, such as on AP tests.


Teachers, please don't teach high school (or other) students to memorize particular dates, formulas, or other facts, show them how to understand the statement of a problem, and then how to reason from that understanding towards a solution.

Finally teach them to write up that solution in complete sentences.

Then heaven will come on earth, and all our students will be able to do proofs.

And perhaps they will then observe that Hans Blick was right after all. :zzz:

recommended reading: Harold Jacobs' Geometry, a brilliant, amusing, well illustrated, well written, deeply substantive, high school text.

 

[honestrosewater]

Maybe more than anything else in logic, learning - and practicing with - a natural deduction system could help in writing proofs and discovering some common proof techniques. These systems are designed to follow people's natural reasoning processes, and they're very easy to learn. It's just basic 'what can you infer from what' stuff. I don't think that mindlessly applying rules can get you very far with these systems, rather you actually need to understand what you're doing. But maybe others here have had bad experiences with this.?

I like the system in Copi & Cohen's Introduction to Logic, which should be easy to get ahold of (check your library). There are also several places on the internet that present a natural deduction system:
http://tellerprimer.ucdavis.edu/
http://www.mathpath.org/proof/proof.inference.htm
http://www.danielclemente.com/logica/dn.en.html
http://en.wikipedia.org/wiki/Propositional_calculus#Inference_rules

These systems work like so:
You're given some inference rules and possibly some replacement rules. For example, some Inference Rules:
Modus Ponens: Given P implies Q and P, you may infer Q.
Reductio ad absurdum: If you can derive Q and not Q while assuming P, you may infer not P.
Replacement rules:
You can replace any instance of P implies Q with (not P) or Q and vice versa.
For each proof, you're given a conclusion and a (possibly empty) set of premises, and you must choose which rules to apply in what order in order to derive the conclusion. Obviously, it can end up taking a very long time to derive your conclusion if you just randomly choose and apply rules.

 

[matt grime]

my oft stated displeasure in over teaching logic (not that i disapprove of logic at all, or foundational maths) comes from the fact that the only necessary skill is to be sensible, and that learning when a convoluted statement is a tautology has no bearing on ever proving anything except in formal logic. we shouldn't need to teach at university level that to show A implies B is false it suffices to find a case when A is true and B is false. That should be patently obvious to anyone doing a degree in maths. Besides which, that doesn't ever actually help a student find such a case which is what is important.

 

[honestrosewater]

Perhaps just going through the list of rules and understanding why eash is valid would be helpful for someone who hasn't bothered to give them much thought? It would at least make their 'common sense' reasoning explicit.

 

[matt grime]

would it? i obtained all my maths qualifications up to masters level and was well into my phd before it came to my attention that A implies B is the same as not(A)\/B. can't say it bothered me that i'd never thought of that until required to teach it.

 

[ComputerGeek]

(basic analysis proofs are even easier though few undergraduates ever believe me).

I believe you :-)

my basic analysis class was so much easier (in hindsight) than some of the proof I did in Abstract Algebra and I will be taking basic Number Theory this fall. I am waiting with ambivalence at this time.

BTW, how long does it take to get the amount of experience to recite information as you do? I have not had calculus in almost 2 years and I have gotten very rusty with it and fear encountering some of the ideas again in grad school (I am sure it will come back to me, but still)

 

[ComputerGeek]

Teachers, please don't teach high school (or other) students to memorize particular dates, formulas, or other facts, show them how to understand the statement of a problem, and then how to reason from that understanding towards a solution.

Finally teach them to write up that solution in complete sentences.

I plan to teach problem solving, come hell or high water. what is interesting is that there is a strong movement in public schools now that focus on getting students to think critically and get better at comprehending information. that is something that math is uniquely qualified to introduce to students due to the required discipline of thought and reasoning that math requires.

 

[matt grime]

BTW, how long does it take to get the amount of experience to recite information as you do? I have not had calculus in almost 2 years and I have gotten very rusty with it and fear encountering some of the ideas again in grad school (I am sure it will come back to me, but still)

i can probably only recite elementary analysis proofs because i teach them every year; i have no interest in analysis anymore apart from that. however, years of experience makes you realize how few methods of proof you need. even the great hilbert is alleged by one author whose name escapes me to have reused the same 6 ideas to prove his most astonishing ideas.

however, unlike the rest of these forums, the questions asked here are quite elementary to a mathematician, and i am not the first to mention this difference between the maths forums and the physics, chem, or biology forums; this i think reflects two things - the US education system wherein lots of maths is taught as a background for all science subjects and it is students in those classes who post here predominantly, and the fact that advanced mathematics is a mystery even to those who are practitioners in its dark arts. you get few questions here of the level of a US graduate course.

 

[honestrosewater]

would it? i obtained all my maths qualifications up to masters level and was well into my phd before it came to my attention that A implies B is the same as not(A)\/B. can't say it bothered me that i'd never thought of that until required to teach it.

I don't know - I'm not very far ahead of the OP. That's why I was careful to say maybe and ask for others' opinions. But for your example - how then do you reason that (P -> Q) <=> (~Q -> ~P)? Isn't that a helpful thing to know? I think it's easy to realize that they are both equivalent to (~P v Q). Also, if you're trying to prove a statement of the form (~P v Q), and you're already familiar wth proving (P -> Q) via a conditional proof, you would know right away how to approach your proof. To someone who's just starting out, this kind of stuff might not be so obvious. A conditional proof may not be the first thing that comes to mind when someone sees (~P v Q).

 

[ComputerGeek]

i can probably only recite elementary analysis proofs because i teach them every year; i have no interest in analysis anymore apart from that. however, years of experience makes you realize how few methods of proof you need. even the great hilbert is alleged by one author whose name escapes me to have reused the same 6 ideas to prove his most astonishing ideas.

however, unlike the rest of these forums, the questions asked here are quite elementary to a mathematician, and i am not the first to mention this difference between the maths forums and the physics, chem, or biology forums; this i think reflects two things - the US education system wherein lots of maths is taught as a background for all science subjects and it is students in those classes who post here predominantly, and the fact that advanced mathematics is a mystery even to those who are practitioners in its dark arts. you get few questions here of the level of a US graduate course.

so, basically the more you teach it the more you know it. well, I do not feel so inadequate then at this point in my life.

 

[pivoxa15]

Thanks for your suggestions.

A thing I noticed was notations. Maybe most of my trouble comes from not fully understanding what the notations mean which hinder my understanding of the proof. And one small misunderstanding or lack of understanding here and there in a proof could be disastrous, leaving me in total confusion and frustration.

 

[honestrosewater]

A thing I noticed was notations. Maybe most of my trouble comes from not fully understanding what the notations mean which hinder my understanding of the proof.

Which notations?

 

[matt grime]

I don't know - I'm not very far ahead of the OP. That's why I was careful to say maybe and ask for others' opinions. But for your example - how then do you reason that (P -> Q) <=> (~Q -> ~P)?

Easily: if I know that P implies Q, and I know not(Q), then not(P) must follow, otherwise we must have P, but that would imply Q, contradiction since we have not(Q). Hence P implies Q means that not(Q) implies not(P), the reverse implication now follows by symmetry. This is just the reason why we declare ordinary deductive logic to have the rules it does.

 

[honestrosewater]

Easily: if I know that P implies Q, and I know not(Q), then not(P) must follow, otherwise we must have P, but that would imply Q, contradiction since we have not(Q). Hence P implies Q means that not(Q) implies not(P), the reverse implication now follows by symmetry. This is just the reason why we declare ordinary deductive logic to have the rules it does.

Where did you come up with the rules that you used? Did you ever doubt that your 'natural' reasoning was correct? I mean, I'm not doubting you; I'm curious. How can someone do math without having the rules clearly set out ahead of time?

 

[arildno]

Where did you come up with the rules that you used? Did you ever doubt that your 'natural' reasoning was correct? I mean, I'm not doubting you; I'm curious. How can someone do math without having the rules clearly set out ahead of time?

Actually, the rules for which inferences is to be regarded as logically valid should be part of the explicit set of axioms within the particular maths you're doing. It's just that most won't bother to list them; I guess..

 

[honestrosewater]

Actually, the rules for which inferences is to be regarded as logically valid should be part of the explicit set of axioms within the particular maths you're doing. It's just that most won't bother to list them; I guess..

Yes, good point. So am I the only one who finds that it's easier - and puts you on firmer ground - to just state the rules that you're allowed to use?

 

[arildno]

Yes, good point. So am I the only one who finds that it's easier - and puts you on firmer ground - to just state the rules that you're allowed to use?

A good point as well!

However, I think a convention has established itself that logicians state&study sets of rules of inference, whereas mathematicians just use the "natural" system, unless otherwise specified.

I might be wrong on this, of course; the math wizzes will know better.

 

[honestrosewater]

Well, this isn't directed at matt or anyone else in particular. I just don't understand the idea that people should be left to figure out the rules on their own. If the rules are obvious, it won't hurt to state them. If the rules aren't obvious, they should be stated. ??

 

[matt grime]

Where did you come up with the rules that you used? Did you ever doubt that your 'natural' reasoning was correct? I mean, I'm not doubting you; I'm curious. How can someone do math without having the rules clearly set out ahead of time?

i understand your point, but the rules are the obvious and the minimal ones such as not(not(A)) is A, and that's about it, indeed that is all I used along with the notion of what deduction means. About the only other one we need is A implies B and B implies means that A implies C the associativity of deduction but again that is simple elementary logic we learn possibly even before school.

there are many subtle points in logic, almost none of them is of interest in other parts of 'functional mathematics' by which i mean the notion of practising mathematics to any reasonable level. Another one that we can and should overlook is what a set actually is.


as another example, until i was forced to teach it against my will i had never thought that false implies true is true; i had also never thought it false or for given it one second's consideration at all. It has no bearing on mathematics. If I want to show that f continuous on a compact subset of R implies f is uniformly continuous I would try to show how we can deduce the antecedent from the hypothesis or whatever the language is. I would never consider the case where the antecedent was false.


in short what A implies B is when A is false is not of direct interest in proving that A implies B. It may be if it we are wondering about the converse.

 

[roger]

you mean when a implies b and b implies c ?

 

[roger]

As far as axioms go, how do you know when to stop ?

That is to say, at the most basic fundamental level, we make certain rules but how do we know when to stop proving ?

 

[mathwonk]

well i agree the rules should be stated, but they are stated in traditional geometry courses, but as i said, many high schools stopped teaching that subject in favor of AP calc, a stupid move in my opinion.

that said, the rules are also obvious:

e.g.

if you say "I'll jump off the high board if you do"

Isn't that the same as saying " if I do not jump off the high board, then you didn't either".



or if you say every differentiable function is also continuous"

isn't that the same as saying " any function that is not continuous is also not diffentiable".

or "if I leave the room, then I cannot lock the door from the inside",

is the same as "if I locked the door from the inside, then I did not leave the room".

or "if you make all A's I'll give you a transam" ism the same as "if i do not give you a transam, then you did not make all A's".


These are simple examples of "A implies B" if and only if "notB implies notA",

and they should be relatively obvious upon reflection.

most school sdo teach these rules of logic now, to make up for the poor high school training now provided, but unfortunately they do so in later years, like junior year, instead of freeshman year.

the reason is we have people in engineering schools wanting their students still to ahve in first eyar and not to take up a whole semester rpoviding makeup for missing high school courses,

it is very hard to constantly keep taking up in college the slack provided by our high school system's constant decline, but we are trying.

whats wrong with the student taking some initiaitve and reading a book on the topic, i did that as a high school senior.

we have recommended several already.

 

[matt grime]

that is one of the more important aspects in which logic and foundational mathematics are interesting. no axiom is true in and of itself and we are free to pick whatever we choose as our axioms. if we add the axiom of choice then every vector space has a well defined notion of basis, but then banach tarski is true.


we use whatever we feel necessary, to be honest. try reading gowers' a very short introduction to mathematics.

 

[roger]

so you mean the axioms are relatively true ?

 

[mathwonk]

math is about proving things like if A holds then B does too.

we do not care whetehr A is true or not, that is up to the suer.

i.e. a statements like that is useful to anyone ni whose world A actually is true.

we prove statements involving many axiom sysstems so lots of people in different worlds can use them.

you bring the list of axioms you expect to hold in your world and we will tell you what you can deduce from them for your own use.

like in europe power runs at something 220 volts so people make devices that work that way, in the US power is at 110 volts so we make also devices for them.

different worlds satisfy different axioms systems.