Re: [math-fun] Re: favorite theorem
Bill Thurston wrote: << Once when I TA'd in a course "math for elementary school teachers" taught by Leon Henkin, he went over a proof of this theorem---I thought it was pretty revealing, (although I have to say it wasn't very appropriate for the future elementary school teachers, who didn't understand the point.) But for me, after going through the proof and trying to explain it to my students, it made a lot of sense why there is something that needs proof and that can be proven, our early indoctrination to the contrary notwithstanding. In fact, there's a good proof reducing it to on more primitive intuition than counting. It's very close to the standard proof that finite-dimensional vector spaces over a given field are classified by their dimension---which few people think is obvious without proof! I.e., when you count a finite set in two different orders, why do you get the same number? You can transform one order of counting to the other step-by-step using a simple exchange. I kind of like the point of view that proofs as a dialectical construct, as in Lakatos' book "Proofs and their refutations", rather than part of a formal system (which in practice they definitely are not). Many things people accept for a time, or for ever, until they are challenged, when their beliefs can be shaken. Did you ever tabulate a big set of data by hand and find the column sums and the row sums did not reconcile? At times like that, my belief in the commutative law for addition can become shaken --- thinking back through why sums, or counts, should reconcile is a non-obvious task.
How would you phrase the theorem(s) you're referring to? I can't see how to say the sizes of [two permutations P,Q of a finite set X] are equal other than this: ------------------------------------- Assume X nonempty. A permutation of a nonempty set X is a bijective mapping X -> {1,...,r} for some r in Z+, so we have bijections P: X -> {1,...,k} and Q: X -> {1,...,n}, and hence P Q^(-1) shows {1,...,k} and {1,...,n} are bijective, hence the same size. ------------------------------------- So, you need to know that inverses and compositions of bijections are bijections, as well as the definitions of permutation and "same size". Is that it? --Dan
Bijections or matchings between two sets --- yes, let's start by assuming people understand that concept. It's very basic, and young kids catch on to that quickly. Before they can count correctly, they can line things up so they match. What's **not** obvious except for early indoctrination is that a finite set can't have a bijection to a proper subset of itself. I.e. if you count a set 1,2,3,4,5,6,7 and someone else goes in a different order and counts 1,2,3,4,5,6,7,8, then one of the two is not a bijection. The proof: you make some little numbered blue tags and stick them to the objects, while the other person makes little numbered red tags and sticks them on. Did you both stick your #1 tags to the same object? If not, find the red #1 tag, and trade it with the red tag stuck next to your blue #1 tag. Now check the #2 tags ... etc. If they're both bijections to initial segments of counting numbers, in the end they'll match. Bill Counting involves several different levels On Apr 30, 2006, at 11:42 PM, dasimov@earthlink.net wrote:
Bill Thurston wrote:
<< Once when I TA'd in a course "math for elementary school teachers" taught by Leon Henkin, he went over a proof of this theorem---I thought it was pretty revealing, (although I have to say it wasn't very appropriate for the future elementary school teachers, who didn't understand the point.) But for me, after going through the proof and trying to explain it to my students, it made a lot of sense why there is something that needs proof and that can be proven, our early indoctrination to the contrary notwithstanding.
In fact, there's a good proof reducing it to on more primitive intuition than counting. It's very close to the standard proof that finite-dimensional vector spaces over a given field are classified by their dimension---which few people think is obvious without proof! I.e., when you count a finite set in two different orders, why do you get the same number? You can transform one order of counting to the other step-by-step using a simple exchange.
I kind of like the point of view that proofs as a dialectical construct, as in Lakatos' book "Proofs and their refutations", rather than part of a formal system (which in practice they definitely are not). Many things people accept for a time, or for ever, until they are challenged, when their beliefs can be shaken. Did you ever tabulate a big set of data by hand and find the column sums and the row sums did not reconcile? At times like that, my belief in the commutative law for addition can become shaken --- thinking back through why sums, or counts, should reconcile is a non-obvious task.
How would you phrase the theorem(s) you're referring to?
I can't see how to say the sizes of [two permutations P,Q of a finite set X] are equal other than this:
------------------------------------- Assume X nonempty. A permutation of a nonempty set X is a bijective mapping X -> {1,...,r} for some r in Z+, so we have bijections P: X -> {1,...,k} and Q: X -> {1,...,n}, and hence P Q^(-1) shows {1,...,k} and {1,...,n} are bijective, hence the same size. -------------------------------------
So, you need to know that inverses and compositions of bijections are bijections, as well as the definitions of permutation and "same size".
Is that it?
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Bill Thurston -
dasimov＠earthlink.net