Talk:Countable Union of Countable Sets is Countable/Proof 2

From ProofWiki
Jump to navigation Jump to search

Why specifically countably infinite sets? The theorem is as easy to prove, but a little stronger when just countable is required. --Lord_Farin 12:42, 19 January 2012 (EST)

No reason. I think there was a contributor some years back who argued that "countable" should always mean "countably infinite" rather than "countably infinite or finite" so an effort must have been made to write the proofs so they distinguished between the two. Can't remember the details now. You're quite correct. Feel free to upgrade this and any other similar. --prime mover 16:34, 19 January 2012 (EST)
My lecture notes on axiomatic set theory require the Axiom of Choice for this theorem. They state '...without AC we cannot prove that $\R$ is not the union of countably many countable sets.' That sounds like they are quite certain that AC is necessary (well, of course, Axiom of Countable Choice would suffice, but I accept AC anyway, so no big deal there; I only pursue that it is known when AC is made use of). --Lord_Farin 18:11, 19 January 2012 (EST)
Wah! I'm seriously unhappy with that. Countable sets can be well-ordered without the need for AoC, surely? I'm going to have to think about this ... acceptance of AoC or not, it would be good for PW to be able to distinguish rigorously what needs AoC and what doesn't, and this statement is difficult. I'm to bed, I'll catch up on this later. --prime mover 18:16, 19 January 2012 (EST)

Merge with Countable Union of Countable Sets is Countable

Suggestion made that Countable Union of Countable Sets is Countable should be merged with this one.

Countersuggestion: rename / rebuild this one as to be Countable Union of Countable Sets is Countable, and add a further page containing the proof of a Finite Union of Countable Sets is Countable. This latter page would have at least 2 proofs: one being a corollary of the countable one, and one being a separate proof. --prime mover 17:18, 29 March 2012 (EDT)

I would say that's a good (counter)idea, as it separates the results depending and not depending on some choice axiom; let's proceed. --Lord_Farin 17:24, 29 March 2012 (EDT)
Not sure exactly what you mean by "rename / rebuild this one as to be Countable Union of Countable Sets is Countable", but the problem with Countable Union of Countable Sets is Countable, if I'm not mistaken, is that the proof uses the axiom of choice, which is a stronger condition than the axiom of countable choice. --abcxyz 18:03, 29 March 2012 (EDT)
Here, you mean 'the problem with the proof of...'. This is a subtle though significant difference. --Lord_Farin 18:05, 29 March 2012 (EDT)
What I mean is: rename / rebuild this one to be Countable Union of Countable Sets is Countable. That is, do a "move" function to call this page Countable Union of Countable Sets is Countable and then amend the content as necessary to make the body of the proof consistent with what the title of the page describes.
If this means changing it to use AoC not ACC then get on and change the bloody proof so as to use AoC not ACC. --prime mover 18:13, 29 March 2012 (EDT)
Did you mean: "...change the proof so as to use ACC instead of AoC"? If so, I tried that and all I came up with is Countable Union of Countable Sets is Countable/Proof 2. --abcxyz 18:21, 29 March 2012 (EDT)
I don't know. I'm just responding to what you wrote up above: "the problem with Countable Union of Countable Sets is Countable, if I'm not mistaken, is that the proof uses the axiom of choice, which is a stronger condition than the axiom of countable choice." FFS, that's exactly the same result as this one! How can that require AoC but this require ACC?!? --prime mover 02:26, 30 March 2012 (EDT)
I meant: the proof in Countable Union of Countable Sets is Countable uses the axiom of choice. The result itself doesn't require the axiom of choice. --abcxyz 08:40, 30 March 2012 (EDT)
That's the fault of the proof, then, not the fault of the result. Wonder who put that proof up? Let's see ... Well, well. --prime mover 13:17, 30 March 2012 (EDT)
It's my fault. I put the proof up. It is LF who brought the use of the axiom of choice to my attention. --abcxyz 13:21, 30 March 2012 (EDT)
... so what are we doing with Countable Union of Countable Sets is Countable/Proof 3? --abcxyz 21:55, 30 March 2012 (EDT)
What's this "we"? You posted it, you finish it. --prime mover 01:07, 31 March 2012 (EDT)
I already mentioned that when I tried to fix it, all I came up with is Countable Union of Countable Sets is Countable/Proof 2. I put the new proof on a different page because "Countable Union of Countable Sets is Countable" was the principal page at that time. --abcxyz 22:35, 31 March 2012 (EDT)
I understand now. --prime mover 00:58, 1 April 2012 (EDT)
Maintenance note: Countable Union of Countable Sets is Countable/Proof 3 has been deleted. — Lord_Farin (talk) 16:45, 18 September 2013 (UTC)
I doubt that the finite case (that is, the finite union of countable sets) merits a separate page, as the only place the axiom of countable choice is used is in the choosing of the sequence of mappings $\left\langle{f_n}\right\rangle_{n \in \N}$. Comments? --abcxyz 19:33, 29 March 2012 (EDT)
I contend that it does merit a separate page. --prime mover 02:26, 30 March 2012 (EDT)
So we would pretty much just copy Proof 1 (and Proof 2 if anyone sees fit) into Finite Union of Countable Sets is Countable (or whatever the title is to be), except noting that the result does not require the axiom of countable choice? --abcxyz 08:52, 30 March 2012 (EDT)
Yep. --prime mover 13:17, 30 March 2012 (EDT)
... still need to do the Finite version, but apart from that, done. I'll let you clever boffins sort out the actual mathematics. --prime mover 15:40, 30 March 2012 (EDT)

