# Talk:Uncountable set

WikiProject Mathematics (Rated Start-class, Mid-priority)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 Start Class
 Mid Priority
Field:  Foundations, logic, and set theory

## Denumerable

The term "non-denumerable" is less common than uncountable, but it is used. I added it because I found a wiki link to the non-existant page "non-denumerable." (It now redirects here.) Here are a few pages on the Internet that use the term: http://www.google.com/search?hl=en&q=non-denumerable+mathematics Crunchy Frog 16:58, 24 August 2005 (UTC)

## lack of references

This may sound very obvious, but with regard to the 'lack of referencing' flag at the top of the page, I notice that the 'countable set' page has a good number of references - presumably if someone enthusiastic can look up those books, they might provide suitable citations for this page also. (Especially as, as I understand it, 'uncountable' strictly just means 'not countable'.) OK, this has probably already been thought of though!! Ab0u5061 18:59, 10 January 2007 (UTC)

## Uncountable in non-AC settings

The article claimed

The foregoing assumes the axiom of choice. Without the axiom of choice, there might exist cardinalities incomparable to ${\displaystyle \aleph _{0}}$ (such as the cardinality of a Dedekind-finite infinite set). These are not considered to be uncountable.

I have never seen this claim - I have always thought uncountable was simply the negation of countable. But I am used to working in settings where AC is assumed. Is the quote above correct? CMummert · talk 20:52, 19 January 2007 (UTC)

The point is that uncountable sets are TOO BIG to be countable. Without the axiom of choice there may be sets which are not countable for other reasons than because they are too big. They cannot be counted simply because you are unable to systematically choose the next element to count, rather than because you run out of natural numbers with which to count them. JRSpriggs 08:24, 20 January 2007 (UTC)
I understand about non-well-orderable sets and the failure of AC. But every time I can remember seeing "uncountable" defined, it was defined as the simple negation of countable. This is likely because every time I have seen it defined it was defined in the context of ZFC. If there is a convention somewhere that a cardinal must be comparable with aleph_0 to be uncountable, then we should certainly include it here, but I have never seen that convention in print.
Basically, I'm asking if a reference can be found for the "without AC" section. It's especially important to get articles like this right because they are probably used as "the" definition by people doing searches on Google. CMummert · talk 14:03, 20 January 2007 (UTC)
You have a point, I could not find a reference which defines it. However, is it more natural to say that a cardinal number ${\displaystyle \kappa \!}$ satisfies ${\displaystyle \kappa >\aleph _{0}}$ or ${\displaystyle \kappa \nleq \aleph _{0}}$? Perhaps we should ask Arthur Rubin (talk · contribs) how it is defined when ~AC. JRSpriggs 10:04, 21 January 2007 (UTC)
Yes, I would be glad to hear Rubin's opinion on the matter. I was going to leave a comment on his talk page but see you already left one.
What you are saying is a perfectly reasonable interpretation of uncountability, and it shows that there is not a unique way to generalize the definition when switching from AC to not-AC. So I am in no hurry to delete the non-AC paragraph, and I wouldn't say we disagree over any of the facts, only (possibly) over their presentation. CMummert · talk 14:07, 21 January 2007 (UTC)
I would probably use it as ${\displaystyle \kappa >\aleph _{0}}$, or possibly even ${\displaystyle \kappa \geq \aleph _{1}}$, but I really don't recall seeing "uncountable" used in contexts where it wasn't applied to a well-orderable set, even without the axiom of choice. In other words, I really can't help you. I think the term that I would use for ${\displaystyle \kappa \nleq \aleph _{0}}$ is non-countable, but that may just be me. (I'm reminded of a model in which ${\displaystyle \beth _{1}}$ covers ${\displaystyle \aleph _{0}}$ but is not equal to ${\displaystyle \aleph _{1}}$). — Arthur Rubin | (talk) 16:45, 21 January 2007 (UTC)
I'd say just cut the section out, unless someone can be found who actually has some experience with models that have these pathologies and knows the literature on them well. We a similar problem at transfinite number with someone who wanted to claim that "transfinite" specifically meant "Dedekind infinite", apparently an attested usage, but not standard in my experience. I don't really think there is any widely agreed convention on these usages. From my point of view that's not surprising; AC is true in the real world, and even most widely-studied models of ¬AC, such as L(R), all satisfy at least countable choice. --Trovatore 23:01, 21 January 2007 (UTC)
I think we should remark early on that the notion of "uncountability" is, in practice, only used when we have (enough of) AC available. (Unlike the notion of "countability", which makes sense already in a (fragment of) ZF.) I have read a few (very few) papers involving Dedekind finite sets, but have never seen "uncountable" mentioned there.
But note that under the definition
${\displaystyle \kappa }$ uncountable ⇔ ${\displaystyle \aleph _{1}\leq \kappa }$,
you would need the axiom of choice to show that the reals are uncountable, which I find weird. (And I think Cantor would agree.)
--Aleph4 01:01, 22 January 2007 (UTC)

