HCSSiM Workshop day 9
We then proved an uncountable set union a countable set is uncountable, with the help of Lior’s comment from yesterday.
Then we proved the Cantor-Schroeder-Bernstein Theorem, which states that if you have two injective maps and in the opposite directions: and then you can construct a bijection between and , and in particular the two sets will have the same cardinality. It’s not that hard – consider the orbits of points in X and Y under repeated applications of the two injective maps , and if possible, by pulling back by and
It doesn’t take much thinking to convince yourself that these orbits come in three forms: an infinite list in both directions, a finite loop, or an infinite forward path but a finite backwards path, where at some point you can’t pull back any more. In the last case you could get “stuck” in either or Since the orbits form a partition of all of the points, you can independently decide how to define the bijection depending on what that orbit looks like. Namely, it takes an element in to unless it’s an orbit that gets going backwards in in which case you take to
Now that I think of it, I’m pretty sure this proof uses the axiom of choice, and according to the wikipage on this theorem it doesn’t need to, but I don’t know a proof which avoids it. The truth is I can never tell. Please explain to me if you can, how you can verify if you’re using the axiom of choice in an argument where you make infinitely many decisions.
We defined a homomorphism of groups and wrote it in both additive and multiplicative notation, because it turns out some of the students were getting confused. We proved very basic properties that follow such as the fact that the identity element goes to the identity element under a homomorphism, and the image of the inverse of an element is the inverse of the image. We ended by asking them to consider the set of homomorphisms between a cyclic group of 6 elements and itself, or between a cyclic group of 6 elements to a cyclic group of 7 elements.
Fermat and Wilson
Next we whipped out some theorems modulo a prime We looked at the action defined on numbers mod 17 when you multiply them by 3, and noticed it just scrambles the non-zero ones up (and of course sends 0 to 0). We proved that this is true in general. But this means that the product of all the non-zero numbers mod p is the same if we pre-multiply by any , which means that product is equal to itself times and since it’s invertible that means That’s just a hop skip and jump away from Fermat’s Little Theorem, which states that for every number .
Next, we wondered, what was that product of all those non-zero numbers mod ? It turns out that each of those nonzero guys is invertible, so if you pair each up with its inverse their contribution to the product is just 1, and the leftovers are just the guys who are their own inverse, which is only 1 or -1 (which we proved, and which is most definitely not true modulo 8). So the whole product is -1. That’s Wilson’s Theorem, but we called it Wilevson’s Theorem since Lev came up with the argument.