Home > math education > HCSSiM Workshop day 9

HCSSiM Workshop day 9

July 12, 2012

A continuation of this, where I take notes on my workshop at HCSSiM.

First we had a few proofs from the previous night’s problem set, including a proof of Hall’s Marriage Problem using Dilworth’s Theorem.

Counting stuff

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 f and g in the opposite directions: f:X \rightarrow Y and g:Y \rightarrow X, then you can construct a bijection between X and Y, 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 f,g, and if possible, by pulling back by f^{-1} and g^{-1}.

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 X or Y. 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 x in X to f(x) unless it’s an orbit that gets going backwards in Y, in which case you take x to g^{-1}(x).

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 p. 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 a, which means that product is equal to itself times a^{p-1}, and since it’s invertible that means a^{p-1} \cong 1 \, \, (mod \; p). That’s just a hop skip and jump away from Fermat’s Little Theorem, which states that a^{p} \cong a \, \, (mod \; p) for every number a.

Next, we wondered, what was that product of all those non-zero numbers mod p? 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.

Categories: math education
  1. Dan L
    July 12, 2012 at 10:26 am

    There may be infinitely many orbits, but there are only 2 sets that you care to distinguish. You just need a formal statement of what it means for x to “not get stuck in Y going backwards,” and observe that it doesn’t require AC to define this set. (The set of all x such for any natural n, if x is in the image of (gf)^{n-1}g, then it’s also in the image in (gf)^n.)

    Other than the AC confusion, I don’t think I’ve ever seen this theorem explained as nicely as it is here. Also, it’s a good exercise for students just to rigorously verify that the claimed function is a bijection. It’s a typical example of something that is “obvious” but not so easy to write down properly for students untrained in writing proofs.


  2. July 12, 2012 at 6:46 pm

    I agree that the proof of Cantor–Schroder–Bernstein is best viewed as a statement about a bipartite graph. I’d recommend having every vertex degree at most $2$ (that is, using the edges (x,f(x)), (g(y),y)) which forces each connected component to be either an even cycle or a one-ended chain or a bi-infinite chain. Then you choose a bijection on each component.

    Now regarding the use of the axiom of choice: making “decisions” never involves the axiom of choice, while making “choices” does.

    On a connected component which was a one-ended chain there was only one way to make the bijection work, but on connected components which were cycles or bi-infinite chains there are two natural bijections, corresponding to the two possible “directions” of traversing the chain/cycle. Why didn’t the proof require the axiom of choice to manage this infinite number of choices? Because we could make the decision ourselves in advance. Specifically for this proof, each chain came with a “built-in orientation” [say, the direction given by f-arrow], and we can agree to only traverse cycles and bi-infinite chains in that direction. Note that this happened in your proof.

    In short, you constructed a bijection F by deciding by rule for each x what F(x) will be. This didn’t require the axiom of choice, which is need in proofs where you can’t give a rule of this decision and need to make an arbitrary choice.

    So let A be a set of non-empty sets of real numbers, and consider the problem of choosing one element from each member of A, in other words of constructing a function F with domain $latex $A so that \forall a\in A:F(a)\in a. In general of course you need the axiom of choice for this, but a good way to illustrate the axiom is to see why most of the time you don’t need it:

    (1) Suppose every a\in A is compact. Then we can set F(a) = \min a.

    (2) Suppose every a\in A is just closed. We can let F(a) be “the minimum if that’s defined, the maximum non-positive member otherwise”. Again we have a clear rule how to determine what F(a) is, so no choice was involved. Of course, one needs to verify that every closed set either has a minimum or has a maximal non-positive member, but that’s not hard.

    (3) Suppose every a\in A is open. Choose an auxiliary surjective function g\colon \mathbb{N}\to\mathbb{Q} (there are explicit constructions) and set F(a)=g(\min(g^{-1}(a))) [in other words, “the first rational number in the set”. Did we need to make choices? No — the function F is defined, and the function g was constructed earlier in the course.

    (4) The elements of A are the ranges of specified functions (that is, for each a you are also given the function), and that the domains are nice (e.g. fall under parts (1)-(3)). Then it is enough to choose a point in the domain of each function and map it forward.


  1. July 13, 2012 at 6:44 am
Comments are closed.
%d bloggers like this: