The argument to prove that there are different sizes of infinity is by saying .. no matter how many decimal numbers you write you can always come up with new one different from all others listed already.So, there is no one-one correspondence between natural numbers and decimal numbers. But, every time you come up with new one, you can add that new one to the list and correspond that to a natural number(which can go to infinity). So, again we have one-one correspondence and same cardinality and Hence same size of infinities. Please can someone help me what is wrong with my argument and what am I missing? It seems like the original argument is relying on the assumption that list of natural numbers end somewhere and we come up with a new decimal number to disprove one-one correspondence.
37259
I'm having trouble understanding Cantor's diagonal argument.  Specifically, I do not understand how it proves that something is "uncountable".  My understanding of the argument is that it takes the following form (modified slightly from the  article, assuming base 2, where the numbers must be from the set $ \lbrace 0,1 \rbrace $):  \begin{align} s_1 &amp;= (\mathbf{0},1,0,\dots)\\ s_2 &amp;= (1,\mathbf{1},0,\dots)\\ s_3 &amp;= (0,0,\mathbf{1},\dots)\\ \vdots &amp;= (s_n \text{ continues}) \end{align}  In this case, the diagonal number is the bold diagonal numbers $(0, 1, 1)$, which when "flipped" is $(1,0,0)$, neither of which is $s_1$, $s_2$, or $s_3$.  My question, or misunderstanding, is: When there exists the possibility that more $s_n$ exist, as is the case in the example above, how does this "prove" anything?  For example:  \begin{align} s_0 &amp;= (1,0,0,\mathbf{0},\dots)\ \ \textrm{ (...the wikipedia flipped diagonal)}\\ s_1 &amp;= (\mathbf{0},1,0,\dots)\\ s_2 &amp;= (1,\mathbf{1},0,\dots)\\ s_3 &amp;= (0,0,\mathbf{1},\dots)\\ s_4 &amp;= (0,1,1,\mathbf{1},\dots)\\ s_4 &amp;= (1,0,0,\mathbf{1},\dots)\ \ \textrm{ (...alternate, flipped } s_4\textrm{)}\\ s_5 &amp;= (1,0,0,0,\dots)\\ s_6 &amp;= (1,0,0,1,\dots)\\ \vdots &amp;= (s_n \text{ continues}) \end{align}  In other words, as long as there is a $\dots \text{ continues}$ at the end, the very next number could be the "impossible diagonal number", with the caveat that it's not strictly identical to the "impossible diagonal number" as the wikipedia article defines it:     For each $m$ and $n$ let $s_{n,m}$ be the $m^{th}$ element of the $n^{th}$ sequence on the list; so for each $n$,      $$s_n = (s_{n,1}, s_{n,2}, s_{n,3}, s_{n,4}, \dots).$$      ...snip...      Otherwise, it would be possible by the above process to construct a sequence $s_0$ which would both be in $T$ (because it is a sequence of 0s and 1s which is by the definition of $T$ in $T$) and at the same time not in $T$ (because we can deliberately construct it not to be in the list). $T$, containing all such sequences, must contain $s_0$, which is just such a sequence. But since $s_0$ does not appear anywhere on the list, $T$ cannot contain $s_0$.      Therefore $T$ cannot be placed in one-to-one correspondence with the natural numbers. In other words, it is uncountable.   I'm not sure this definition is correct, because if we assume that $m = (1, \dots)$, then this definition says that "$s_n$ is equal to itself"&mdadsh;there is no "diagonalization" in this particular description of the argument, nor does it incorporate the "flipping" part of the argument, never mind the fact that we have very clearly constructed just such an impossible $T$ list above.  An attempt to correct the "diagonalization" and "flipping" problem:  $$s_n = (\lnot s_{m,m}, \lnot s_{m,m}, \dots) \quad \text{where $m$ is the element index and} \quad\begin{equation}\lnot s_{m,m} = \begin{cases}0 &amp; \mathrm{if\ } s_{m,m} = 1\\1 &amp; \mathrm{if\ } s_{m,m} = 0\end{cases}\end{equation}$$  This definition doesn't quite work either, as we immediately run in to problems with just $s_1 = (0),$ which is impossible because by definition $s_1$ must be $ = (1)$ if $s_1 = (0)$, which would also be impossible because...   Or more generally, with the revised definition there is a contradiction whenever $n = m$, which would seem to invalidate the revised formulation of the argument / proof.  Nothing about this argument / proof makes any sense to me, nor why it only applies to real numbers and makes them "uncountable". As near as I can tell it would seem to apply equal well to natural numbers, which are "countable".  What am I missing?
20559
This question was inspired by the question on .  From the discussion in the comments there, it seems there does not exist a set of all sets of a given cardinality.  To me, it seems easy to see that this is true for any nonzero finite cardinality $n$. Given any set $x$, you can always make a set of size $n$ by adding $n-1$ other sets to $x$ to make a set of size $n$, which exists by repeated use of the pairing axiom.   But how would you do this for infinite cardinalities? For suppose $\kappa$ is some given infinite cardinality. To show that the set of all sets of cardinality $\kappa$ does not exist, it seems you would have to show that for any set $x$, there exists a set of that size with $x$ as an element, and then you could take the union of that set to find the set of all sets, and thus a contradiction. But it doesn't seem reasonable to simply say, for a given set of size $\kappa$ if $x$ is in the set, we have no problem. If not, just take an element out of the set and put $x$ in. Something about that seems like it would not be allowed.  So how would you do this for infinite cardinalities?
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?
68953
I am comfortable with the different sizes of infinities and Cantor's "diagonal argument" to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. So if we have a set $\Omega$ and $|\Omega| = \aleph_i$, then (assuming continuum hypothesis) the cardinality of $2^{\Omega}$ is $|2^{\Omega}| = \aleph_{i+1} &gt; \aleph_i$ and we have $\aleph_{i+1} = 2^{\aleph_i}$.  I am fine with these argument.  What I don't understand is why should there be a smallest $\infty$? Is there a proof (or) an axiom that there exists a smallest $\infty$ and that this is what we address as "countably infinite"? or to rephrase the question "why can't I find a set whose power set gives us $\mathbb{N}$"?  The reason why I am asking this question is in "some sense" $\aleph_i = \log_2(\aleph_{i+1})$. I do not completely understand why this process should stop when $\aleph_i = \aleph_0$.  (Though coming to think about it I can feel that if I take an infinite set with $\log_2 \aleph_0$ elements I can still put it in one-to-one correspondence with the Natural number set. So Is $\log_2 \aleph_0 = \aleph_0$ (or) am I just confused? If $n \rightarrow \infty$, then $2^n \rightarrow \infty$ faster while $\log (n) \rightarrow \infty$ slower and $\log (\log (n)) \rightarrow \infty$ even slower and $\log(\log(\log (n))) \rightarrow \infty$ even "more" slower and so on).  Is there a clean (and relatively elementary) way to explain this to me?  (I am totally fine if you direct me to some paper (or) webpage. I tried googling but could not find an answer to my question)
118333
I have a really hard time learning math when I can't find any justifications for the existence of infinity (in this case actual infinity).  Are there any justifications for the Axiom of Infinity?   Thank you very much.
68243
I was reading about countably infinite sets and the definition goes as, "A set is countably infinite if its elements can be put in one-to-one correspondence with the set of natural numbers"(Source: Google). Well yes, this make sense. As the set $\mathbb{N}$ is countably infinite and set which can it can create a bijection with, would end up having the same number of elements and thus they too would be countably infinite. But this would be true iff $\mathbb{N}$ is countably infinite. How would you prove that? Or is the idea of countably infinite base on some assumption that $\mathbb{N}$ is countably infinite?
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.
111403
I'm reading through How to Prove It by Velleman and I'm having trouble with this exercise in the section about Existence and Uniqueness proofs. Here is the exercise:     Suppose $A$ is a set and for every family of sets $\mathcal{F}$, if $\cup \mathcal{F}=A$ then $A \in \mathcal{F}$. Prove that $A$ has exactly one element.    He hints that for both the existence and uniqueness parts of the proof it would be a good idea to use contradiction. I've been playing around with this proof for a while but I can't seem to make any substantial progress.   I current idea is considering some cases  where for some family of sets $\mathcal{G}$, $A \in \mathcal{G}$ and $A \notin \mathcal{G}$. I thought if I could show that if $A= \varnothing$ lead to contradictions, I could at least say that there is something in $A$, and try to prove that it is unique from there. I haven't been able to make any progress with this though. Any help with this problem would be greatly appreciated!
48880
In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.  My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.  If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.
93690
Let the set S be infinite, and the set T countably infinite. S and T are both subsets of R. Show that S and S U T have the same cardinality.  I know we can discuss whether S is countable or uncountable, but is it true that, for example like this, countable set's cardinality basically does not count in the union of itself and an uncountable set?
67170
For example, can we say: $\infty=\lim\limits_{n\rightarrow\infty} n &lt; \aleph_0$?  These are two different types of structures. The limit being like the length, extension, or just generic magnitude and the other being cardinality of a set. Can we compare magnitude to cardinality?  Intuitively, we can reach $\aleph_0$ by counting the natural numbers on the number line and in the process will be approaching $\infty$. Which leads me to believe $\infty\leq\aleph_0$. But I can't see why it should be a strict inequality. I feel like they should be of equal magnitude.  I saw on a recent comment that $2^\infty=\infty$, but are those infinities really the same? It seems not to me. Of course we (usually) have that  $2^{\aleph_0}=\aleph_1$ where ${\aleph_0}$ and $\aleph_1$ are clearly two very distinct infinities, countable vs uncountable at least. Maybe one might argue that as far as the concept of magnitude is concerned, all infinities are "equal".
99057
The diagonal argument establishes that the continuum is greater than countable infinity. What is an example of the next infinity (or any greater infinity) and how can it be shown that there is no 1:1 correspondence with the continuum?
56061
I am reading George Gamow's book  and a certain assertion Gamow makes seems a little startling considering what I already know of the subject of infinite cardinality.     But the number of all geometrical points, though larger than the number of integer and fractional numbers, is not the largest one known to mathematicians. In fact it was found the variety of all possible curves, including those of the most unusual shapes, has a larger membership than the collection of all geometric points, and thus has to be described by the third number in the infinite sequence. [Gamow, 22]   He later does explicitly say the number of all possible curves is $\aleph_2$. But nowhere else can I find reference to this being true, nor does he provide any sort of reasoning to its validity.  My question is how can you prove the set of all possible curves is of cardinality $\aleph_2$ and not $\aleph_1$ or $\aleph_0$?
14267
Often, when I try to describe mathematics to the layman, I find myself struggling to convince them of the importance and consequence of "proof". I receive responses like: "surely if Collatz is true up to $20×2^{58}$, then it must always be true?"; and "the sequence of number of edges on a complete graph starts $0,1,3,6,10$, so the next term must be 15 etc."  Granted, this second statement is less logically unsound than the first since it's not difficult to see the reason why the sequence must continue as such; nevertheless, the statement was made on a premise that boils down to "interesting patterns must always continue".  I try to counter this logic by creating a ridiculous argument like "the numbers $1,2,3,4,5$ are less than $100$, so surely all numbers are", but this usually fails to be convincing.  So, are there any examples of non-trivial patterns that appear to be true for a large number of small cases, but then fail for some larger case? A good answer to this question should:   be one which could be explained to the layman without having to subject them to a 24 lecture course of background material, and have as a minimal counterexample a case which cannot (feasibly) be checked without the use of a computer.   I believe conditions 1. and 2. make my question specific enough to have in some sense a "right" (or at least a "not wrong") answer; but I'd be happy to clarify if this is not the case. I suppose I'm expecting an answer to come from number theory, but can see that areas like graph theory, combinatorics more generally and set theory could potentially offer suitable answers.
94508
Some very wise people here have just told me that  $\aleph_0 = \mathbb{N}$, i.e. that the cardinality of the set of natural numbers is just the set of natural numbers itself. Is this now the general consensus in mathematics, real analysis in particular? Or have I got completely the wrong end of the stick as usual?
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.
40663
I realize this is possibly a copy of another question (The Axiom of Choice and definability) but I would appreciate an explanation with less set theoretical explanations if that is at all possible.  I recently took the opportunity to look up the axiom of choice (AC). Wikipedia has both a formal and an informal definition.  Based on my shortcomings in set theory I have to rely on the informal version: “given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin”.  It seems that this can be used to define an endless series of decimals such as an arbitrary number x between 0 and 1, in term corresponding to an arbitrary positive real number through such a function as f(x)=1/x-1, i.e. it can be used to define any real number (assuming a real number is an infinite decimal series).  A beauty spot is the cases of 0.99999… and 1.00000… - discussed in a number of questions on the site. It points to several issues:  I argue, albeit in a roundabout way, that for a choice involving the AC to have any value then the number received through the choice must also allow for existing mathematical operations, i.e. 2*0.11111…=0.22222…  as discussed in another question. (“You're also assuming that you can multiply 0.9999... by 10 and get 9.9999... (or, rather, that arithmetic with infinite decimals works normally), which is not at all unreasonable to assume. – Isaac Jul 20 '10 at 20:59”) i)  0.99999…must be equal to 1.00000… for the same reason. ii) The fact that 0.99999…=1.00000…can challenge the one-to-one correlation between the real numbers, as we view as being without these doublets. However it can be disregarded as   I was assured in a recent question, in that removing a countable set such as 0,99999…, between the endless decimal series and 0.099999…and 0.0099999…  etc. from a uncountable set would not change the one-to-one correlation to numbers without this anomaly. (I was referred to i.a. the Cantor–Bernstein–Schroeder theorem).  Reasoning in this manner I perceive the AC to be identical of postulating - or at least allowing for the definition of – real numbers. My question is whether or not this is the case.  Edit much later: I should add that I primarily am looking at the problems of defing invividual real numbers, so called pointwise definition, rather than definition of the whole set of reals. I didn't realize at the time that these are two different issues.