I added a list of the four possible generalizations of "uncountable" to not-AC and suggested that it would be best to be specific. JRSpriggs 05:18, 22 January 2007 (UTC)

Good advice, I think, but is this really the place to give it? I'm still not convinced the section should be there, given that none of us has really seen it used in this way or can give a reference showing it to be a standard usage. If we just delete the section, problem solved. --Trovatore 05:58, 22 January 2007 (UTC)

#### Two quotes from the literature

In his 1963/64 paper On the axiom of determinateness (Fund.Math), Jan Mycielski considers implications between various statements associated with AD, among them a weak version of countable choice, and also the statement

Every non-denumerable set of reals contains a perfect subset.

On the other hand, Solovay shows (in his 1970 Annals paper) that the sentence

every uncountable set of reals contains a perfect set

is consistent with ZF+DC. (Emphasis added by me, in both statements).

So Mycielski does not assume a version of AC, and uses the word "non-denumerable"; Solovay constructs a model of DC, in which it is reasonable to talk about "uncountable" sets. (Solovay mentions Mycielski several times in the introduction.)

I think that these two quotes give weak support to Arthur Rubin's suggestion that the word "uncountable" should be replaced by "non-countable" if we do not assume AC (or a sufficiently strong fragment of AC). (I say "weak" because the number two is very small, and both papers are rather old.)

Aleph4 10:16, 22 January 2007 (UTC)

## Omega_1?

I think that the definition

${\displaystyle \Omega _{1}\!}$ is the least regular ordinal greater than ${\displaystyle \omega .\!}$

is not standard notation. Note that ${\displaystyle \Omega _{1}}$ could be undefined: There is a 1985 paper of Moti Gitik (Regular cardinals in models of ZF, Transactions AMS) which proves that the sentence

"No ${\displaystyle \aleph _{\alpha }>\aleph _{0}}$ is regular"

is consistent. --Aleph4 17:45, 22 January 2007 (UTC)

To put it more clearly: I think that the fourth clause (about Omega_1) should be deleted. While it may not be obvious which of the first three clauses are the appropriate generalisation of "uncountable, it seems obvious to me that the fourth is not appropriate. It should be included only if it somebody finds a reference. --Aleph4 22:43, 26 January 2007 (UTC)

I think the whole section should be deleted. It's mostly just confusing. If someone can show that there's a standard agreement as to whether infinite-but-Dedekind-finite sets are "uncountable", that would be different, but I don't believe there is any such standard agreement, and in its absence there's no point in giving a discussion of what the possible agreements might be. In fact it's worse than pointless; it's borderline OR. --Trovatore 23:20, 26 January 2007 (UTC)

## Change to first line?

In mathematics, an uncountable set is an infinite set which is too big to be countable.

To:

In mathematics, an uncountable set is an infinite set which contains too many elements to be countable.

I believe this is slightly more precise, and slightly more understandable. The word "big" may seem intuitive, but it may also lead to misunderstanding and complication. 128.163.129.168 (talk) 22:09, 24 March 2009 (UTC)

Seems reasonable. I changed which to that. --Trovatore (talk) 23:57, 24 March 2009 (UTC)

This is only reasonable in choice settings. In non choice settings, one can envision a set being too "disorganized" to be countable, in the sense that the theory is too weak to "realize" an equivalence of cardinality. —Preceding unsigned comment added by 68.107.107.159 (talk) 17:49, 3 October 2010 (UTC)

The Dedekind-finite infinite sets of cardinality ${\displaystyle \kappa \,}$ satisfy ${\displaystyle \kappa \nleq \aleph _{0}\,}$ and ${\displaystyle \aleph _{0}\nleq \kappa \,.}$ I think that this is what you mean by "disorganized" (i.e. lacking structure in its powerset). While such sets might be called "uncountable" because they are not countable sets, many people do not use the word "uncountable" that way. Rather "uncountable" is often understood to mean that it can be counted as far as counting can go but it still has more elements, that is, ${\displaystyle \kappa \nleq \aleph _{0}\,}$ and ${\displaystyle \aleph _{0}\leq \kappa \,,}$ also written as ${\displaystyle \aleph _{0}<\kappa \,.}$ JRSpriggs (talk) 03:22, 4 October 2010 (UTC)
I don't think that we should focus too much on the non-choice case, and particularly not in the first sentence of the article. There is a section lower down for that. The first paragraph should develop the intuitions that will be more useful, in general. Those will make use of the axiom of choice. — Carl (CBM · talk) 12:25, 4 October 2010 (UTC)

Does it make sense to add this article to Category:Unknown content? Possibly, but I don't know enough about the subject matter. I thought about adding Pi and then Irrational number and that led me here. Any thoughts? --Northernhenge (talk) 20:01, 5 March 2013 (UTC)

