Intereting Posts

Is there a function such that $f(f(n)) = 2^n$?
Expression for normal product similar to semidirect product
A counterexample to the isomorphism $M^{*} \otimes M \rightarrow Hom_R( M,M)$
integer solutions to $x^2+y^2+z^2+t^2 = w^2$
Why is it that if “A is sufficient for B” then “B is necessary for A”?
Decomposing a discrete signal into a sum of rectangle functions
First hitting time for a brownian motion with a exponential boundary
Find a set of vectors {u, v} in $R^4$ that spans the solution set of the equations
Why does $\ln(x) = \epsilon x$ have 2 solutions?
How to obtain equation of line of the form $ax + by + c = 0$?
Box Dimension Example
Ideal class group of a one-dimensional Noetherian domain
Why do $2^{\lt\kappa}=\kappa$ and $\kappa^{\lt\kappa}=\kappa$ when the Generalized Continuum Hypothesis holds?
Find all natural numbers $n$ such that $21n^2-20$ is a perfect square.
Can Spectra be described as abelian group objects in the category of Spaces? (in some appropriate $\infty$-sense)

Possible Duplicate:

Proof that the irrational numbers are uncountable

We previously proved that $\mathbb{Q}$, the set of rational numbers, is countable and $\mathbb{R}$, the set of real numbers, is uncountable. What can you say, then, about the cardinality of the irrational numbers?

I would say that the cardinality of irrational numbers is uncountable. That would be because the set $\mathbb{Q}$ is a subset of $\mathbb{R}$. The irrationals is also a subset of $\mathbb{R}$. Basically, my thought is that the continuum is composed of irrationals and rationals (only two subsets of reals). Because we can prove that the rationals are countable by Cantor’s proof, then the remaining subsets of $\mathbb{R}$, the irrationals, has to be uncountable for $\mathbb{R}$ to be uncountable. My concern is how to go about the prove this (rigorous, intro level).

- Comparing the cardinality of sets
- Formulations of Singular Cardinals Hypothesis
- Can we conclude $\prod_{\kappa \in Crd, \kappa=1}^{\kappa<\aleph_\alpha}\kappa=2^{\aleph_\alpha}$ in ZFC?
- Show that 2S = S for all infinite sets
- Are there non-equivalent cardinal arithmetics?
- Problems about Countability related to Function Spaces

- Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$
- How is $\mathbb N$ actually defined?
- Proving that for infinite $\kappa$, $|^\lambda|=\kappa^\lambda$
- Ordinals - motivation and rigor at the same time
- Aren't vacuous statements True and False simultaneously?
- Is $\mathbb{Z}= \{\dots -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable?
- if $f: (0,\infty) \to (0,\infty)$ is a strictly decreasing then $f \circ f$ is decreasing?
- Proving all rational numbers including negatives are countable
- How many different subsets of a $10$-element set are there where the subsets have at most $9$ elements?
- Easiest way to prove that $2^{\aleph_0} = c$

**Claim:** Suppose $A,B$ are two countable sets which are disjoint, then $A\cup B$ is countable.

**Proof:** Fix $f\colon A\to\mathbb N$, and $g\colon B\to\mathbb N$ two bijections given by the fact that these sets are countable. Now define $h\colon A\cup B\to\mathbb N$ by: $$h(x)=\begin{cases}2\cdot f(x) & x\in A\\ 2\cdot g(x)+1 & x\in B\end{cases}$$

Since $A\cap B=\varnothing$ this function is well defined, and it is easy to see that it is in fact a bijection.

**Claim:** $|\mathbb R\setminus\mathbb Q|>\aleph_0$.

**Proof:** Suppose not, then $\mathbb R=(\mathbb R\setminus\mathbb Q)\cup\mathbb Q$ and by the previous claim it is a union of two disjoint countable sets, and therefore $|\mathbb R|=\aleph_0$. Contradiction.

Note, however, that this does not mean *at all* that $|\mathbb R\setminus\mathbb Q|=|\mathbb R|$. It just proves that the irrationals are uncountable.

The proof that the irrationals are of the same cardinality of the continuum is harder. If we want to use Cantor-Bernstein’s theorem we need to find an injection from $\mathbb R$ into the irrationals.

This can be done using continued fractions, the proof is not trivial and quite long, or in a somewhat more general way as discussed here: Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

Lastly, assuming the axiom of choice the result is obvious since $|\mathbb R|=|\mathbb R\setminus\mathbb Q|+\aleph_0=\max\{|\mathbb R\setminus\mathbb Q|,\aleph_0\}$, and we do know that $|\mathbb R\setminus\mathbb Q|>\aleph_0$ and thus we have the equality.

(It is not true without the axiom of choice that addition of cardinals is the same as taking the maximum of the two.)

Hint: The rationals are countable so they can be counted as $q_1,q_2,q_3,\dots$ and if the irrationals are also countable they can be counted as $r_1,r_2,r_3,\dots$ – so then what are you counting if you combine the two sequences (say, alternate them: $q_1,r_1,q_2,r_2,q_3,r_3,\dots$)?

If $A$ and $B$ are countable sets, one knows that the union $A\cup B$ is again countable.

A consequence of this principle is that the complement of a countable subset in an uncountable set must be uncountable (else, you’d get an easy contradiction). That’s exactly your situation since the irrationals are the complement of $\Bbb Q$ in $\Bbb R$.

Your idea sounds pretty rigorous to me. The union of rationals and irrationals yields the reals, thus if both sets are countable $R$ is countable (if you haven’t proved a union of two countable sets is countable in class, think about how you can show this by a simple injection into $N$), which is a contradiction.

- Canonical symplectic form on cotangent bundle of complex manifold
- Finite automaton that recognizes the empty language $\emptyset$
- How to comprehend $E(X) = \int_0^\infty {P(X > x)dx} $ and $E(X) = \sum\limits_{n = 1}^\infty {P\{ X \ge n\} }$ for positive variable $X$?
- Proving the volume of a cone
- How to prove that $\lim\limits_{h \to 0} \frac{a^h – 1}{h} = \ln a$
- What is the expected length of the largest run of heads if we make 1,000 flips?
- Finding when $\mathbb{C}P^n / \mathbb{C}P^{n-2}$ is homotopy equivalent to $S^{2n} \vee S^{2n-2}$ using Steenrod squares
- Simple question on conditional probabilities (multidimensional normal distributions)
- In Borel-Cantelli lemma, what is the limit superior?
- What exactly is a basis in linear algebra?
- Truncated alternating binomial sum
- Calculating a value inside one range to a value of another range
- If $d>1$ is a squarefree integer, show that $x^2 – dy^2 = c$ gives some bounds in terms of a fundamental solution.
- Evans PDE Problem 5.15: Poincaré inequality for functions with large zero set
- fast algorithm for solving system of linear equations