Do Uncountable Infinite Sets Exist?
I was looking over a Casella & Berger, “Statistical Inference” 7th edition and have been pondering a question all night as a result.
A finite set is defined as…
A set S is finite if it has the same cardinality as some natural number n in N (The set of all natural numbers) . We then define |S| = n and say that S has n elements. A set is infinite if it is not finite.
A countable set is defined as…
A set S is countable if |S| = |N|. A set S is at most countable if |S| ≤ |N|.
Thus a set S is countable if there is a one-to-one mapping of N onto S, that is, if S is the range of an infinite one-to-one sequence.
Otherwise, the set is uncountable.
My proof skills have always been lackluster, and it has been well over a year since I last attempted a proof, so I was hoping someone who has some recent practice with proofs, set theory, or probability theory could help me figure out an example of an uncountable finite set. I am of the mind, at the moment, that there is no such thing. Casella & Berger give no example…does this mean such a set is not possible? A Google search of “finite uncountable set” and uncountable finite set” yielded less then lackluster results.
Update: Kerry mentions in the comments section that it is a bit strange that I do proofs in my spare time…Kerry prefers to bowl…Vinny likes to update his blog layout. To each their own!
on April 3rd, 2006 at 7:09 am
No such thing as an uncountable finite set. Usually a countable set is defined as being finite or having the same cardinality as the natural numbers. In fact, Casella and Berger mention this when they say an “at most countable” set.
on April 3rd, 2006 at 7:40 am
The real line is an uncountable infinite set. The proof can be found in any real analysis text like that by Rudin or Strichartz or at .
on April 3rd, 2006 at 7:42 am
Addendum: A finite set by definition is countable, so your Google search would not yield anything sensibe.
on April 3rd, 2006 at 8:31 am
Anonymous…I saw Casella & Berger mention ‘at most countable’ and just wanted to be sure that I wasn’t missing something obvious. I am glad I couldn’t think of a uncountable finite set…since clearly the consensus is that one does not exist. How difficult is the proof that they do not exist? I was looking for a proof to follow the logic and could not find one. Does anyone know where a proof can be found?
My intuition is that such a proof should not be difficult. I will go home tonight and spend a little bit more time on it. My worry is that simple propositions in mathematics can often be the most difficult (or tricky i.e. you must know the trick) to prove.
on April 3rd, 2006 at 8:56 am
uhhhhh, is proofmaking some kind of hobby of yours?
In my spare time, I go bowling….but that’s just me.
Good info anyways.
on April 3rd, 2006 at 9:02 am
Kerry,
I have no defense. I had a moment a regression (the psychological not the mathematical kind) where I was curious about how much statistics I have forgotten in the past year. Let me tell you….the saying shouldn’t be use it or lose it…it should be use it or forget you ever knew it…at least in this case.
With that being said…I still have no defense for thinking about mathematical proofs in my spare time.
on April 3rd, 2006 at 10:17 am
Chris, here would be my strategy:
1. Show that there is a one-to-one function from any finite set A to the natural numbers, N. This establishes that |A|
on April 3rd, 2006 at 10:17 am
Agh, it didnt put my entire comment.
2. Show that there is no onto function from a finite set A to the natural numbers N.
on April 3rd, 2006 at 11:40 am
Here is a proof R is uncountable (Cantor’s diagonalization). If they are countable, make an enumeration r1, r2, r3, … Write them out in repeating decimal form. Consider the number x whose ith digit after the decimal is r(i)’s ith digit+1. Then x!=ri for any i which contradicts {ri} being an enumeration.
on May 29th, 2006 at 9:01 am
philosophy of maths is shit and i hate it. diagonal arguments suck. cantor was gay
on November 9th, 2007 at 1:24 am
It seems to me that any finite set is uncountable, if you define the set S countable, iff |S| = |N|. Since there are no 1-to-1 mappings from N onto a finite set, every finite set has to be uncountable.
It might be better to define a set S countable, iff there is a 1-to-1 mapping from S into N.
on August 12th, 2009 at 12:36 am
prime numbers! are uncountably infinite..
on August 12th, 2009 at 3:33 am
Prove it.
on May 5th, 2010 at 6:29 pm
When I’m riding the orange line in Chicago, from Midway into downtown, and I’m looking at all the brick walls, brick buildings, etc. I think to myself “Now there is a definition of uncountable finite.”