Wikipedia:Reference desk/Archives/Mathematics/2014 June 15

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 15

Countable cover needs choice?

Does the observation that any open cover of the reals has a countable subcover require something like countable choice, or is it possible to do without any choice axiom? Black Carrot (talk) 19:39, 15 June 2014 (UTC)

I don't see how this requires the axiom of choice. If $(U_{\alpha })_{\alpha \in A}$ is an open cover of the reals, then it is also an open cover of the compact set $[-n,n]$ for any positive integer $n$. Closed and bounded sets are compact (by Heine–Borel theorem), hence there is a finite cover $(U_{\alpha })_{\alpha \in A_{n}}$ of $[-n,n]$. The set ${\hat {A}}=\bigcup _{n}A_{n}$ is countable as a countable union of finite sets, and the reals are covered by the $U_{\alpha }$ with $\alpha \in {\hat {A}}$. Am I missing something? —Kusma (t·c) 20:08, 15 June 2014 (UTC)

Well, the potential problem is that there might be more than one finite cover of each of the intervals [−n,n], and you have to pick a sequence of finite covers.

I don't actually know the answer, though — that is, I don't know how to get a model of ZF in which the reals are not Lindelōf. --Trovatore (talk) 20:19, 15 June 2014 (UTC)

Oh yeah, sorry. I do mathematical analysis, so I am apparently too naive to talk about set theory :) —Kusma (t·c) 14:44, 16 June 2014 (UTC)

I remember my first-year-grad-school real-analysis prof talking about how hard it was to find instances of AC in proofs. He said, "It's just such a reasonable thing to do."

I think he was right. If you understand the motivating picture of set theory, it is very hard to avoid giving assent to AC. AC really is "self-evident" in that sense.

Still, it is useful to know what can be proved without it, because those results still hold in some models (like L(R)) that have some very nice properties (although all "nice" models I'm aware of do satisfy countable choice for sets of reals, so not directly relevant to this example).

And in order to figure out what can be proved without it, you need to go through the exercise of learning what "reasonable" mental operations correspond to it. --Trovatore (talk) 17:04, 16 June 2014 (UTC)

Right, that's exactly the problem. Not just that you need to choose each cover, but that you need to choose a canonical ordering on the elements of each cover in order to get an enumeration of the union. The other construction I know also seems to require a union of countable many sets, which is why I wonder if it might be necessary to the theorem. Black Carrot (talk) 22:00, 15 June 2014 (UTC)

It seems likely, but as I say I don't know a proof. You might look in the Handbook of Set-theoretic Topology. --Trovatore (talk) 22:17, 15 June 2014 (UTC)

According to [1], the reals are Lindelof is equivalent to the axiom of countable choice holding for subsets of real numbers. It cites [2], which covers this in the opening theorem.Phoenixia1177 (talk) 07:17, 16 June 2014 (UTC)

Nice find!

Note that the second reference claims that, to recover countable choice for sets of reals, all you need is for the natural numbers, with the discrete topology, to be Lindelöf. Since in the discrete topology, all sets are open, that means that if countable choice for sets of reals fails, then there is a collection of sets of naturals that covers the naturals, but such that no countable subcollection covers the naturals.

This no longer seems to be about topology at all. --Trovatore (talk) 07:29, 16 June 2014 (UTC)

Thank you:-) From [3] the reals being a countable union of countable sets implies not CC(R) -Fefermen and Levy constructed a model (M9) in which this is the case. Pg.142 in "The Axiom of Choice" by T.J. Jech constructs a model of ZF in which this is the case - I don't have a free online link for that, though (nor anywhere else this is shown)- You can also look at "Set Theory and the Axiom of Choice", section 10 "Changing Cardinalities" discusses the model (again, no free source). This [4] also mentions the F-L model (A8 here), not much detail, though. Also from [5], CC(R) fails iff Lindelof = Compact for T1 spaces (I found this interesting). --With varying degrees of applicability to the main question, these may be of further interest on the matter: [6], [7], [8], [9], [10]. --Thank you for the interesting question:-)Phoenixia1177 (talk) 09:11, 16 June 2014 (UTC)

This is perfect :) Thank you so much for those references, though they are taking some time to digest. So my original condition is actually equivalent to CC(R), by "When is N Lindelöf". Is it correct that CC(R) is independent of ZF? Which reference would show that? Black Carrot (talk) 22:14, 17 June 2014 (UTC)

No problem, they were very enjoyable to read:-) For CC(R) being independent: any model with choice has CC(R), several of the refs above mention there being a model in which CC(R) fails, thus, CC(R) is independent since we have models of ZF in which it fails and in which it holds. Probably the best refs would be the two not online (Cohen and Jech). Although, Pg.323 of [11] mentions there being models of ZF for which CC(R) fails, as does [12] - though not much detail is supplied.Phoenixia1177 (talk) 05:07, 18 June 2014 (UTC)

Regularity needs choice?

