First, I should preface this by saying that I am not incredibly familiar with the mathematics at play here; I am simply trying to obtain a conceptual understanding of the answer, since my current conceptual understanding would entail that real numbers are countable. As such I will likely not be using the proper mathematical language in all cases; please bear with me.  From the Wikipedia article 'Countable set':     Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a natural number.   The issue here is that I think one can assign a unique natural number to every real number in a manner such that you could map the real and natural numbers bidirectionally and uniquely.  I would do so with the idea that you can represent every real number with a decimal base and a decimal exponent (base * 10^exponent). The base would be the set of all integers without leading zeros; that is, where the digit at the 1's place is not 0. The exponent would be the set of all integers, excluding 0. These are both subsets of the set of integers, which is countable, and I am given to understand that a subset of a countable set is countable. Thus, for every possible base and exponent, you could assign a unique natural number.  I am also given to understand that you can assign a unique natural number to every ordered pair of two natural numbers; so, one should be able to assign a unique natural number to every pair of base and exponent (which can both be assigned unique natural numbers).  That would leave every real number (excluding 0) tied uniquely to a natural number. You could then form a set of all real numbers by 'appending' 0, and increment all the other natural number bindings by 1. At this point, you would have uniquely assigned a natural number to every real number, making the set of real numbers countable.  So... what's wrong here?
38749
I was just thinking about this recently, and I thought of a possible bijection between the natural numbers and the real numbers.  First, take the numbers between zero and one, exclusive.  The following sequence of real numbers is suggested so that we have bijection.    0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.02, ... , 0.09, 0.10, 0.11, ... , 0.99, 0.001, 0.002, ... , 0.999, 0.0001, etc.  Obviously, this includes repeats, but this set is countable.  Therefore, the set of all numbers between zero and one is a subset of the above countable set, and is thus countable.  Then we simply extend this to all real numbers and all the whole numbers themselves, and since the real numbers, as demonstrated above, between any two whole numbers is countable, the real numbers are the union of countably many countable sets, and thus the real numbers are countable.    Please help me with this.  I understand the diagonalization argument by Cantor, but I am curious specifically about this proof which I thought of and its strengths and flaws.  Thanks.
57240
I am confused as to what numbers are. Numbers are defined to be what they are, so numbers aren't real? But numbers are found in nature, right? So if we invented them, how can they be found in nature? How can everything be based on something that is not real. Sorry if what I am saying don't make sense, it hard to put it into words. I feel like I've been known numbers all my life yet I don't know what they are. Also why don't complex numbers have an order? Real numbers are an invention just as complex numbers are, so how are imaginary numbers any more imaginary than real numbers? I mean an order was given to the real numbers, so why can't complex numbers be given a definite order?  Thanks
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.
40936
This question is essentially a paraphrase of a  (deleted) question, which talks about a comment by Asaf Karagila about the &quot;elements of $\pi$&quot;.  I'm aware of how natural numbers can be , so for example $3$ may be viewed as the set $\{\:\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\:\}$, so has elements $\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}$. This seems pretty concrete and natural. I can see that we can adapt this to deal with the integers, by for example adding in a second empty set as a &quot;marker&quot; element (so $-3$ corresponds to $\{\:\emptyset, \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\:\}$). I can also see that we can adapt this &quot;marker&quot; idea to deal with the rational numbers (which are pairs of integers, and we &quot;mark&quot; the top one and the bottom one in a certain way). However, I am already getting nervous here as this seems much more synthetic than how we viewed the natural numbers. Anyway. It not clear to me how a number like $\pi$ or $e$ can have elements. One way might be to view these numbers as limits of sequences, and so as lists of rational numbers. However, this seems suspicious as these numbers are limits of multiples sequences, so this does not give me a canonical set which represents these numbers, but instead a family of sets. Is this OK, or is my reasoning broken? So what I want to ask is:  What are the elements of $e$?  Or, more subtly, does this question make sense, or should we remove the word &quot;the&quot; from it?
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".
10637
A well-known mathematical fact is that the rational numbers are countable, i.e. there is a bijective function  $$f:\mathbb{N}\rightarrow \mathbb{Q}$$  I am interesting in making a list of all explicit such bijections since each one that I know have a different philosophy behind it.   This is one of the more counterintuitive facts about infinite, at least when one enters inside set theory. When I explain this in the first time to anyone, he/she is surprised. Thus I think  it will be useful for showing the fact in a more clear manner or as possible exercises to show alternatives ways with respect to the standard one.
53718
There are two questions:        Image of a countable set of real numbers under any continuous function is countable?      My claim is yes. Let $X$ is countable $\implies X=\{x_1,x_2,\ldots,\}$. Now $f(X)=\{f(x_1),f(x_2),\ldots,\}$ which can be atmost countable. Now my question is "What is the role of continuity here?"        Image of a uncountable set of real numbers under any non-constant continuous function is uncountable?      I feel this is true. But unable to proceed. Please provide me a hint.
85715
How can I rigorously prove that a finite set is countable?   A set is countable if there exists a bijective mapping from this set to that of natural numbers.   Please anyone help me to prove it. Thanks in advance.
50394
Denote by $\mathbb{N}$ the set of natural numbers and by $2^{\mathbb N}$ the set of all subsets of $\mathbb N$. Let $E$ be some subset of $2^{\mathbb N}$ such that for  every pair of elements in $E$, one is a subset of the other. Clearly, $E$ could be countable by considering $E=\big\{\{1,\cdots, n\}, n\in\mathbb N\big\}$. My question is the following: could we find an example that $E$ is uncountable? Many thanks for the answer!
111940
Does every number not ending with zero have a multiple without zero digits at all?   We consider numbers in their usual base 10 representation. we don't consider numbers ending with $0$, because all multiples of such numbers end with $0$.   It can be proven that all powers of $2$ have such a multiple: Indeed, for every number of the form $2^n$, we can find a multiple $l$ of it whose last $n$ digits are nonzero (This can be done by repeatedly multiplying a number by $10^k+1$, as explained ), and then forget all other digits; these last $n$ digits constitute a number that is still divisible by $2^n$, since it is obtained from $l$ by subtracting a multiple of $10^n$ which is in particular a multiple of $2^n$.  The same argument shows that every power of $5$ has a multiple without zeros, but this does not seem to generalize to other numbers.  My intuition is actually that the claim is not true, since the density of numbers without any zero digits approaches $0$ for big numbers. This is because the probability of a random number with at most $n$ digits to contain only nonzero digits is $(\frac{9}{10})^n$. Thus big numbers "nearly always" contain a zero. This hints on the existence of a counterexample, but does not prove its existence.
100534
For example say, $n = 2$. So our set is $\{1, 2, 3, 4\}$ in base $10$ and  $\{1, 10, 11, 100\}$ in base $2$. So Output $1$, because only one number i.e. $3$ is there such that it has $``11"$ in it.  For $n = 3$, we get $\{3, 6, 7\}$ as having $``11"$, so output $3$.
32976
The set of all strictly increasing sequences  ($a_n$) of natural numbers has cardinality $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$ or $\mathcal{P}( \mathcal{P}(\mathbb{N}))$?  I answered $\mathcal{P}(\mathcal{P}(\mathbb{N}))$ because as the set can be described by $X=\{\{\ldots, a_n, \ldots \},\{\ldots,b_n,\ldots\}, \ldots\}$ as it is not known if there are any limited sequences (so, assuming all have infinite elements), the cardinality of $X$ could not be the first option $\mathbb{N}$ because considering any function $\phi : \mathbb{N} \rightarrow X$ there would always be elements not listed from $X$. So I thought it would possible to say that $|X|\ge | \mathcal{P}(\mathbb{N})|$ and thinking that trying to build any bijection $\varphi: \mathcal{P}(\mathbb{N}) \rightarrow X$ would also not be possible as there would be elements from $X$ not listed too. So than I got $|X| = |\mathcal{P}( \mathcal{P}(\mathbb{N}))|$, but I would like to know if I answered correct and, if not, why?
94997
Suppose we want to define a first-order language to do set theory (so we can formalize mathematics). One such construction can be found . What makes me uneasy about this definition is that words such as "set", "countable", "function", and "number" are used in somewhat non-trivial manners. For instance, behind the word "countable" rests an immense amount of mathematical knowledge: one needs the notion of a bijection, which requires functions and sets. One also needs the set of natural numbers (or something with equal cardinality), in order to say that countable sets have a bijection with the set of natural numbers.  Also, in set theory one uses the relation of belonging "$\in$". But relation seems to require the notion an ordered pair, which requires sets, whose properties are described using belonging...  I found the following in Kevin Klement's,  (pages 2-3).  "You have to use logic to study logic. There’s no getting away from it. However, I’m not going to bother stating all the logical rules that are valid in the metalanguage, since I’d need to do that in the metametalanguage, and that would just get me started on an infinite regress. The rule of thumb is: if it’s OK in the object language, it’s OK in the metalanguage too."  So it seems that, if one proves a fact about the object language, then one can also use it in the metalanguage. In the case of set theory, one may not start out knowing what sets really are, but after one proves some fact about them (e.g., that there are uncountable sets) then one implicitly "adds" this fact also to the metalanguage.  This seems like cheating: one is using the object language to conduct proofs regarding the metalanguage, when it should strictly be the other way round.  To give an example of avoiding circularity, consider the definition of the integers. We can define a binary relation $R\subseteq(\mathbf{N}\times\mathbf{N})\times(\mathbf{N}\times\mathbf{N})$, where for any $a,b,c,d\in\mathbf{N}$, $((a,b),(c,d))\in R$ iff $a+d=b+c$, and then defining $\mathbf{Z}:= \{[(a,b)]:a,b\in\mathbf{N}\}$, where $[a,b]=\{x\in \mathbf{N}\times\mathbf{N}: xR(a,b)\}$, as in  question or  on Wikipedia. In this definition if set theory and natural numbers are assumed, then there is no circularity because one did not depend on the notion of "subtraction" in defining the integers.  So my question is:     Question Is the definition of first-order logic circular?   If not, please explain why.   If the definitions are circular, is there an alternative definition which avoids the circularity?   Some thoughts:   Perhaps there is the distinction between what sets are (anything that obeys the axioms) and how sets are expressed (using a formal language). In other words, the notion of a set may not be circular, but to talk of sets using a formal language requires the notion of a set in a metalanguage. In foundational mathematics there also seems to be the idea of first defining something, and then coming back with better machinery to analyse that thing. For instance, one can define the natural numbers using the Peano axioms, then later come back to say that all structures satisfying the axioms are isomorphic. (I don't know any algebra, but that seems right.) Maybe sets, functions, etc., are too basic? Is it possible to avoid these terms when defining a formal language?
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.
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.
102083
I'm well aware of the standard proof based on cardinality arithmetic to show that these two sets have the same cardinality and the question of defining a bijection between the two sets came up. I worked on it a little while and was wondering if there were any gaps, or a simpler method of coming up with such a bijection.   The main idea I had was to take a family of sequences indexed by the real numbers. So that each one of these sequences corresponds to a unique real number. Then I can map each one of these sequences to another number, by applying the binary function from $\mathbb R$ to $\{0,1\}$ and mapping the infinite binary sequence to a real number, use one of the standard bijections.  First let $E$ be a family of sequences indexed by the real numbers. Such that $E_{xi}\neq E_{yj}$ for all $x,y \in \mathbb R$ and $i,j \in \mathbb N$ also with the property that  $\mathbb R= \bigcup_{x \in \mathbb R, i \in \mathbb N} E_{xi}$.   What sort of theorems would I need to prove such a family existed, is it enough to note that the reals can be represented as a uncountable union of countably infinite sets?  Also let $P: 2^{\mathbb N} \rightarrow \mathbb R$ be you favorite bijection.  Now consider an element of $2^{\mathbb R}$ as a function $f: \mathbb R \rightarrow \{0,1\}$ and $g \in \mathbb{ R^R}$ in a similar manner. Then our bijection between the two sets will be the function $\Phi$ which maps $f$ to a function $g$, such that $g(x)=P(F(E_x))$ where $F$ applies $f$ to each element of the sequence $E_x$.   I'm fairly sure this is an onto and one-to-one function. The one-to-one property should follow because the sequences are disjoint, cover $\mathbb R$ and $P$ is a bijection. The onto argument is a little hazier, but it should be possible to recreate the function $f$, by first inverting each element with $P$ and then defining $f$ based on these sequences.
101156
I am asked to prove the following question:  For each finite set of real numbers, $F$, define $\sum F$ to be the sum of all the numbers in $F$.  For each set $P$ of positive real numbers, define $\sum P=\sup\{\sum F: F\text{ is a finite subset of } P\}$.  Suppose $P$ is a set of positive real numbers such that $\sum P &lt; \infty$. Prove that $P$ is a countable set.  My attempt (just a sketch proof):  Suppose $P$ is uncountable, $\exists \epsilon_1 &gt; 0$, s.t. $$ P_1 = [\inf P + \epsilon_1, \sup P]\cap P $$ is uncountable. Pick $a_1 \in [\inf P, \inf P + \epsilon_1] \cap P \in P$, such a $P$ must exists due to greatest lower bound property.  Now $P_1$ is uncountable, $\exists \epsilon_2 &gt; 0$, s.t. $$ P_2 = [\inf P_1 + \epsilon_2, \sup P_1]\cap P_1  $$  is uncountable. Pick $a_2 \in [\inf P_1, \inf P_1 + \epsilon_2]\cap P_1 \in P$. Carry on this process (this should be formalized using induction), we can find  $$ a_1 \leq a_2 \leq a_3 \leq ... $$ with $a_n &gt; 0$ and $a_n \in P$ for all $n$.  Now $\sup\{\sum F_n: F_n = \{a_1,...,a_n\}, n \in \mathbb{N}^+\} = \lim_{n \to \infty}\sum_{i = 1}^n a_i &gt; \lim_{n \to \infty}na_1 = \infty$. This means that $\sum P = \infty$ since $\{\sum F_n: F_n = \{a_1,...,a_n\}, n \in \mathbb{N}^+\} \subset \{\sum F: F\text{ is a finite subset of } P\}$.  I think my proof is a bit clumsy but is it correct?