## HCSSiM Workshop day 9

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 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.

**Homomorphisms**

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.

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.

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 ) 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

twonatural 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 -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

decidingby rule for each x what F(x) will be. This didn’t require the axiom of choice, which is need in proofs where youcan’tgive a rule of this decision and need to make an arbitrary choice.So let be a set of non-empty sets of real numbers, and consider the problem of choosing one element from each member of , in other words of constructing a function with domain $latex $A so that . 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 is compact. Then we can set .

(2) Suppose every is just closed. We can let be “the minimum if that’s defined, the maximum non-positive member otherwise”. Again we have a clear rule how to determine what 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 is open. Choose an auxiliary surjective function (there are explicit constructions) and set [in other words, “the first rational number in the set”. Did we need to make choices? No — the function is defined, and the function was constructed earlier in the course.

(4) The elements of are the ranges of specified functions (that is, for each 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.

Awesome, thanks! That helps a lot. I get it now.

Cathy