I have recently watched a video by "Undefined Behavior", explaining countable and uncountable infinities, and showing why uncountable infinity is larger than countable infinity. He then stated that a question had been asked if there is some infinity that's in-between the two (larger than countable, but smaller than uncountable), and that it has been proven that this question in unsolvable. However, he did not mention any name of the theorem proving this, and also did not show any proof. What is the proof that this problem is unsolvable?
115977
I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not exist a set with a cardinality less than the reals and no set strictly greater than the natural numbers.) is neither true or false.  This is utterly baffling to me, If it's possible to construct a set between $\mathbb{N}$ and $\mathbb{R}$ then this statement is demonstrably false, but if not then the statement is true.  This seems to be a straitforward deduction, but many with a more advanced understanding of the topic matter believe CH to be neither.  How can this be?
116757
Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements.  I've seen a simple natural language statement here and elsewhere that's supposed to illustrate this: "I am not a provable statement." which leads to a paradox if false and logical disconnect if true (i.e. logic doesn't work to prove it by definition). Like this answer explains: .  The natural language statement is simple enough for people to get why there's a problem here. But Gödel's incompleteness theorems show that similar statements exist within mathematical systems.  My question then is, are there a simple unprovable statements, that would seem intuitively true to the layperson, or is intuitively unprovable, to illustrate the same concept in, say, integer arithmetic or algebra?  My understanding is that the continuum hypothesis is an example of an unprovable statement in Zermelo-Fraenkel set theory, but that's not really simple or intuitive.  Can someone give a good example you can point to and say "That's what Gödel's incompleteness theorems are talking about"? Or is this just something that is fundamentally hard to show mathematically?  Update: There are some fantastic answers here that are certainly accessible. It will be difficult to pick a "right" one.  Originally I was hoping for something a high school student could understand, without having to explain axiomatic set theory, or Peano Arithmetic, or countable versus uncountable, or non-euclidean geometry. But the impression I am getting is that in a sufficiently well developed mathematical system, mathematician's have plumbed the depths of it to the point where potentially unprovable statements either remain as conjecture and are therefore hard to grasp by nature (because very smart people are stumped by them), or, once shown to be unprovable, become axiomatic in some new system or branch of systems.
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.
100909
Possible Duplicate:          Those terms keep confusing me. Could somebody give a clear and unambiguous definition? How do we prove a set is countable, finite, ...? I know that there are more real numbers than there are integers. How do we prove this? What about other sets like $\mathbb{Z, Q, C}$?
52256
For any set $A$, I proved already that $|A| &lt; |\mathcal{P}(A)|$ by injecting $A \to \mathcal{P}(A)$ by $a \mapsto \{a\}$ and then demonstrating, by contradiction, that no surjection can exist. I want to prove that there is no largest cardinal number, but the argument $$|\mathbb{N}| &lt; |\mathcal{P}(\mathbb{N})| &lt; |\mathcal{P}(\mathcal{P}(\mathbb{N}))| &lt; |\mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N})))| &lt; \ldots$$ Perhaps more formally, I could suppose for the sake of contradiction that $|A|$ is the largest infinite cardinal, but this theorem implies that $|\mathcal{P}(A)| &gt; |A|$, a contradiction. How can I make this proof sufficiently formal?
82138
I am trying to prove that algebraic numbers are countably infinite, and I have a hint to use: after fixing the degree of the polynomial, consider summing the absolute values of its integer coefficients, and setting the sum less than or equal to $m$, for each $m \in \mathbb{N}$. I am also allowed to use the fact that every polynomial has a finite number of roots. I am not sure where to begin... Perhaps after fixing the degree of the polynomials, I could try enumerating them, and after proving countability of the set that contains the roots of all polynomials of a certain degree, I could state that the union of infinitely many ($\bigcup_{n=1}^{\infty}$, $n \in \mathbb{N}$) countably infinite sets is countable, and thus the algebraic numbers are countably infinite, too, but I am not sure if this is a good approach/how to enumerate the polynomials. Thanks!
63975
Prove that a set $A$ is infinite if and only if $A$ contains a countable subset $C$. I know I have to build a sequence and then I'll get a countable subset, but I don't know how to build that sequence from a infinite set.
110211
Is every open subset of $\mathbb{R}$ uncountable?  I was crafting a proof for the theorem that states every open subset of $\mathbb{R}$ can be written as the union of a countable number of disjoint intervals when this question came up.  I feel like the answer is yes, but I'm not sure how to go about proving it or whether there is a crazy construction (like the Cantor Set)  that creates a countable, open subset of $\mathbb{R}$. Any ideas?
1939
Loosely, a number is describable if it can be unambiguously defined by a finite string over a finite alphabet. Numbers such as $\frac{1}{3}$, $\sum_{n=0}^\infty \frac{1}{n!}$, and "the ratio of circumference to diameter of a circle" are all describable numbers. One can  show that the set of all such numbers is countable.  Let $U$ be the set of indescribable real numbers. I "claim" $U$ is empty, and so every real number is describable. Suppose to the contrary. Place a well-order on $U$ (this can be done assuming the Axiom of Choice). The least element $u$ of $U$ admits the description "the least element of $U$ according to the specified well-order", contradicting the indescribability of $u$.  Obviously, something has gone awry here. I suspect it is some combination of my loose definition of describability and my self-referential "description" of $u$. My (slightly open-ended) question is "What's wrong here?".  P.S. There is a  addressing something rather like my question. As I understand it, the author's response is "the given description isn't really a description". If so, I'd enjoy some elaboration.
28805
If $y\in E\cap E+x$ then $y=h=h'+x \implies x=h-h'$ for $h,h'\in E$. Likewise, if $x=h-h'$, then $h\in E\cap E+x$. So that $E\cap E+x$ is non empty iff $x=h-h'$ where $h,h'\in E$. Thus, if there exists a real $x$ which cannot be expressed as above, the result is proven. The problem is I cannot prove that such an $x$ must exist. I have tried assuming that all real $x$ are of that form, but that gives me nothing except that $E$ must be uncountable and unbounded. Any hints?
123408
The proof that the set of real numbers is uncountably infinite is often concluded with a contradiction. In the following argument I use a similar proof by contradiction to show that the set of rational numbers can be shown to be uncontably infinite:  Let us assume that the set of rational numbers is countable. This implies that we can write all the rational numbers between 0 and 1 in a list. Let us say, it looks something like this:     $ 0.\color{red}0000000001000000...\\ 0.0\color{red}10000001110000...\\ 0.10\color{red}000001000000... \\ ....$   ans so on. Now, create a new number that picks $n^{th}$ digit from $n^{th}$ number and  changes it to $0$ if it is $1$ and vice versa.     $0.101.... $   This number, say $x$, is between 0 and 1, and so it must appear in the list. Suppose it appears at the $n^{th}$ position in the list. However, based on how we constructed $x$, we know that the $n^{th}$ digit of $x$ is different from the $n^{th}$ digit of the $n^{th}$ number in the list. So, $x$ should be different from the $n^{th}$ number in the list at the $n^{th}$ digit and hence, this is a contradiction. We can conclude that such a list of the rational numbers does not exist and hence, the set of rational numbers is uncontably infinite.  I know that there is another mapping between the set of rational numbers and natural numbers that can show that there is one-to-one mapping between the two sets (). However, the above proof in that sense is not really conclusive and that the set of real numbers might also be countably infinite and it is just that we are not yet aware of the mapping.  Please provide your comments if the above proof is somehow flawed for rational numbers or if I'm missing something.
107144
I know that the set of functions $ f:\mathbb N \to \mathbb N$ is uncountable, but what if we consider only $f$ such that $f$ is increasing? I want to know if this set is countable D: and also the case of bijective and increasing (clearly if the firstone holds then this too). I think that it could be possible that it's countable
22378
In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?  Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: \mathbb{N} \rightarrow T$. And $S \subseteq T = \{ f(n) \ | \ n \in \mathbb{N} \}$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) \in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) \in S$. And because $S$ is infinite, we continue forever. Now consider the function $\beta : \mathbb{N} \rightarrow S$ which sends $k \rightarrow f(n_{k})$.   So in order for $S$ to be countable, $\beta$ would have to be a bijection. $\beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.   Edit: $\beta$ also needs to be surjective. So for every $r \in S$ there exists a $q \in \mathbb{N}$ such that $\beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) \in \{n_{1}, n_{2}, ..., n_{k} ... \}$, so we can let $f^{-1}(r) = n_{d}$. Thus $\beta(d) = f(n_{d}) = r$.
118422
Here is the problem and my attempted solution. Problem: Let $m^*(E) &gt; 0$. Define the Rational Equivalence Relation on $E$ by $x \sim y$ if, any only if, $x - y \in \mathbb{Q}$. Show that the choice set $(c_E)$ for the Rational Equivalence Relation must be uncountably infinite. (my) Solution: Let $m^*(E) &gt; 0$. Define the Rational Equivalence Relation on $E$ by $x \sim y$ if, any only if, $x - y \in \mathbb{Q}$. By way of contradiction, suppose that $c_E$ is countably infinite. Notice, one property of $c_E$ is the following: (i) For any $e \in E, \exists c \in c_E: e - c = q$, for $q \in \mathbb{Q}$. Therefore, by (i) if $c_E$ is countably infinite so is $E$. Since the Lebesgue Outer Measure of a countably infinite set is zero we obtain: $$m^*(E) = 0,$$ a contradiction. Hence, our assumption that $c_E$ is countably infinite is false. Therefore, $c_E$ must be uncountably infinite, as desired.
15214
I was comparing the sets $\mathbb{N}^{\mathbb{N}}$ and $\mathbb{R}$ for a fun practice because I didn't know at first that $\mathbb{N}^{\mathbb{N}}$ was uncountable. But how can I compare two uncountable sets and see which has the larger cardinality?
81480
Infinity, is clearly not . But there is some dissent on whether or not zero is finite. I have seen authors use "finite" to indicate the value of $0$ is excluded as well as infinity.  Is there any rule about this?
56817
I have alot of questions.   Do Infinite sets have the same cardinality when there is a bijection between them? Are $\mathbb{N}$ and $\mathbb{Z}$ infinite sets? I assume they are, but why? Why does there not exist a bijection between them? Why do $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ have the same cardinality? I assume there exists a bijection between them, but how can I find this function?