Definitely do not add this article, or either of the other two you mentioned. That makes no sense at all as far as I can tell. --Trovatore (talk) 20:15, 5 March 2013 (UTC)
Thanks Trovatore. I'll take your advice. --Northernhenge (talk) 18:47, 6 March 2013 (UTC)

## Uncountable and "bigness"

The comments here, and the article seem, to concur that uncountable means "too-big" to count. An uncountable set is defined as having "too many" elements to count. This seems incorrect as the notion of "bigness" (or "too many-ness") by definition applies as an absolute to the concept of infinity/infinite sets. In terms of "bigness"/"too many-ness", every infinite set is too big to count/has too many elements to count. My understanding of the concept of an uncoutable set is as a set that it is not possible to EVEN TO BEGIN to count. For instance, there are an infinite number of integers, but the set is countable: 1, 2, 3.... etc ad infinitum. There are also an infinite number of numbers between zero and 1 but these are uncountable. We can start with the number zero ..... but then that's it, we cannot get to the next number in order to begin our count. Would the next number be 0.1, or 0.01 or 0.001 or etc.? Surely this is the "definition" of uncountable? The article as is seems indecipherable, continuing this further by introducing the notion of a "degree of uncountability" without explaining this other than by a statement that it is the case. If the article is not actually incorrect then it is too technical and with an inadequate introduction for a non-technical publication. LookingGlass (talk) 08:10, 4 January 2014 (UTC)

You need to give up your preconceived notions which are getting in the way of understand this. Just accept that, in this context, "countable" means that there is an injection from the set into the natural numbers, i.e. there is a way of listing the elements such that you could count up to any one of them by going thru that same list in the same order. JRSpriggs (talk) 09:25, 4 January 2014 (UTC)
Your argument about there being no "next" number after zero applies equally well to the rationals, yet the rationals are countable. It's true that a countable set can be placed in an order where each element has a "next" element, but this ordering need not have any relation to any "normal" ordering that may be defined on the set. Mnudelman (talk) 21:08, 5 September 2015 (UTC)

## If an uncountable set X is a subset of set Y, then Y is uncountable

Hi, being a modest mathematician, I was wondering if this statement could be detailed a little more, and specifically, if it could be explicitely said whether or not this requires the axiom of choice to be proven.

I could offer to use reduction to absurdity, saying that if a one-to-one correspondance f can be established between Y and ℕ, then, the restriction of f to X noted f|X is a one-to-one correspondance between X and a subset of ℕ, thus X is countable, which is absurd. However, does the argument using f|X require the axiom of choice in this case ?

Thank you very much,--ByteMe666 (talk) 21:04, 27 November 2017 (UTC)

I'm sorry if I seem like I'm rambling, but I've given it some more thought: defining f|X requires, according to my reasoning, extracting X from Y by means of writings such as X={x∈Y|x∈X} (which seems trivial, but I only wish to show that such manipulation of writings does not require the axiom of choice), which then enables to identify {f(x)|x∈X} which is a subset of ℕ, and f|X is obviously a bijection between X and {f(x)|x∈X} because f is a bijection.

I apologize again if I seem to dwell on trivial matters, but for neophytes to the axiom of choice such as myself, it is sometimes very easy to let the usage of the axiom of choice go unnoticed, therefor I tend to be excessively careful and make every demonstration very explicit.

If my attention to detail is deemed excessive, please disregard. Thank you.--ByteMe666 (talk) 21:38, 27 November 2017 (UTC)

Technically, questions about the subject matter should appear at WP:RD/Math, not here. But the answer is short enough that I don't see a lot of harm. Please direct any followup questions to WP:RD/Math.
The answer is, no, you don't need the axiom of choice. The contrapositive of the statement is that any subset of a countable set is countable. That's easily proved without AC, because a countable set is either finite (in which case every subset is finite, thus countable), or else it has a bijection with the natural numbers. The natural numbers are wellordered, so you can show that any subset is countable by collapsing the ordering.
However you do need excluded middle to show the equivalence with the contrapositive, and intuitionists do not necessarily accept the result. --Trovatore (talk) 22:13, 27 November 2017 (UTC) Actually I think I messed up that last bit a little. See subcountability for more information, and again, if you want to discuss it in more detail, please use the mathematics reference desk. --Trovatore (talk) 22:16, 27 November 2017 (UTC)
The contrapositive argument is much clearer than what I wrote. Thank you. As for how to use the different segments of Wikipedia, your directions are duly noted. Thank you very much.--ByteMe666 (talk) 22:27, 27 November 2017 (UTC)
Actually, upon closer inspection, the collapsing of the ordering argument isn't so clear in my mind. I know it is useful to prove that a surjection can be turned into a bijection, but I don't see how this works in this case. I will look up the references you have provided, and take it from there. Thank you.--ByteMe666 (talk) 22:55, 27 November 2017 (UTC)