So do I. It's a subresult that doesn't use any choice axiom; thence deserves a page to make this (IMO important) observation rigid. (As opposed to: 'Hm, I read this proof and it appears that a finite union would not need choice, but can I be sure?' which is potentially dangerous in other situations.) --Lord_Farin 08:58, 30 March 2012 (EDT)

All right, then let's go with Finite Union of Countable Sets is Countable. --abcxyz 09:14, 30 March 2012 (EDT)

Explain

I strongly suspect the phrase 'countable number' to be what is to be avoided. --Lord_Farin 18:18, 29 March 2012 (EDT)

How about "the union of a countable collection of countable sets"? --abcxyz 18:20, 29 March 2012 (EDT)
What's wrong with "countable number"?
No, what you do is set up a page defining "Countable union" and then link to it. --prime mover 18:33, 29 March 2012 (EDT)
We already have Definition:Countable Union, and where is "countable number" defined here? --abcxyz 18:35, 29 March 2012 (EDT)
Exactly. My argument is: if we already have a compound definition defined, use it. So I have changed them now because I forgot we had this in there. I suggest that when making similar amendments to pages that a little research be done first to see what we already have up there.
My own contribution to this particularly pointless pissing-contest is to suggest that the wording "Assuming the blah, dadada" is something my English teacher would have deducted marks for. --prime mover 02:26, 30 March 2012 (EDT)
Plausibly. Wordings expressing things like $A \implies (B \implies C)$ fk with your mind (not that the very statement in itself doesn't; these things are horrible). Just for fun, check out 'If, if $A$, then $B$, then $C$.' as opposed to 'If $A$, then, if $B$, $C$.' and '$A$ implies $B$ implies $C$.'. Now imagine that $A,B,C$ need multiple words of description rather than just a letter. --Lord_Farin 08:58, 30 March 2012 (EDT)
So should the phrase "assuming the axiom of countable choice" be deleted? --abcxyz 09:14, 30 March 2012 (EDT)
I'd be tempted to split it into two sentences: "Let the ACC be accepted. Then it can be proved that ..." This then takes on the nuance that if ACC is not accepted, then this statement can not be decided. We may of course decide (no pun intended) to specifically mention that latter statement, and everything would be completely specified. - but as it stands it comes across as woolly.
I still contend that "countable number" is perfectly adequate. It means a "countable quantity", or "such that a set containing these objects is countable". Does it need a specific definition? --prime mover 09:18, 30 March 2012 (EDT)

Redundant?

By the way, I think Proof 2 is rather redundant because it is much the same as Proof 1, except for quite a few unnecessary steps. Sorry for creating an additional page again ... any comments? --abcxyz 09:14, 30 March 2012 (EDT)

Leave it as it is. Proof 1 is an intuitively accessible proof which is intellectually straightforward. Proof 2 is not so. --prime mover 09:20, 30 March 2012 (EDT)