While teaching logic for the first time (I am teaching to graduate students, but I haven't taught any logic before), I've finally realized how much I like constructive proofs. I gave a completely constructive proof of weak propositional completeness, by giving a simple proof algorithm that underlies this perl prover program. Basically, you start by proving excluded middle for each atomic. Then you just do proof by cases on all possible combinations of truth values of atomics. This only works for a finite number of atomics, so it only gives weak completeness. But the proof method is entirely constructive, simple enough that one can use it oneself (e.g., I used it myself when proving one of the De Morgan directions in class). I am not claiming it's at all new—it's not—but I had fun rediscovering it.
Then, today or Thursday (depending on whether time allows), I'll give a semantic proof of propositional compactness in the case of countably many atomics. (I am sure this proof has a name attached to it, but it's easier to make up than to look up.) Again, it's going to be entirely constructive, and pretty simple. It just uses induction and the lemma that if A is f-satisfiable (i.e., every finite subset of A is satisfiable), and Q is an atomic, then either A plus Q is f-satisfiable, or A plus not-Q is f-satisfiable. As it stands, this only works for countably many atomics, but in fact it also works for any case where there is a well-ordering on the atomics (and hence by the Axiom of Choice, it extends to the general case; but it is kind of nice to note that once one fixes the well-ordering on the atomics, it's entirely constructive). I'm not a logician. None of this is at all new. But I'm having lots of fun, hopefully of an innocent variety.
But I have also made an interesting sociological discovery: Students find set theory harder than first order logic. They seem to think of set theory as more abstract and strange. This was really weird to me at first, but that's just because I've been using sets for the larger part of my life, and only got to rigorous first order logic recently. Next time I teach the material, I will have to move more slowly through the beginning of set theory to make it clear that "member of" is not transitive but "subset of" is, that {{1,2,3}} has only one member, and so on. (Why, oh why, don't they teach computer programming starting with Grade 2 in all schools, so one could suppose familiarity with various kinds of abstract data structures by the time of college, which would allow for a nice stock of common concepts? It's a more useful intellectual and practical skill than, say, cursive handwriting.)
7 comments:
I second the idea that they should be teaching computer programming from an early age.
I have always detested set theory; you can do some things elegantly in set theory, but it has always seemed to me to be clunky and unintuitive. Whatever elegance it has is an elegance only a mathematician could love. My feeling has always been that if you are going to drag me through anything involving set theory you had better be going for a truly significant result that would be even more difficult to get any other way. I've recently come to wonder, though, if a lot of the strangeness of set theory for most people could be dissipated by playing up the (surprisingly strong) analogies between sets and lists. People in everyday life usually don't think in terms of sets as such; but we actually perform operations on lists all the time, and a lot of the things you do with lists are closely analogous to things you do with sets. (The major difference in most cases is that lists have 'intensions' as well as 'extensions', and the intensions also play a big role in our reasoning about lists. But this also means, e.g., that it's easier to grasp the idea of an empty list than an empty set.) In a sense a lot of the usual examples given to beginners are lists anyway, just not presented as such. I once had the idea of sitting down and trying to set down as much of set theory as I could by presenting it entirely as a sort of generalization of the idea of lists. Probably one of those things I'll never get around to trying.
Brandon:
I think ordered lists are very intuitive. We also ordinarily talk of collections, too. I think a lot of the difficulties with set theory for people come from nesting sets. I wonder if that's a sign that people don't want to be Platonists about collections--they are willing to have collections with real members, but not collections of collections, because collections, they think, aren't something real. And, just as unordered lists, ordinary collections can lose and gain members.
While set theory itself is clunky, it can be used to make some really elegant definitions. The notion of an equivalence class is really, really neat, and is central to just about every kind of beautiful mathematics. It's just that after you make the definition, you need to encapsulate it in a new notation.
Everybody:
A friend emailed me asking if I knew any good resources for teaching programming to small children. I don't. Does anybody?
On the teaching programming, I came to programming relatively later than the age at which I'd like my children to do so, at age 9, with a Timex-Sinclair 1024, and a fun book with a picture of a dragon that taught really simple BASIC programming (of the guess my number variety). I don't know if BASIC is still the way to start.
Logo was once used a lot for educational purposes, but I've heard the Logo skills don't carry over nicely to other programming languages.
Of course, unstructured BASIC also induces bad habits. But I don't actually think these bad habits are a problem--GOTOs teach one how computers work, and while one should use better flow control methods when these are available, the better flow control methods are anyway implemented on GOTOs at the assembly level. Once I moved on to C, I automatically started using the better flow control methods simply because they were easier.
Anyway, now there are all these structured BASICs. Maybe that's the way to go.
One problem is that nowadays the motivations for kids will be smaller, since all kinds of pieces of software much flashier than whatever they'll make themselves are easily available for free.
Correction: "age 9" should be "age 10".
I'm inclined to think that people would probably have an easier time nesting lists than collections; but I don't have any evidence for that. Of course, either way one has to make something of a leap from the analogue to the notion of a set.
On programming resources for kids, I know that there are actually a lot of different resources along those lines, mostly designed for homeschoolers: Phrogram, Snake Wrangling for Kids, Jurtle. I don't know much about them, though, or whether they're any good.
Snake Wrangling for Kids is labeled for ages 8 and up, but I think it moves a bit too fast for them. For instance, the introduction of order of operations is much too fast for 8 year-olds.
Other than that, it seems a rather nice introduction.
On second thought, while it's probably inappropriate for 8-year-olds to read on their own, it may be good with a parent's help.
Post a Comment