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