Without any choice axiom, does regularity imply no infinite descending chain of membership? The article seems to assume that for any infinite descending chain there will be a function to the members of that chain from the naturals, but without choice it doesn't seem obvious that such a function, as a set, would exist. Black Carrot (talk) 19:44, 15 June 2014 (UTC)

So first of all let me point out that, in my experience, the usual name is axiom of foundation rather than axiom of regularity. I don't know why Jech uses the latter; I would prefer to move our article.

Then the point is that many of these axioms have different forms used by different authors, and they are not all equivalent if you drop other axioms. I suppose you're taking the axiom in the form "every nonempty set X has an element disjoint from X"? That does imply no infinite descending epsilon-chain. Just looked at the article to see what you meant — an infinite descending epsilon-chain is by definition such a function f; that's just what you get when you translate the English phrase into set-theoretic language.

However, sometimes Foundation is simply taken to mean there is no infinite descending epsilon-chain, and in that case you do need some choice to show the equivalence, I think. --Trovatore (talk) 19:55, 15 June 2014 (UTC)

Regularity is the word in my textbook, maybe it's the sort of word that's far enough out of date that it's only used in school :) That is the definition I intended, about every set is disjoint from one of its elements. I guess what I'm asking is, how do you construct the set representing that sequence, or equivalently the set containing the members of the sequence, given only the set with the infinite chain? For instance, given a set which had a membership loop, you could in a finite number of steps construct the set that contains the members of the loop. Because you can construct it, it exists, so after that you can apply the axiom to forbid it and the set that caused it. But would it be possible for the set with the chain strung out vertically to exist, without a set with the chain strung out horizontally existing? So that whether it broke the rules would be sort of invisible. Black Carrot (talk) 22:16, 15 June 2014 (UTC)

The definition of "infinite" is that the naturals embed, so the function exists by definition. --Trovatore (talk) 22:18, 15 June 2014 (UTC)

Oh, although I suppose you could get into some difficulty in a pathological model that has sets of cardinality incomparable with $\aleph _{0}$, if you consider those cardinalities "infinite". --Trovatore (talk) 22:21, 15 June 2014 (UTC)

If we're talking about weak forms of choice, weird cardinalities are pretty much the point :) My book actually defines infinite as not finite, with the existence of a countable subset in every infinite set as a theorem that requires the axiom of choice. But I'm really talking external to the model here. Even if I can see that there is an infinite descending chain in the model, it's not clear to me that the axioms can prove it, so it's not clear that the axiom of foundation can forbid it. Black Carrot (talk) 23:56, 15 June 2014 (UTC)

Well, if it's true in every model, then there's a proof, by the completeness theorem. So models are likely to be the best way to think about it.

So your concern is that there might be an infinite (meaning "not equinumerous with any natural number) chain, but no way to recover an embedding of the naturals into the chain.

I think we can't really go any further until you say what you mean by "chain" here. To me "infinite chain" pretty much means an embedding of the naturals. I'm not sure what else it could mean. In some contexts it means "suborder of a partial order on which the restriction is a linear order", but that doesn't seem to make a lot of sense here, as epsilon is not necessarily a partial order anyway (may not be transitive), and taking the transitive closure would open up a whole 'nother can of worms. --Trovatore (talk) 00:29, 16 June 2014 (UTC)

I think I've figured out the answer to my question, but now I have a slightly different question. If I understand Separation right, we can take from Infinity the minimal "inductive" set, and call it the Naturals, and with Replacement we can apply induction over the Naturals for any first-order statement, and the entire image of that inductive process is a set. So, statements related to set membership can be built up by induction and Replacement into a set of all descending chains from a base set, and each of those chains will have to have a last element by Foundation, making them finite. So ZF without choice can build all descending chains and prove that they are finite. Does that sound reasonable? But all of this is in a first-order theory, which means that there are non-standard models of this process, which produce descending chains that are "finite" internally, but infinite or even uncountably long from the outside. How do we prevent that? Black Carrot (talk) 17:26, 16 June 2014 (UTC)

I'm ... not quite sure what you're getting at here. But I see a bit of a red flag.

The red flag is that you're mixing objects from the universe of discourse (your "base set" and descending chains from it) with syntactic objects like "proofs from ZF". This may be just fine, depending on what exactly you mean, but since I'm not sure what you mean, I'm not sure whether it's fine.

Keep in mind that ZF has access only to objects that have actual names, except in the context of a sub-argument where you temporarily give them names ("existential instantiation"). Most sets do not have names. --Trovatore (talk) 17:43, 16 June 2014 (UTC)

Sure, let me try to be clearer. With the first part, I'm imagining a sort of bucket of clearly identified sets. Starting with whatever set was chosen arbitrarily, each application of an axiom adds some set to the bucket. That is, for any set B, there is some set C with certain properties related to B, and some set D with other properties related to C, etc. At some point, we've got a set of all descending chains from B, and it has a temporary name, and hopefully we know it is not empty. In the second part, I'm concerned that these chains are indexed by the natural numbers, which in a nonstandard model will be very long. Black Carrot (talk) 21:55, 16 June 2014 (UTC)