Proof mathematics subjects at University

[chronon]

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?

But eventually you have to appeal to something being obvious: http://www.lewiscarroll.org/achilles.html

 

[Doodle Bob]

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?

Actually, that's why they teach (or are supposed to teach) logic and truth tables in high school (and later on in college). I don't know about most other states, but these topics are still in Ohio's mathematics standards for K-12 education.

 

[mathwonk]

I am surprized that truth tables are on the high schools standards, and impressed, at elast if they get taught.

are they not only in the standards but also actually taught there? in my state, such lists of standards are sometimes very overly optimistic lists of everything some one thinks will look good.

but in my state the teachers are not at all prepared to teach most of what is on the standards. in fact even the booklet designed to help them prepare for the teachers' test is written by people who also do not understand most of the topics.

(I know, I reviewed it as a professional consultant.)

of course I am sadly aware my southern state is a weak example. I am scheduled to teach truth tables to college juniors this fall, and in the past such students have never seen them before.

 

[honestrosewater]

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.

Which is the reason for setting out the rules: there's no arguing over what a set 'actually' is - a set is whatever the definitions or rules say it is. IMO, what you mean is a matter of philosophy, not logic.

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.

I guess that's just what happens when you formalize the rules that you're already using. I gather you don't think that formal logic is unnecessary, but maybe you think it is a necessary evil?
Those .\overline{9} = 1 threads may serve as an example. You first try to explain things through common sense and mathematical reasoning and resort to the formalism and foundations when nothing else works?

 

[honestrosewater]

But eventually you have to appeal to something being obvious: http://www.lewiscarroll.org/achilles.html

Actually, that's a good example of why you need to just set out the rules in the first place. Then if you want to question those rules, you may do so in another system.

 

[matt grime]

I gather you don't think that formal logic is unnecessary, but maybe you think it is a necessary evil?

evil? not at all; i find a logic a very useful and interesting subject and have been even known to read things on O-minimal structures and listen to talks by logicians.

I just think it unnecessary to teach logic to people upon entering university. the basics, all that is needed, should be naturally obvious and even if not they will become apparent quickly if we teach them properly what a proof is.

but then i may be expecting too much of people when i think that anyone doing a degree in mathematics ought not to be a moron: why on Earth should I have to prove to someone that A implies B and B implies C implies A implies C? If you do A, B happens, if B happens then C happens, thus if you do A C happens, come on, it's not rocket science. i mean when ever in mathematics do you ever have to prove anything by appealing to some ridiculous complicated statement being a tautology? seriously, beyond not not A is A, and A implies B being obviouly not(B) implies not(A), as well as the associativity of implication what on Earth do we need from logic in order to start teaching matheamtics? perhaps a simple idea of negation of statements and a little quantifier stuff, but again it should be obvious that in order to show that for all X, P(X) implies Q(X) is false by finding a counter example, or more importantly, it should be obvious after one example in their course that this is how it can be done.

there is nothing at this level of utility that needs to be treated as a speciality of logic, it is just elementary maths that you pick up quickly. drawing attention to it is not necessary. i still get students who don't understand that writing out a truth table for all possibilitise of A and B doesn't prove that A implies B in any particular case.

The difficult and interesting stuff is not teachable to people who are struggling to comprehend this weird thing that is the first year of degree level mathematics.

I would no more give an deep introduction to groups rings and modules to a first year as a prelude to explaining what euclid's algorithm than I would enter a deep discussion on predicate calculus with someone before explaining what a sequence is and what it means for it to converge (this is not a vacuous example and is exactly what I am required to teach to my first year tutees).

 

[roger]

Regarding the associativity of implication, matt referred to something which has nothing to do with maths, by saying if you do a , b happens etc..and implied it was easy to understand.

Its actually no more obvious than why 1+1=2 in my opinion

 

[Eratosthenes]

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?

You should be comfortable proving things different ways. Here are three different ways to prove the same thing that you will find extremely useful I think. I'll try to explain them as best as I can. A good book would be better of course!

Prove that if x is an even integer then x + 9 is odd.
For the examples below, let A and B denote the following.
A: x is an even integer.
B: x + 9 is odd.

Method 1(sometimes called direct proof)
If A holds then B must follow. So we are showing that if x is an even integer, then x + 9 must be odd.

