Timeline for Why are induction proofs so challenging for students?
Current License: CC BY-SA 3.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 13, 2020 at 16:47 | comment | added | user21820 | @LSpice: Incidentally, if you are interested, in my teaching experience the method I gave in this post to teach induction (where you must break down a larger structure into smaller ones) does in practice eliminate students' common fallacious notions about induction, because it forces them to actually argue in the correct logical direction even if they are not taught formal FOL reasoning. (And the cherry on top is that, for almost all practical applications, all you need is induction on naturals. Heheh.) | |
| Nov 13, 2020 at 16:44 | comment | added | user21820 | But the point that we can do well-founded induction/recursion beyond well-orderings is a very good one (+1), because I sort of forgot about that. | |
| Nov 13, 2020 at 16:44 | comment | added | LSpice | Certainly; I don't mean to imply that students who master the usual approach can't handle other approaches. I mean instead that some students never master the usual approach, or take an inordinate amount of time to do so, and that an alternate approach first could give them a better path to a success they might otherwise not have reached. | |
| Nov 13, 2020 at 16:43 | comment | added | user21820 | @LSpice: I've taught enough to know that once students can do FOL reasoning properly (and by that I mean formal FOL deductive proofs), they will definitely not hampered by anything at all, much less natural numbers. The only students who will fail to see how the appropriate version of strong induction easily extends to other well-founded things (indeed not just restricted to well-orderings), are those who cannot even do FOL reasoning, and thereby rely on their intuitive crutches to blindly guess their way through hand-waving arguments. | |
| Nov 13, 2020 at 16:38 | comment | added | LSpice | … run along these more general sets, but I meant to the contrary that I think students are hampered by starting with nat.s, which are too familiar; they can't help bringing in undue intuition that hides the structure of induction and makes, as others have mentioned, the usual statement of induction sound like "you assumed $P(n)$ and you concluded $P(n)$, and that's circular." Anyway, I am braver in speech than in action; I have never taught induction this way—but I definitely would if teaching mostly CS majors. | |
| Nov 13, 2020 at 16:37 | comment | added | LSpice | @user21820, you're right that I appeared to be referring to ordinals, and I certainly don't mean to discuss them before the natural numbers. I forgot that "well ordered" implies "totally ordered". I meant to consider more general sets for which $(\forall\beta\mathrel.(\forall\alpha < \beta\mathrel.P(\alpha))\implies P(\beta))\implies(\forall\beta.P(\beta))$, such as, for example, the set of trees with its natural order. You may respond again that students need to learn to walk along the naturals before they … | |
| Nov 13, 2020 at 12:45 | comment | added | user21820 | And, somewhat off-topic, but in my philosophical viewpoint of mathematics, the naturals are in fact very special and irreducible, so much so that you cannot do without them to even set up formal reasoning. General well-orderings, on the other hand... Can you really construct an uncountable well-ordering? Sure, using set-theoretic tools, but is that a platonic fact or an artifact of set-theoretic assumptions? Who knows? | |
| Nov 13, 2020 at 12:39 | comment | added | user21820 | @LSpice: Well you and I both know that strong induction in the appropriate form works for any well-ordering, but this post was about students who cannot even do proper FOL reasoning... To run, one must first learn to walk. =) Incidentally, for ordinary mathematics there is rarely a need to deal with ordinals at all, because we can prove the well-ordering theorem and Zorn's lemma easily. | |
| Nov 12, 2020 at 22:47 | comment | added | LSpice | @user21820, I think that an emphasis on size, except perhaps informally, misleads into thinking that there's something special about the natural numbers. To the contrary, I think it's important to realise that they're just one example of a well ordered set, and that induction suitably stated works perfectly well on any such set; and that a size measure is just a way of helping to show that a set is well ordered. | |
| Jun 18, 2020 at 8:32 | history | edited | CommunityBot |
Commonmark migration
|
|
| Aug 26, 2017 at 15:53 | comment | added | user21820 | [cont] Call the connections in (2) edges. Define a finite tree to be a tree with a natural number size. If you don't want "size" as a partial function, you need to define size a bit more carefully. As an example I shall prove that every finite tree $T$ has more nodes than edges. If $T$ is a leaf node, then we are done. If $T$ is not, then $T$ has $k$ subtrees each with size strictly smaller than that of $T$, and if all of them satisfy the claim then there are $k$ more nodes than edges in them, which can offset the $k$ edges from them to the root, so $T$ itself satisfies the claim. | |
| Aug 25, 2017 at 22:35 | comment | added | Wildcard | This answer would be much clearer with an example. | |
| Jan 27, 2016 at 2:59 | comment | added | user21820 | @vonbrand: Recursive induction on the other hand in some sense does not depend on meta-logic, as it only depends on the ability to assign a size to each finite object of that particular type, so that we can talk about smaller subobjects. For a simple example, consider defining a tree as either (1) a leaf node or (2) an internal node connected to one or more disjoint trees. This is so elegant that nothing compares to it, and moreover it is perfectly practical as a data structure. Now we can define size recursively too! It is 1 if it is a leaf node and 1 plus the sum of the subtree sizes. [cont] | |
| Jan 27, 2016 at 2:54 | comment | added | user21820 | @vonbrand: Well I do think there's a significant difference, because in fact the recursive definition is significantly different from the iterative definition. If you look at my other answer, iterative induction is based on meta-logic, and requires understanding of proofs and encodings of the natural numbers as strings of the form "$1+1+\cdots$". Then only one truly appreciates the correctness of induction, and will not make the mistake of building bigger from smaller objects. [continued] | |
| Jan 27, 2016 at 2:43 | comment | added | vonbrand | @user21820, just observing that they understand neither, for more of less the same underlying reason. That doesn't help a bit in finding out how to get them to understand either... | |
| Jan 27, 2016 at 2:41 | comment | added | user21820 | @vonbrand: I can assure you it is because of how they were taught. Without having heard the word "recursion" before, they would certainly not run away on hearing it the first time. It is if the one who first talks to them about "recursion" does not explain it intuitively and precisely that they find it incomprehensible and hence shun it, exactly like all other mathematics. | |
| Jan 26, 2016 at 22:09 | comment | added | vonbrand | Computer science students run away screaming in horror when they hear "recursion"... exactly the very same "induction is incomprehensible" phenomenon. | |
| Nov 21, 2015 at 6:59 | comment | added | user21820 | @dtldarek: Ah yes then I fully agree. That's why I mentioned trees in my answer, because only when things break down in a non-linear way (exactly as you say) do students really get a feel for the true nature of recursive structures and structural induction. Thanks for pointing it out! | |
| Nov 20, 2015 at 14:00 | comment | added | dtldarek | @user21820 Perhaps we have misunderstood each other. I don't say that bounding with recursion is bad, quite the opposite, I would encourage it as long as the class allows it. It is that, in my opinion, it is not enough. In my experience, in the case of loops, the students frequently seem to use their old reasoning with a mental note "call it induction" attached—they think they understand and are satisfied with what they already know. | |
| Nov 20, 2015 at 13:40 | comment | added | user21820 | @dtldarek: I mean the proof that really goes down to the details of why the output of the algorithm, and before that the particular variable that was used to store the tentative maximum, is the maximum. It boils down straight to loop-invariance, which is an important variant of induction. | |
| Nov 20, 2015 at 13:36 | comment | added | dtldarek | Cont. In other words, I would consider finding the maximum a bad example. My guess is that when learning structural induction the students usually cannot rely much on their intuition, and have to examine, from the scratch, why such proof could/should work. Once the connection between the shape of the structure/relation and the shape of chain of inferences has been made, all else seems much easier. Fin. | |
| Nov 20, 2015 at 13:36 | comment | added | dtldarek | @user21820 At that particular account I disagree, in particular that algorithm works, because "we examined all the numbers, so we had to find the biggest one". Actually this is one of the points I want to address with using the structural induction: induction on naturals does not force the student out of his usual modes of reasoning (processing items one by one are similar approaches are common enough in real life, hence the quoted explanation suffices to the student and he/she might not understand why we need more). Cont. | |
| Nov 20, 2015 at 12:50 | comment | added | user21820 | @dtldarek: To make sure it weighs a lot, I would recommend teaching structural induction at the same time as teaching recursive viewpoint of structures. For example most people don't think twice about the simple algorithm to find the maximum of an array of integers. But why does it work? When really faced with this question, the student now has to start thinking about justification, and then this recursive viewpoint is motivated and helps to crystallize the vague intuitive justifications. | |
| Nov 20, 2015 at 12:15 | comment | added | dtldarek | @JosephO'Rourke I also think that structural induction is a better approach (see here and here), although this is only a hypothesis. The question is whether the potential benefits outweigh the increased complexity of the problems. | |
| Nov 19, 2015 at 18:22 | comment | added | user21820 | @JosephO'Rourke: Then this might be the best way to go. I've also done them together. The thing is that for CS objects, they are all finite and so we rarely need to use much more than this type of structural induction. And after structural induction is grasped, ordinary induction is easy. | |
| Nov 19, 2015 at 17:50 | comment | added | Joseph O'Rourke | Incidentally, I plan to teach induction & recursion together, hopefully with one reinforcing the other. | |
| Nov 19, 2015 at 17:40 | history | edited | user21820 | CC BY-SA 3.0 |
added 498 characters in body
|
| Nov 19, 2015 at 17:30 | history | answered | user21820 | CC BY-SA 3.0 |