In Stephen Abbott's &quot;Understanding Analysis&quot; book, he proves that the set of Real numbers is an uncountable set in theorem 1.4.11. My issue with the proof is that it seems too strong, as in it seems like you can prove that the set of Integers or Rationals are uncountable with the exact same proof, just replace Reals with Integers or Rationals. Where does he invoke properties of the Reals that the Integers and Rationals don't have? I know I have to be missing something... Here's the theorem and proof, copied straight out of Abbott: Theorem 1.4.11. The set R of Real Numbers is uncountable. Proof.  Assume that there does exist a 1–1, onto function f : N → R. Again, what this suggests is that it is possible to enumerate the elements of R. If we let x1 = f(1), x2 = f(2), and so on, then our assumption that f is onto means that we can write (1) R ={$x_1$, $x_2$, $x_2$, $x_2$,...} and be conﬁdent that every real number appears somewhere on the list. We will now use the Nested Interval Property (Theorem 1.4.1) to produce a real number that is not there. Let $I_1$ be a closed interval that does not contain $x_1$. Next, let $I_2$ be a closed interval, contained in $I_1$, which does not contain $x_2$. The existence of such an $I_2$ is easy to verify. Certainly $I_1$ contains two smaller disjoint closed intervals, and $x_2$ can only be in one of these. In general, given an interval $I_n$, construct $I_{n+1}$ to satisfy (i) $I_{n+1}$ ⊆ $I_n$ and (ii) $x_{n+}$ $\mathrel{{\epsilon}\llap{/}}$ $I_{n+1}$. We now consider the intersection $\cap_{n=1}^{\infty}I_n$. If $x_{n_0}$ is some real number from the list in (1), then we have $x_{n_0} \mathrel{{\epsilon}\llap{/}} I_{n_0}$, and it follows that $x_{n_0} \mathrel{{\epsilon}\llap{/}} \cap_{n=1}^{\infty}I_n$. Now, we are assuming that the list in (1) contains every real number, and this leads to the conclusion that $\cap_{n=1}^{\infty}I_n =∅$. However, the Nested Interval Property (NIP) asserts that $\cap_{n=1}^{\infty}I_n \mathrel{{=}\llap{/}}∅$. By NIP, there is at least one $x ~\epsilon \cap_{n=1}^{\infty}I_n$ that, consequently, cannot be on the list in (1). This contradiction means that such an enumeration of R is impossible, and we conclude that R is an uncountable set.
28625
If we map every integer to a string that represents a rational number, and produce a number different from all the ones listed, we are essentially following Cantor's algorithm. But why does it not apply? Is it because we can't be certain that the number produced is a rational number?
66319
Possible Duplicate:             Does $\mathbb R^2$ contain more numbers than $\mathbb R^1$? I know that there are the same number of even integers as integers, but those are both countable sets. Does the same type of argument apply to uncountable sets? If there exists a 1-1 mapping from $\mathbb R^2$ to $\mathbb R^1$, would that mean that 2 real-valued parameters could be encoded as a single real-valued parameter?
96728
I saw a proof of the following theorem.     Every open subset $\mathcal{O}$ of $\mathbb{R}$ can be written uniquely as a countable union of disjoint open intervals.   The proof was convincing, but can anyone help me writing out explicitly such a representation of the interval $(0,1)$? Or maybe $(0,1)$ itself is already such a representation? Can I write it as countable union of "smaller" disjoint open intervals?
76683
How can I prove that the set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable?  Edit:  This answer came to mind.  Is it correct?  This answer just came to mind.  By contradiction suppose the set is $\{f_n\}_{n \in \mathbb{N}}$.  Define the function $f: \mathbb{N} \to \{0,1\}$ by $f(n) \ne f_n(n)$.  Then $f \notin\{f_n\}_{n \in \mathbb{N}}$.
83683
Let $X$ be a set and consider the collection $\mathcal{A}(X)$ of countable or cocountable subsets of $X$, that is, $E \in \mathcal{A}(X)$ if $E$ is countable or $X-E$ is countable. If $X$ is countable, then $\mathcal{A}(X)$ coincides with the power set $\mathcal{P}(X)$ of $X$. Now suppose that $X$ is uncountable. Assuming the axiom of choice, we can conclude that $\mathcal{A}(X) \ne \mathcal{P}(X)$, since $|X| = |X| + |X|$. So the question is:     Can we prove in ZF that $\mathcal{A}(X) \ne \mathcal{P}(X)$ for every uncountable set $X$?   I'm assuming that a set $X$ is uncountable if there is no injective function $f : X \rightarrow \mathbb{N}$.
34422
I am reading a proof that the cantor set is uncountable and I don't understand it. Hopefully someone can help me.  Let $C$ be the Cantor set and $x\in C$.  Then there exists unique $x_k\in \{0,2\}$ such that $x=\sum_{k\in \mathbb N}\frac{x_k}{3^k}$. Conversely every $x$ with this representation lies in C.  If $C$ would be countable then there would exists a injective map $f:C\rightarrow \mathbb N$.  Let $f^{-1}(i)=\sum_{k\in \mathbb N}\frac{x_{ik}}{3^k}$ or $f^{-1}(i)=\emptyset$.  Set $z_k=2-x_{i_k}$, then z=$\sum_{k\in \mathbb N}\frac{z_k}{3^k}$  Then $z$ is in the cantor set but z isn't in the pre-image of $f$.  Questions:   Shouldn't it be $z_k=2-x_k$? I understand that z lies in C but why it is not in the pre image of f?   Thanks in advance
88221
Sorry if this problem is repeated.  Is there a nonempty perfect set in $\mathbb{R}^1$ which contains no rational number?  Proof sketch: This set must be uncountable because any nonempty perfect set in $\mathbb{R}^k$ is uncountable.   We know that Cantor set (C) is perfect set on a line. If we take $E=C+\sqrt{2}=\{x+\sqrt{2}: x\in C\}$. Will this set be an answer to above problem?
67370
I've been told that there are precisely the same number of rationals as there are of integers. The set of rationals is countably infinite, therefore every rational can be associated with a positive integer, therefore there are the same number of rationals as integers. I've ignored sign-related issues, but these are easily handled.  To count the rationals, consider sets of rationals where the denominator and numerator are positive and sum to some constant. If the constant is 2 there's 1/1. If the constant is 3, there's 1/2 and 2/1. If the constant is 4 there's 1/3, 2/2 and 3/1. So far we have counted out 6 rationals, and if we continue long enough, we will eventually count to any specific rational you care to mention.  The trouble is, I find this very hard to accept. I have two reasons. First, this logic seems to assume that infinity is a finite number. You can count to and number any rational, but you cannot number all rationals. You can't even count all positive integers. Infinity is code for "no matter how far you count, you have never counted enough". If it were possible to count to infinity, it would be possible to count one step less and stop at count infinity-1 which must be different to infinity.  The second reason is that it's very easy to construct alternative mappings. Between zero and one there are infinitely many rational numbers, between one and two there are infinitely many rational numbers, and so on. To me, this seems a much more reasonable approach, implying that there are infinite rational numbers for every integer.  But even then, this is just one of many alternative ways to map between ranges of rationals and ranges of integers. Since you can count the rationals, you can equally count stepping by any amount for each rational. You can use 1..10 for the first rational and 11..20 for the second etc. Or 1..100 and 101..200 etc, or 1..1000 and 1001..2000 etc. You can map finite range of integers of any size to each rational this way and, since there is no finite upper bound to the stepping amount, you could argue there are potentially infinite integers for every single rational.  So... can anyone convince me that there is a single unambiguous correct answer to this question? Are there more rational numbers than integers, or not?  EDIT  Although I've already accepted an answer, I'll just add some extra context.  My reason for questioning this relates to the Hilbert space-filling curve. I find this interesting because of applications to multi-dimensional indexing data structures in software. However, I found Hilberts claim that the Hilbert curve literally filled a multi-dimensional space hard to accept.  As mentioned in a comment below, a one meter line segment and a two meter line segment can both be seen as sets of points and, but (by the logic in answers below), those two sets are both the same size (cardinality). Yet we would not claim the two line segments are both the same size. The lengths are finite and different. Going beyond this, we most certainly wouldn't claim that the size of any finite straight line segment is equal to the size of a one-meter-by-one-meter square.  The Hilbert curve reasoning makes sense now - the set of points in the curve is equal to the set of points in the space it fills. Previously, I was thinking too much about basic geometry, and couldn't accept the size of a curve as being equal to the size of a space. However, this isn't based on a fallacious counting-to-infinity argument - it's a necessary consequence of an alternative line of reasoning. The two constructs are equal because they both represent the same set of points. The area/volume/etc of the curve follows from that.
19720
So, to explain the title, I'm referring to the necessity of the axiom of choice in the existence of a well ordering on reals, or any uncountable set.  Now, while tweaking some sets, I came across this :  We start with the natural numbers, $N$. We take the power set of the naturals, $P(N)$.  Then we remove all the finite subsets of $N$ from $P(N)$. Let us call this new set $S$. This set is the set of all infinite subsets of $N$.  It is easy to show that $S$ has uncountable cardinality, same as that of real numbers. This is because the removal of finite subsets only removes a countable number of elements. (Haven't posted this deduction, for it is very easy, but I may post it if it is not so evident)  Now, we seek to find an ordering on the set $S$. Every set in this set is an infinite subset of natural numbers, so each of these sets are well ordered by the natural ordering of $N$.  Taking any two sets in $S$, say $A$, and $B$, we seek to order them by checking their elements lexicographically. We compare the first two elements in $A$, and $B$. Let them be $a_1$, and $b_1$ respectively. If $a_1 = b_1$, then we move on to the second elements in the sets, $a_2$, and $b_2$, and so on. If, at any point, $a_n &lt; b_n$, then $A &lt; B$, or if $b_n &lt; a_n$, then $B &lt; A$.  This order seems to be a well ordering of the uncountable infinity of reals. I don't seem to have invoked the axiom of choice anywhere in the construction of this set $S$.  So, why isn't this a well ordering on the uncountable of reals?
48495
If you have an uncountable subset of $\mathbb{R}$, which is dense in $\mathbb{R}$, is its complement countable?   I'm trying to see if you can take the set of irrationals, remove a countable amount, and still have a dense subset in $\mathbb{R}$.If this is the case, this sets complement would still be countable.  My goal is to determine if you can have an uncountable subset of $\mathbb{R}$, which is dense in $\mathbb{R}$, yet its complement is uncountable.  If somebody could just let me know if this is possible or not I would appreciate it. Thanks.
10700
Given any uncountable subset $S$ of the unit interval. Then $S$ clearly has an accumulation point and indeed uncountably many (which might also be a nice exercise). So my question is: Is there an accumulation point, that again lies in $S$?
26129
Can someone point me to a proof that the set of irrational numbers is uncountable? I know how to show that the set $\mathbb{Q}$ of rational numbers is countable, but how would you show that the irrationals are uncountable?
84543
Let $U$ be a collection of pairwise disjoint open intervals. That is, members of $U$ are open intervals in $\mathbb{R}$ and any two distinct members of $U$ are disjoint. Show that $U$ is countable.  My attempted proof:  Let $U \subseteq \mathbb{R}$ be a collection of pairwise disjoint opern intervals. Let $(a,b) \subseteq U$ be one such interval. Since $\mathbb{Q}$ is dense in $\mathbb{R}$, there exists a rational number $q_{a,b} \in (a,b)$. Define $f: U \to \mathbb{Q}$ by $f((a,b))=q_{a,b}$. As $f(a_1,b_1)=f(a_2,b_2)$, or $q_{a_1,b_1}=q_{a_2,b_2}$, implies $(a_1,b_1)=(a_2,b_2)$, we deduce that $f$ is injective. It was proved already in my lecture class that $\mathbb{Q}$ is countable, and that union of countable sets is countable. Thus, we deduce that $U$ is countable. (End of attempted proof)  I feel confident about my proof except the injectivity part. I was looking for help there, assuming the rest of my proof is cogent. If not, please let me know how I can improve on it.
112359
This is part of a bigger problem I'm trying to prove, but my argument relies of the validity of the following idea. Note that when I say countable, I don't mean finite -- I mean countable infinity.   Consider the set of natural numbers, $\mathbb{N}$. Now take a countable subset of them, call it $\mathsf{S}_1$. Then take a countable subset of $\mathbb{N}\setminus{\mathsf{S}_1}$ and call it $\mathsf{S}_2$. Then take a countable subset of $\mathbb{N}\setminus\{{\mathsf{S}_1}\cup{\mathsf{S}_2}\}$ and call it $\mathsf{S}_3$. Continue in this manner to construct $\mathsf{S}_i$'s such that ${\mathsf{S}_i}\cap{\mathsf{S}_j}=\emptyset$ for $i≠j$.  My question is this: is it necessarily the case that eventually there will be finitely many $\mathsf{S}_i$'s with $\mathbb{N}\setminus\bigcup_{i}{\mathsf{S}_i}={P}$ where $P$ is either empty or finite? My guess is yes, but I'm not how to prove it or how to find a counterexample.
95692
Countable sets have the same cardinality as the natural numbers (or a subset of the natural numbers, depending on who you ask).  Can one make the same claim about uncountable sets and real numbers?  In other words, do all uncountable sets have same cardinality as real numbers?
76017
I know and I have proved more than once that the set of irrational numbers ($\mathbb{I}$) is uncountable, but now I'm given to solve this problem:   Show that $|\mathbb{I}|=|\mathbb{R}|$,  How can I do that?  Do I need to assume the Continuum Hypothesis in order to that statement to be true?  Thanks
40613
I recently started studying set theory and am having quite a bit of difficulty accepting Cantor's diagonal proof for the uncountability of the reals. I also saw a topological proof via nested sets for uncountability which still does not satisfy me completely, given that just like the diagonal it relies on a never ending process. In fact, the nested sets proof sounds very much like the diagonalization proof to me.  Do all proofs of the uncountability of the reals involve diagonalization? Are there any other proofs I can look at to understand? I couldn't find any on searching stack exchange. Thanks.