Proof
Suppose x is even. Then x = 2k for some integer k. Then x + 9 = 2k + 9 = 2k + 8 + 1 = 2(k + 4) + 1. Since k + 4 is an integer(you can state reasons if you want here, closure etc, doesn't matter I think), then x + 9 is odd.


Method 2(sometimes called proof by contradiction or indirect proof)
We assume that it is not true that if A holds, then B must follow. Then we reach a contradiction to show that our assumption was false, which means the negation of our assumption is true.

Proof
Suppose x is even and x + 9 is even(this is the negation of "if A, then B").
Then x + 9 = 2k for some integer k. Then x = 2k - 9 = 2k - 10 + 1 = 2(k - 5) + 1, where k - 5 is an integer. Thus x is odd. Now we have a contradiction. So the negation of our assumption must be true, thus x + 9 is odd.


Method 3(sometimes called proof by contraposition)
Here we use the contrapositive of "If A, then B." Which is: If not B holds, then not A must follow. So we are trying to show that if x + 9 is not odd, then x is not even. This is the same as trying to show that if x + 9 is even, then x is odd.

Proof
Suppose x + 9 is not odd, hence even. Then x + 9 = 2k for some integer k. Then x = 2k - 9 = 2k - 10 + 1 = 2(k - 5) + 1, where k - 5 is an integer. Thus x is odd.

If you ever run into something like prove A if and only if B, where A and B are statements you need to do two things.
1. You must show that if A holds, then B must follow.
2. You must show that if B holds, then A must follow.


The most useful example is method 1. However some proofs are easier with other methods, so it's good to be familiar with all the them. Wikipedia should have better explanations of each method and your number theory book should provide lots of practice:)

Induction is another method you should be really familiar with if you are taking Number Theory. A good exercise in proof by contradiction is to prove the Principle of Mathematical Induction. Anyways I hope there are no really bad mistakes in those examples, the last thing I want to do is confuse you more. Goodluck to you!

 

[matt grime]

Let me see, so if it is true that when i press this here button a bell rings, and if it is true that when the bell rings my pavlovian dog drools, then why is it not obvious that pressing the button ends up with me having a saliva dripping pavlovian dog?

 

[roger]

matt, wouldn't you say this is heading towards philosophy rather than having anything to do with maths ?

I recall, you yourself explicitly advised me to disregard and steer clear of physical examples or referring to the 'real' world .

And I can't say the example above is obvious to me actually.

 

[matt grime]

It has nothing to do with philosophy, and it is perefctly valid to use real world examples since we are fixing what rules of deduction we will use in maths which are based upon our experiences in the real world. In fact we are discussing exactly what it is necessary to specify in our system of logic. the choices for that will be based upon what is 'obviously true'. just as it is perfectly reasonable to look at some real phenomenon to figure out what it is we wish to model, say.

We are not considering maths of the kind my advice referred to and in the sense in which the advice was given and you ought to realize that.

 

[roger]

Well if it is to be based upon what is 'obviously true', then that again is something debateable.

And in any case, what do you define as the real world ?

this is why I said it could be heading towards philosophy.

And when we do look at phenomenon, and try to model it, we run into trouble anyway, so it goes to show, looks can be deceptive.

 

[honestrosewater]

matt,
I think I finally understand you, and you've changed my mind about what is appropriate at which level. Since people often post questions about adapting to proofs, I think it would be nice to have a list and brief explanation of the useful rules for them. Do you want to add any more rules to your list?

roger,
I don't see what you're getting at. In matt's example, the subject matter of the atomic propositions has no bearing on the argument's logical validity, which is what he was highlighting.

Let me see, so if it is true that when i press this here button a bell rings, and if it is true that when the bell rings my pavlovian dog drools, then why is it not obvious that pressing the button ends up with me having a saliva dripping pavlovian dog?

P = I press the button
Q = The bell rings
R = Pavlov's dog drools

If P, then Q. If Q, then R. Thus, if P, then R.

Does it make sense to you that if x = y and y = z, then x = z? How about if x > y and y > z, then x > z?

 

[matt grime]

Of course I should have said transitivity when i was trying to illustrate my examples.

Also, roger, when I say something in this argument is "obviously true" I mean "I obviously want it to be true because that is nice" or soemthing. I don't mean it has an easy proof, indeed it has no proof really since it is one of those axioms we are going to have in our system.

 

[honestrosewater]

Also, roger, when I say something in this argument is "obviously true" I mean "I obviously want it to be true because that is nice" or soemthing. I don't mean it has an easy proof, indeed it has no proof really since it is one of those axioms we are going to have in our system.

Well, not to confuse things - you're talking about math and I about logic, but here are the proofs in two natural deduction systems, with minimal explanation. I'm quite curious to see if they make sense to anyone.

In the system that I'm used to, the argument to be proven is actually one of the rules, so the proof is quite simple (anyone can look up the names I use here - Edit: there are explanations of them further down the page):

1) P -> Q [premise]
2) Q -> R [premise]
3) P -> R [1, 2, Hypothetical Syllogism/QED]

