Home > math education > HCSSiM Workshop day 7

HCSSiM Workshop day 7

July 10, 2012

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

The real numbers are uncountable

Today we used Cantor’s diagonal argument to prove that the real numbers aren’t countable. Namely, we assumed they were, and that we had a bijection f: \mathbb{N} \rightarrow \mathbb{R} and then proved it didn’t contain the real number YP, whose ith digit we defined to be 1 if the ith digit of f(i) is 7, and 7 otherwise. One of our students pointed out that there are some numbers that have more than one decimal expansion, so the general argument that a certain decimal expansion isn’t in the list isn’t a total proof. But we decided that we’d be able to prove on homework that the only numbers that have more than one representative in decimal expansions are rational with their denominators divisible only by 2 and 5, which is not the case for the number YP we’d been talking about.

Then we wanted to show that \mathbb{R} has the same cardinality as \mathbb{R}\times\mathbb{R}. We tried to use a “splicing argument” where we create a new decimal expansion out of two decimal expansions (where the odd digits correspond to the first and the even to the second), but then we decided this map isn’t well defined, since we still have this “overlap” problem where 0.999… = 1 but the pair (0, 0.999...) doesn’t get mapped by the splicing map to the same decimal expansion as the pair (0, 1).

So then we decided to instead consider the set of decimal expansions, which is a bit bigger than the reals, and there the splicing map works. We reduced it to this case and are leaving it to homework to prove that the set of decimal expansions has the same cardinality as the reals. Although I don’t actually know how to do this without Cantor-Schroder-Bernstein, which we haven’t proven yet.

The Chinese Remainder Theorem 

We stated and proved the Chinese (Llama) Remainder Theorem. It was a nice example of a constructive proof that assumes it’s possible and then, when you follow your nose, it’s possible to completely characterize what the solution must look like, and then it falls out. We showed it described a bijection of sets \mathbb{Z}/\prod_i n_i \mathbb{Z} \rightarrow \prod_i \mathbb{Z}/n_i \mathbb{Z}. We haven’t talked about homomorphisms of groups yet though so we can’t prove it’s an isomorphism of groups.

Dilworth’s Theorem on chains and anti-chains in posets

We started the proof of Dilworth’s Theorem but didn’t finish yet (to be continued tomorrow). Turns out that this problem is really hard and that, moreover, there are lots of ways to convince yourself it’s true but be wrong about. The inductive proof in wikipedia, for example, is incomplete, but can be extended to a complete proof.

As an example, try to cover the following poset on the power set of five letters with 10 chains:

In particular you can see we solve a matching problem on the way, between subsets of size two and subsets of size 3 in the set of five letters, which isn’t the normal “take the complement” match, but rather is an inclusion of one in the other. I’m still wondering if there’s a more direct way to do this.

Categories: math education
  1. Lior Silberman
    July 10, 2012 at 3:46 pm

    For comparing the reals and the decimal expansion, all you need is the Hilbert hotel constructions you’ve already discussed, since the irrationals are in bijection with their decimal expansions, while the set of decimal expansions corresponding to rational numbers is countable.

    Like

  1. July 11, 2012 at 8:22 pm
    HCSSiM Workshop day 8 « mathbabe
  2. July 12, 2012 at 6:53 am
    HCSSiM Workshop day 9 « mathbabe
Comments are closed.