In teaching students how to design and implement proofs, we start them with an extremely structured format. This structure is both a boon and an irritation, since it helps organize the ingredients of a proof, while at the same time making the format of a proof extremely predictable. We have the goldilocks problem of making the form predictable enough, but not too predictable.
If students want to prove something about all natural numbers, they introduce a name for a generic natural number, prove things about it, and then conclude that the results they've proved apply to all natural numbers.
We force them to indent the results they prove about the generic natural number, to emphasize that they are inside the "world" where name they've introduced is a generic natural number.
If they go further and implement a proof about an implication, of the form P implies Q, we have them (at least for a direct proof) assume P is true, indent some more, and then derive Q. Our rationale for this step is that if P were false the implication would be vacuously true, so they only have to worry about the case where P is true.
We expect students who become mature theoreticians will develop their own voice, and write clear, valid proofs that diverge from the proof format that we impose in our course, with its arbitrary order and indentation. We don't know exactly when they will develop this mathematical maturity (some of them may already have), so in the mean time we coerce them into mastering one format for proofs that they, and the course teaching staff, can agree works.
My challenge in communicating the proof format to them is to get most students to the point that they are nodding along with the proof format because they understand it, but stop before they are all nodding off. Goldilocks.
Friday, February 5, 2010
Friday, January 29, 2010
limits and turf
Sometimes we computer science folk get into jurisdictional disputes with our neighbours in mathematics (partly because our neighbours used to be us, depending on how you reckon the heritage of computer science).
A standard dispute is over whether zero is a natural number. From a computer science perspective it seems pretty innocuous: zero is often a useful case to consider in the realm of whole numbers of a non-negative flavour, and it's certainly possible to count things starting from zero (and we do, in many programming languages, with list indices and such). In calculus, though, they insist on excluding this completely innocuous (not to mention small) element from the natural numbers.
Now I find myself a little impatient with the way at least one calculus text presents limits. I think of finite limits (what value does a function "get close" to as it argument approaches some constant) and infinite limits (what does it mean for a function to "get close" to infinity as its argument gets close to some value) as part of the same topic. After finding that these two topics seemed hugely different to my fall semester students, I began checking my calculus texts. Courant and Spivak get around to limits of sequences, and limits that are unbounded, toward the end of their treatment of limits. Most of my students use Sala, Hille, and Etgen, where finite limits are treated in the first hundred pages, and the remaining limit-related topics are spread over hundreds more pages (and months of the course).
My motive for discussing limits is twofold. They provide a good example of mixing statements involving "for all" with statements involving "exists". They are also an ideal starting point for the computer science topic of asymptotics: how do you express the idea that one function grows qualitatively faster than another?
The mixed quantifiers value of limits takes my students back to calculus. For every positive real number epsilon, there is a positive real number delta, for every real number x, if x is within delta of a, then x-squared is within epsilon of a-squared. A true statement, since you get to choose the delta based on the epsilon. However, if you change the order of "for every positive real number epsilon" and the "there is a positive real number delta" you get a falsehood: you can't choose a delta that works for every epsilon.
The same reasoning, with appropriate modifications, works for infinite limits. For every positive real number epsilon, there is a positive real number delta, for every real number x, if x is within delta of infinity, then x-squared is within epsilon of infinity. What does "within delta" mean in this context? It means delta to the right of zero --- being close to infinity is synonymous with being far from zero.
Computer scientists want to talk about how exp(x) grows faster than x-squared. One slick way to do this (so slick that we don't allow our students to use it for a few weeks) is to consider the ratio exp(x)/x-squared. If, for every positive real number epsilon there is a positive real number delta, for every real number x, when x is within delta of infinity (bigger than delta), exp(x)/x-squared is within epsilon of infinity (bigger than epsilon), then exp(x) grows faster than x-squared (it does).
To we CS folk, the same notion of limit is being used in all these cases. It's a bit odd that they wouldn't be closely combined in our students' calculus text.
A standard dispute is over whether zero is a natural number. From a computer science perspective it seems pretty innocuous: zero is often a useful case to consider in the realm of whole numbers of a non-negative flavour, and it's certainly possible to count things starting from zero (and we do, in many programming languages, with list indices and such). In calculus, though, they insist on excluding this completely innocuous (not to mention small) element from the natural numbers.
Now I find myself a little impatient with the way at least one calculus text presents limits. I think of finite limits (what value does a function "get close" to as it argument approaches some constant) and infinite limits (what does it mean for a function to "get close" to infinity as its argument gets close to some value) as part of the same topic. After finding that these two topics seemed hugely different to my fall semester students, I began checking my calculus texts. Courant and Spivak get around to limits of sequences, and limits that are unbounded, toward the end of their treatment of limits. Most of my students use Sala, Hille, and Etgen, where finite limits are treated in the first hundred pages, and the remaining limit-related topics are spread over hundreds more pages (and months of the course).
My motive for discussing limits is twofold. They provide a good example of mixing statements involving "for all" with statements involving "exists". They are also an ideal starting point for the computer science topic of asymptotics: how do you express the idea that one function grows qualitatively faster than another?
The mixed quantifiers value of limits takes my students back to calculus. For every positive real number epsilon, there is a positive real number delta, for every real number x, if x is within delta of a, then x-squared is within epsilon of a-squared. A true statement, since you get to choose the delta based on the epsilon. However, if you change the order of "for every positive real number epsilon" and the "there is a positive real number delta" you get a falsehood: you can't choose a delta that works for every epsilon.
The same reasoning, with appropriate modifications, works for infinite limits. For every positive real number epsilon, there is a positive real number delta, for every real number x, if x is within delta of infinity, then x-squared is within epsilon of infinity. What does "within delta" mean in this context? It means delta to the right of zero --- being close to infinity is synonymous with being far from zero.
Computer scientists want to talk about how exp(x) grows faster than x-squared. One slick way to do this (so slick that we don't allow our students to use it for a few weeks) is to consider the ratio exp(x)/x-squared. If, for every positive real number epsilon there is a positive real number delta, for every real number x, when x is within delta of infinity (bigger than delta), exp(x)/x-squared is within epsilon of infinity (bigger than epsilon), then exp(x) grows faster than x-squared (it does).
To we CS folk, the same notion of limit is being used in all these cases. It's a bit odd that they wouldn't be closely combined in our students' calculus text.
Thursday, January 21, 2010
Mick's quantifiers
There exists a house h in New Orleans, for every poor boy p, they call h the Rising Sun, and h has been the ruin of p.I know it doesn't scan, but I can't help it. I've got this ear-worm of Mick Jagger singing the lyric above. I don't think The Stones ever did a cover of House of the Rising Sun, but I can hear it just as though they did.
I got into this state through an occupational hazard filtered through a perceptual problem. I'll be teaching a topic in logic next week called mixed quantifiers, the sort of thing that happens when you make a statement that some object of one type exists with the property that every object of some (possibly other) type has a property ... and so on. That's the occupational hazard. My perceptual problem is that whenever I hear a phrase like "mixed quantifiers" some auditory circuit runs a simulation of what the world might be like if it were really "Mick's quantifiers." So I can't safely hear phrases such as "mixed metaphors," "mixed company," or "mixed grill" without exploring a whole line of speculative alternative interpretations. Although I'm duty-bound to teach my students about mixed quantifiers, there will constantly be a voice at the back of my head wondering how all this fits in with Mick's quantifiers.
I mean, shouldn't I be asking my students to consider the difference between there being at least one instance of a house that has a terrible effect on every boy (or girl, depending on the version), and the situation where we switch the order?
For every poor boy p, there exists a house h in New Orleans, h is the ruin of p, and h is called the Rising Sun.With this reversed order, each poor boy finds their own particular Rising Sun to torment them, whereas in the first version they all end up tormented in the same place. Wouldn't the world be a better place if veteran blues musicians improvised on riffs that are part of their common culture, and switched the quantifiers around a bit? Surely this is what Trad. Anon. had in mind when he/she/they wrote:
With one foot on existence, the other foot on for all, I'm going back to New Orleans to wear that chain and ball.
Wednesday, January 20, 2010
This week Friday falls on Wednesday.
I've already taught one cycle of this week's material to my Monday evening class, and now I'm trying to make sure my Monday-Wednesday-Friday version of the same material is consistent with it, and preparing other material. So the look backwards function of a blog can be exercised from this vantage point as well as any other.
I learned (or perhaps re-learned) just how thoroughly counter-intuitive the notion of vacuous truth can be this week. The name sounds as though the variety of truth is silly, trivial, or empty, but it's an important technique in logic. If we have an implication that claims that if P is true, then Q follows, then then implication as a whole is true whenever P is false. The notion rests on the fact that an implication claims that Q follows from P, and the only time that "following from" rule is broken is when P is true and Q breaches faith by being false.
In particular, whenever P is false, no breach of faith is possible.
I've often fired up vast and powerful pedagogical machinery to convey this point, being sure to make it several different ways since it registers with different people in differently. There are always some people who resist the first onslaught, so I back the machinery up and take another run at it. Usually nobody is willing to admit that vacuous truth still seems weird after two or three runs at it.
Monday night, though, I presented a particularly twisted exemplar of vacuous truth to an audience that wasn't shy about admitting that it seemed weird. Some idea of the dynamics are seen in the annotated slide where I present the claim that for every real number x, if x^2-2x+2 = 0, then x > x+5. The unnerving thing is that the entire if-then claim is true, since you'll never find a real number that satisfies the first part, but falsifies the second (there are no real roots of that quadratic equation). There's no magic: the false conclusion doesn't become true, but the claim that it follows from the antecedent is true.
In response to my question about whether this implication is true for all real numbers (it is), the Monday night crowd was split. Once we thrashed out the point that any real number substituted for x gives us a false antecedent (hence a true implication), I asked whether the claim true if it asked where there existed some real number where the antecedent implied the consequent. The majority disagreed, and asked me to come up with examples. I started spinning off various real numbers: 17.98, 13.532, ... (any real number would work), and we eventually agreed that the "there exists" form of the statement is also true. Then somebody asked what happens if we change the set x is a member of from the real numbers (where there is no solution to the quadratic equation), to the complex numbers (where all solutions exist). That made the question more interesting, and I found myself regretting that I hadn't thought of this twist first.
I had the feeling that several people were coming to grips with vacuous truth in real time during the lecture. Impressive.
I've already taught one cycle of this week's material to my Monday evening class, and now I'm trying to make sure my Monday-Wednesday-Friday version of the same material is consistent with it, and preparing other material. So the look backwards function of a blog can be exercised from this vantage point as well as any other.
I learned (or perhaps re-learned) just how thoroughly counter-intuitive the notion of vacuous truth can be this week. The name sounds as though the variety of truth is silly, trivial, or empty, but it's an important technique in logic. If we have an implication that claims that if P is true, then Q follows, then then implication as a whole is true whenever P is false. The notion rests on the fact that an implication claims that Q follows from P, and the only time that "following from" rule is broken is when P is true and Q breaches faith by being false.
In particular, whenever P is false, no breach of faith is possible.
I've often fired up vast and powerful pedagogical machinery to convey this point, being sure to make it several different ways since it registers with different people in differently. There are always some people who resist the first onslaught, so I back the machinery up and take another run at it. Usually nobody is willing to admit that vacuous truth still seems weird after two or three runs at it.
Monday night, though, I presented a particularly twisted exemplar of vacuous truth to an audience that wasn't shy about admitting that it seemed weird. Some idea of the dynamics are seen in the annotated slide where I present the claim that for every real number x, if x^2-2x+2 = 0, then x > x+5. The unnerving thing is that the entire if-then claim is true, since you'll never find a real number that satisfies the first part, but falsifies the second (there are no real roots of that quadratic equation). There's no magic: the false conclusion doesn't become true, but the claim that it follows from the antecedent is true.
In response to my question about whether this implication is true for all real numbers (it is), the Monday night crowd was split. Once we thrashed out the point that any real number substituted for x gives us a false antecedent (hence a true implication), I asked whether the claim true if it asked where there existed some real number where the antecedent implied the consequent. The majority disagreed, and asked me to come up with examples. I started spinning off various real numbers: 17.98, 13.532, ... (any real number would work), and we eventually agreed that the "there exists" form of the statement is also true. Then somebody asked what happens if we change the set x is a member of from the real numbers (where there is no solution to the quadratic equation), to the complex numbers (where all solutions exist). That made the question more interesting, and I found myself regretting that I hadn't thought of this twist first.
I had the feeling that several people were coming to grips with vacuous truth in real time during the lecture. Impressive.
Friday, January 15, 2010
Correct unless mistaken
The narrow way we use the English word "unless" in a course about mathematical expression is a real eye-opener. Consider the following statements:
In the first, you could translate "unless" as "if-not," so not buying the ticket guarantees not winning, but the converse is false: you aren't guaranteed to win if you buy the ticket. In the second statement, many of my workmates read "unless" as "if-and-only-if-not," so if you don't come too, I certainly won't go, but if you come, I will certainly come. If we take our case to the web, we'll find lots of support for the "if-not" translation, but also some for a combination of both. For the purposes of mathematics, I'll stick with the "if-not" version, but I can see that it's slippery.
Another good confrontation with real-world interpretation came when I asked students to explain the double-meaning in the headline:
They noted that the two meanings of head (the body part perched on your neck, and the leader of some entity) paired up neatly with two meanings of arms (the body parts hanging from your shoulders, and weapons), and they concluded that the headline certainly meant to pair the leader meaning of head with weapons. I realize that Condie probably wasn't thinking of this headline when he made La Sala, but it does leave open the question of whether the other interpretation of the headline doesn't have some support in the real world (wherever that is).
You can't win the lottery unless you buy a ticket.
I won't go unless you come too.
In the first, you could translate "unless" as "if-not," so not buying the ticket guarantees not winning, but the converse is false: you aren't guaranteed to win if you buy the ticket. In the second statement, many of my workmates read "unless" as "if-and-only-if-not," so if you don't come too, I certainly won't go, but if you come, I will certainly come. If we take our case to the web, we'll find lots of support for the "if-not" translation, but also some for a combination of both. For the purposes of mathematics, I'll stick with the "if-not" version, but I can see that it's slippery.
Another good confrontation with real-world interpretation came when I asked students to explain the double-meaning in the headline:
Iraqi head seeks arms
They noted that the two meanings of head (the body part perched on your neck, and the leader of some entity) paired up neatly with two meanings of arms (the body parts hanging from your shoulders, and weapons), and they concluded that the headline certainly meant to pair the leader meaning of head with weapons. I realize that Condie probably wasn't thinking of this headline when he made La Sala, but it does leave open the question of whether the other interpretation of the headline doesn't have some support in the real world (wherever that is).
Sunday, October 26, 2008
Prove it's correct
This topic always marks a sharp departure from hacker culture. On the one hand, when we're used to having fun implementing intuitive ideas in code, why would we divert ourselves into proving they do what we want? On the other hand, even if we wanted to, how can we prove that our code will always do the things we claim it will?
In spite of these nagging doubts, we began looking at proving recursive correctness --- suspiciously like induction (and so it should be). In order to be reasonable a piece of code performs as claimed, we have to examine each line of code in surprising detail. The pay-off is that unexpected "edge" cases sometimes become apparent when we're trying to prove the thing works.
I'm inclined to sing along with my students this week "October is sooo crazy." I think I've nearly gotten through the worse of my administrative (non-teaching) duties for a little while, and will come out the other side soon. Just one more departmental TA ad to post, and I'm almost there.
In spite of these nagging doubts, we began looking at proving recursive correctness --- suspiciously like induction (and so it should be). In order to be reasonable a piece of code performs as claimed, we have to examine each line of code in surprising detail. The pay-off is that unexpected "edge" cases sometimes become apparent when we're trying to prove the thing works.
I'm inclined to sing along with my students this week "October is sooo crazy." I think I've nearly gotten through the worse of my administrative (non-teaching) duties for a little while, and will come out the other side soon. Just one more departmental TA ad to post, and I'm almost there.
Monday, October 13, 2008
Rabbit without a hat
I've always been a bit annoyed when a mathematical result is pulled out, in the middle of a slick argument, because it works. Sometimes this presentation is necessary, since the long, painful path to the result is not useful in and of itself. Often, though, slickness hides the fact that mathematics is a lot of messy work.
An example of these is the closed form for F(n), the nth Fibonacci number. Without even getting in to the controversy of what qualifies as a closed form, this result has the "feature" that F(n) is equal to the sum of two roots of the quadratic r^2 = r + 1, after you multiply them by a suitable coefficient.
Certainly this result can be proved by induction: a nice exercise in simple induction. But how would you ever dream of coming up with the conjecture in the first place? This week I gave an account of how you might find your way from the recursive expression for F(n), and its closed form.
An example of these is the closed form for F(n), the nth Fibonacci number. Without even getting in to the controversy of what qualifies as a closed form, this result has the "feature" that F(n) is equal to the sum of two roots of the quadratic r^2 = r + 1, after you multiply them by a suitable coefficient.
Certainly this result can be proved by induction: a nice exercise in simple induction. But how would you ever dream of coming up with the conjecture in the first place? This week I gave an account of how you might find your way from the recursive expression for F(n), and its closed form.
Subscribe to:
Posts (Atom)
