Talk:Infinite Set has Countably Infinite Subset/Proof 1

The "proof" presented as Proof 1 is nonsense; perhaps something has been deleted inadvertently? Specifically, the claim "Thus there is function $\phi: \N \to S$ which is surjective but not injective" is asserted without explanation or justification, and in no way follows from what comes before. --ratboy.

This was the proof that was entered by User:Dan232 on 3rd December and got tidied into its current format by me between then and now. I confess I don't follow its reasoning myself, but I am reliably informed that I am completely ignorant of mathematics, so that is to be expected. (Since that time it was extracted from its present position in Infinite Set has Countably Infinite Subset and put into its current home in the transcluded sub-page.)

There may or may not be a missing theorem that needs to be inserted between the two statements as you suggest. If there is, and we do not have it on PW it needs to be added. If there isn't, and the statement in question does not follow from its predecessor, there is indeed a problem that will need to be resolved.

The problem stems from the fact that not all contributors are completely familiar with or agree with the philosophies of this site: a) that every step of every proof needs to be justified rigorously, and b) that the proof is laid out with one statement per line. In the case of a), the view is that it is harmful to students to be given every single line of the proof, as they are then robbed of the need to think for themselves. This is a difficult philosophical position to refute.

If you are sufficiently familiar with this area of set theory (as I say, I'm shaky as I am self-taught here), and know what to do to put this whole page right, including whether the reference to Axiom of Choice, in any of its forms is needed (someone suggested that the Axiom of Dependent Choice may be needed instead, way over my head) then I welcome your input. This page has always been a problem. --prime mover 17:11, 17 December 2011 (CST)

Between any two sets there is always an injection, a surjection or both (a bijection); because any two sets have the same cardinality or one of them has a strictly bigger one. I don't know if it is proven here in PW, but if ratboy knows a proof you can write it and link it to this article.--Dan232 05:42, 18 December 2011 (CST)

I have amended this page so as to be able to link to that crucial result which still needs to be written, but which follows from Zermelo's Theorem (Set Theory). It should be straightforward to prove. --prime mover 07:09, 19 February 2012 (EST)

ACC

Suspect we may be able to get round the need for AoC by coming up with a version of Surjection iff Right Inverse for countable sets which relies only upon ACC. Might take some work and look futile. On the other hand we might be able to produce some elegant generalisation. Anyone interested in exploring? --prime mover 15:31, 5 April 2012 (EDT)

I actually suspect not, because applying a "countable version" of Surjection iff Right Inverse that uses only ACC would require that $S$ is countable, but that's what we're trying to prove. Any other ideas? --abcxyz 16:02, 5 April 2012 (EDT)

Well, that would work. Or is it that only the size of the preimage of the elements needs to be countable? Because that's all we're using the choice function on.

But yes, what I'm saying is, if $S$ is countable, then Surjection iff Right Inverse would follow as a conclusion of ACC. So, as I say, if we develop a version of Surjection iff Right Inverse for Countable Sets, we can invoke that one instead of Surjection iff Right Inverse and we would then have that this proof depends on ACC instead of AoC. That's the direction I'm going in. --prime mover 16:12, 5 April 2012 (EDT)

If I'm not mistaken, what matters is that the codomain (of the surjection; in this case, $S$) is countable. The size of the preimages of the elements doesn't matter (unless they are all $1$) ... is that right or not? --abcxyz 16:19, 5 April 2012 (EDT)

Oh yes of course - light dawns ... it's not the size of the sets that matters, it's the number of them. That is, you need AoC to choose one element out of each of an uncountable set of doubletons, but you don't need AoC to choose one element out of each of two uncountable sets. Hmm. Perhaps we ought to add this paragraph (or an extract) into the AoC page in an explanation section. --prime mover 16:26, 5 April 2012 (EDT)

... except I've just noticed, this also uses Between Two Sets Exists Injection or Surjection, which also uses AoC via Zermelo's Theorem (Set Theory). But then again, that itself probably has a countable version attainable from ACC. --prime mover 16:15, 5 April 2012 (EDT)