This system has no conditional proof (you can't introduce assumptions out of nowhere) and I can't see a way to prove the exact argument without the HS rule, so I'm adding another premise: P.
1) P -> Q [premise]
2) Q -> R [premise]
3) P [premise]
4) Q [1, 3, Modus Ponens]
5) R [2, 4, Modus Ponens/QED]
This just shows that (P -> Q) and (Q -> R) connect in such a way that if P is true, then R must also be true.

The other system, which I'm not familiar with, does have a conditional proof rule, so I can prove that [((P -> Q) & (Q -> R)) -> (P -> R)] is a tautology by deriving it from nothing, i.e., the empty set of premises (and hopefully not make any technical blunders).
1)) (P -> Q) & (Q -> R) [hypothesis - I assume this in order to derive the tautology, note that it is nested]
2)) P -> Q [1, Conjunction Elimination]
3)) Q -> R [1, Conjunction Elimination]
4))) P [hypothesis - I assume this in order to derive (P -> R), nested again]
5))) Q [2, 4, Modus Ponens]
6))) R [3, 5, Modus Ponens]
7)) P -> R [4, 6, Conditional Proof]
8) ((P -> Q) & (Q -> R)) -> (P -> R) [1, 8, Conditional Proof/QED]

(I edited some unnecessary steps I used the first time.) This says the same thing: Given (P -> Q) and (Q -> R), if we assume that P is true, (P -> Q) gives us Q. Now that we have Q, (Q -> R) gives us R. So (P -> Q) and (Q -> R) give us (P -> R). Pretty straightforward, I think. The formalism may turn some people off, but it was comforting to me to see everything laid bare. Of course, I'm quite a strange cookie.

 

[roger]

honestrosewater, if the subject matter has no bearing on the logical validity, then why did matt pick that particular example ?

And what relevance does if x=y , y=z then x=z have to this ?

 

[matt grime]

I picked that example for no particular reason. Any example would have done:

If i have a bad fall down the stairs then i break my leg. If I break my leg I go to hospital, if i go to hsopital with a broken leg they;ll put it in plaster, hence if I hava a bad fall down stairs I will end up with my leg in plaster.



If you can't see what honestrosewaters transitivity of equality has to do with it, or any transitivity tehn can i ask you to go away and think abuot this carefully?

another examplei s that i can travel by train from X to Y and I can travel by train from Y to Z then I can travel by train from X to Y.

 

[roger]

but surely isn't there a difference between the transitivity of equality and that of logic ?

they are two separate issues ?

(that should be from x to z not x to y.)

I have referred to your website, and read your thoughts on these matters, you have asserted that maths has nothing to do with the real world, so I simply can't understand why now you chose to appeal to a real world example to demonstrate a mathematical concept ?

 

[matt grime]

i am not demonstrating a mathematical concept. your arguments seem quite specious and merely designed to provoke me into response. objects in mathematics are idealized, that doesn't mean that we cannot reason with them as if they were part of the real world, for heaven's sake, any more than results in combinatorial graph theory cannot be applied to assigning lecture times.

in any case you seem to be entirely mising the point of this argument which is that common sense is all that is requierd to understand what deductive reasoning is required to start doing mathematics. ignore the maths for one second, do you understand simple deductive reasoning in the eral world? If i buy that car I will leave myself with less than 1,000GBP in the bank, if I have less the 1,000 GBP in the bank then I can't afford that cruise in the caribbean, hence if i buy the car i can't go on the cruise. i am making no assertions about mathematics at all, am I? or claiming to? now, why when we start thinking of mathematics must i use a different set of deductive rules? (we may wish to as the constructivists might argue) but that isn't what we're talking about. we are wondering how it is that people entering university are unable to make simple logical deductions be they about mathematics or anything else it would appear if your responses are anything to go by.

 

[meckano]

I didn't read all posts, please excuse repetition.
I find you have to care.
I love math.s and did well in school, but could have done better if I cared about it.

Try this:
Create a situation where you want THE answer on the first try.
- If you don't get THE answer, imagine catastrophe; Public embarrasment, Mechanical failure/costs... whatever.
So, you need to prove to yourself that it is the right answer. You're in the woods, no internet, no towns, nobody.
I had found that it is What I am proofing with that I did not understand completely.
I had to go over what I did not understand and IT's proofs.
Don't stop till you get, but you won't stop cause you care.

I consider the above to be the definition of: learn by rote, aka: keep redoing it till you get it.
- Just keep looking at if from different angles.
Like in my post in 4 dimensions, I like 1, so I checked to see how a circle with a diameter of 1 is related to other circles. (I was lucky to have heard about the power of 1 in math, somewhere, some time ago.)
- Grab on to a reason to learn, a mathematical reason for maths. So wanting to teach it won't be a helper in understanding math.s, although it will be a helper to keep you going on the days you walk around scratching your head wondering if you'll ever Get-it.

:) hope this helps.