Fork me on GitHub
Math for the people, by the people.

User login

K\"onig's theorem

inequality, cardinal
Koenig's theorem, Konig's theorem, K\"onig-Zermelo theorem, Koenig-Zermelo theorem, Konig-Zermelo theorem
Type of Math Object: 
Major Section: 

Mathematics Subject Classification

03E10 no label found


In the proof, you show phi is an injection, and then show that there is an element of the codomain that is not in the range of phi. From this you conclude that there is no possible surjection from phi's domain to it's codomain. This isn't the case.

Let F:N->N be f(n)=2n. The number 3 is in the codomain of f, but not in it's range, however g:N->N, g(n)=n is a surjection.

That's not what it's saying. We show an arbitrary phi, whether or not it's an injection, _cannot_ be a surjection. (The proof here omits the proof that there _is_ an injection, though.)

Hmm, it wasn't clear to me on the first several readthroughs, that phi was any arbitrary function. I took it to be a fixed function, rather than a generic representative of the set of all functions from the first space to the second. I recommend you emphasize this by stating it explicitly either in the first sentence of the proof for Theorem 2 ("Let phi:... be any function"), or later you could conclude "Since we've shown this for any arbitrary phi, there is no surjection..."

Another sticking point I had that could be improved for readability was when you defined phi as mapping to the cross-product space of B_i's, but then used phi(a) as a function whose domain is I and whose range is Union(B_i).

Since functions in set theory are subsets of cross-product spaces (with no two points in the subset sharing the same coordinates in the dimensions that make up the domain), using phi(a) as a function from I to Union(B_i) implies that phi(a) is an element of IxUnion(B_i) not an element of Product(B_i) (as implied by the codomain in the definition of phi). I tried establishing a bijection between Product(B_i) and the function space from I to Union(B_i) [a subset of the powerset of IxUnion(B_i)], and it took me a bit of time to recognize that I could do so once I restricted the function space to those functions that only matched elements from B_i to i (as opposed to matching any element of Union(B_i) to i). It clicked when I saw that these were those function that chose an element of B_i for each i - the set of choice functions on {B_i}. [If F \sub Power(IxUnion(B_i)) is the set of functions from I to Union(B_i), then the set of choice functions on {B_i} is F \intersect Power(Union({i}xB_i)).]

So the way you've defined phi, it is an abuse of notation to say (phi(a))(i). Instead you can establish a bijection theta from Product(B_i) to the set of choice functions on {B_i}. Then instead of (phi(a))(i), it would be (theta(phi(a)))(i).


Subscribe to Comments for "K\"onig's theorem"