Suppose $X \subseteq \mathbb{R}$ is well-ordered by $&lt;$, the normal ordering on $\mathbb{R}$. Is it then countable? If so, how to prove this. I've tried to set up a bijection as follows:  $$ \phi : \mathbb{N} \to X : n \mapsto \ &lt;\textrm{-least element of } X \backslash \phi(\mathbb{N} \upharpoonright n) $$ I.e, $0$ maps to the least element of $X$, 1 maps to the least element of $X \backslash \{x_1\}$, $2$ maps to the least element of $X \backslash \{x_1,x_2\}$ etc. This is injective by construction, but I'm not sure if it is surjective.
28071
I know that the usual ordering of $\mathbb R$ is not a well-ordering but is there an uncountable $S\subset \mathbb R$ such that S is well-ordered by $&lt;_\mathbb R$?   Intuitively I'd say there is no such set but intuitively I'd also say there is no well-ordered uncountable set at all, which is obviously wrong. I still struggle to grasp the idea of an uncountable, well-ordered set.
17193
I have few questions to the proof of this claim that is illustrated in a textbook.  $Seq (\mathbb{N})$ of all finite sequences of elements of $\mathbb{N}$ is countable.   Proof: Since $Seq(\mathbb{N}) = \bigcup^{\infty} _{n=0} \mathbb{N}^n,$ it suffices to produce a sequence $\left \langle {a_n | n \in \mathbb{N}}\right \rangle $ of enumerations of $\mathbb{N}^n,$ i.e. for each $n \in \mathbb{N}, a_n =\left \langle {a_n(k)| k \in \mathbb{N}}\right \rangle $ is an infinite sequence, and $\mathbb{N}^n = \{a_n(k) | k \in \mathbb{N}\}$   Let $g$ be a bijection from $\mathbb{N}$ to $\mathbb{N} \times \mathbb{N}.$ Define $a_1(i) = \left \langle {i}\right \rangle, \forall i \in \mathbb{N}; a_{n+1}(i) = \left \langle {b_0,...,b_{n-1},i_2}\right \rangle, $ where $g(i) = (i_1,i_2)$ and $\left \langle {b_0,...,b_{n-1}}\right \rangle = a_n(i_1).$ Hence $a_n$ is onto $\mathbb{N}^n.$  My questions: This means $a_2(i) = \left \langle {i_1, i_2}\right \rangle,$ where $g(i) =(i_1,i_2).$ Then $a_3(i) = \left \langle {i_1,i_2,i_2}\right \rangle $ $,a_4(i) =\left \langle {i_1,i_2,i_2,i_2}\right \rangle $ and $a_n(i) =\left \langle {i_1,i_2,...,i_2}\right \rangle$ etc? If so, given $f = \left \langle {f(0),...,f(n-1)}\right \rangle  \in \mathbb{N}^n,$ I don't understand how could $f $ be expressed as $a_n(i),$ for some $i \in \mathbb{N}?$  Appreciate any clear instruction. Thank you.
84381
I need to prove that for every countable ordinal $\alpha$, $X_{\alpha} = \alpha\times[0,1)$ is order isomorphic to $[0,1)$, where the order on $X_{\alpha}$ is the lexicographical order. I wanted to go by induction on the countable ordinals. I was able to manually construct a function $f:X_{\omega}\to[0,1)$ that is an order isomorphism, so the base case I have.  So, suppose by induction that for some countable ordinal $\alpha$, for all $\beta &lt; \alpha$, $X_{\alpha}\cong [0,1)$. I need to show that $X_{\alpha+1}\cong[0,1)$. So my attempt was to use the fact that $X_{\alpha + 1} = \left(\alpha\cup\{\alpha\}\right)\times[0,1)$ and to use the induction hypothesis to get an order isomorphism $f'$ between $\alpha\times[0,1)$ and $[0,1)$, and to use the trivial isomorphism $f''$ between $\{\alpha\}\times[0,1)$ and $[0,1)$, and then take the union of these functions $f = f'\cup f''$. But then a problem arises when trying to compare $f(\alpha,r)$ and $f(\gamma,q)$ where $\gamma &lt; \alpha$, since nothing promises me that $f'(\gamma,q) &lt; f''(\alpha,r)$.  I assume after I figure out for successor ordinal, the generalization to a limit ordinal will not be difficult?
58164
I'm trying to find a surjective function $f:\mathbb{N}\to \mathbb{Q}$;  I know that at least one such function must exist since $\mathbb{Q}$ is countable, but I haven't been able to find one.  Can someone show me one such function?  Best regards,  lorenzo
23139
Let $X= \{ A \subset \mathbb{N} : \mathbb{N} \backslash A \text{ is finite}\}$. What is the cardinality of $X$? Prove it.  For me the cardinality should be the same as the natural numbers. I am trying to show a way of ordering it, the first A is one with the smallest numbers and so on.
25440
Prove that there exist uncountable family of subsets of $\mathbb{N}$ which is linearly (totally) ordered by realtion of inclusion.  I do not know how to prove it. Actually I cannot concieve that such family of set can be uncountable. I would be thankful for help
90635
Given a well-orderable infinite set $A$, can we always say that the set $$\left\{R\subset A\times A:\langle A,R\rangle\, \text{is a well-ordering}\right\}$$ has cardinality $2^{|A|}$? How much Choice is required for the proof of this? I believe that where $A$ is countably infinite, we can proceed without any use of Choice. Is that correct?
18368
Is the finite Cartesian Product of Countable sets countable?  If possible, could you give a bijection that would work for any example?  Any help would be appreciated.
92813
Here I offer a "proof" of why the power set of the natural numbers is countable by creating a supposed bijection. I know that my proof is wrong, but where? If anyone could point it out, that'd be awesome.  Consider the power set of the natural numbers. We can form a bijection $f:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ as follows.  For any $f(x)$ convert $x$ to its binary representation, which is a string of $0$s and $1$s. If the $i$-th digit is $1$, then include $i$ in the output set $S=f(x)$. Otherwise do not include $i$. Note that $i$ is $0$-indexed and starts from the right-most digit.  So in this case $f(5)=\{1,3\}$. Supposedly we can construct any set in $\mathcal{P}(\mathbb{N})$ with an appropriate choice of $x$.  Where does this proof blow up?
20551
How do I show that every partial order can be extended to a linear ordering?      I think that I manage to prove that claim for finite set, how can I prove it for infinite set?  Thank you.
43466
Yesterday, Asaf Karagila's  sparked an extensive discussion on ways of proving that all countable ordinals are embeddable in $\Bbb Q$, and whether particular solutions to this use the Axiom of Choice.  Since the arguments used to prove this can be shady on their use of Choice when formulated tersely, fully fleshed out answers are appreciated.  To be concrete, this question asks for proofs of the following fact:     All countable ordinals $\alpha &lt; \omega_1$ are order-embeddable in the rationals $\Bbb Q$.   Especially answers avoiding the Axiom of Choice are appreciated.    Of relevance and related interest is  (but it's not a duplicate, since that question asks for explicit embeddings).
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?
15398
Find the cardinality of the set of all finite subsets of $\mathbb{R}$.    I have proved that the set of all finite subsets of $\mathbb{N}$ is countable . But I cannot find the cardinality of the set in case of $\mathbb{R}$ .  My Attempt:   First I have considered the set $$A_k=\{\{a_1, a_2, ..., a_k\}| a_i \in \mathbb{R}  \ and\ a_1&lt;...&lt;a_k  \}$$  Then $S=$ The set of all finite subsets of $\mathbb{R}=\bigcup_{n=1}^{\infty}A_{n}$, and now in the case of $\mathbb{N}$, I could show that this $A_k$ is countable and consequently the set of all finite subset of $\mathbb{N}$ is countable.  But in this case I cannot say anything like this...In this case the set will be of the cardinality as that of $\mathbb{R}$ (I think). But cannot prove it.  I appreciate your help.  Thank you.
79181
I would like to find a way to construct uncountably many non-isomorphic linear (total) orderings of natural numbers (as stated in the title).  I've already constructed two non-isomorphic total orderings. They are $$ 1 &lt; 2 &lt; 3 &lt;\ldots\\ 1 &gt; 2 &gt; 3 &gt;\ldots $$ where "$&lt;$" and "$&gt;$" are  strict total ordering relations.  Thanks in advance for your help.
42314
I am trying to prove that, given a collection $\{S_i:i \in \mathbb{N}\}$ of infinite sets which all have the same cardinality, that $|S_1 \cup S_2 \cup \cdots|=|S_1|$. WLOG, I'm going to assume the $S_i$ are disjoint.  My thought was to let each $f_i:S_1 \to S_i$ be a bijection and to define $g: S_1 \times \mathbb{N} \to S_1 \cup S_2 \cup \cdots$ by $g(x,n)=f_n(x)$. I see that $g$ is a bijection.   So, the problem is reduced to "merely" proving that $|S_1 \times \mathbb{N}|=|S_1|$. I say "merely" with tongue in cheek because it is by no means obvious to me how to do it.  If $S_1$ is countable, I know how to proceed by the standard diagonal argument used to show $\mathbb{Q}$ is countable. But if $S_1$ is uncountable, I don't know what to do, even though it seems intuitive to me that crossing $S_1$ with $\mathbb{N}$ won't make the set "bigger" since it doesn't make it bigger in the countable case.
27362
I don't even know where to begin on this one.  Let $A$ be a countable set. In other words, $|A| = |\mathbb{N}|$. I'm trying to prove that there doesn't exist an $x$ such that $\mathcal{P}x = A$.   Maybe a proof by contradiction? Suppose there was a set $x$ whose power set was countable ...
4353
Definition of "at most countable" used: A set $A$ is at most countable iff it's finite or there exists a bijection $f:\mathbb{N} \rightarrow A$.  Problem: I want to prove that if there exists a surjective function from the set of natural numbers to a set $A$, then there exists a bijective function $f:\mathbb{N}\rightarrow A$, with the condition that $A$ is infinite (Because if it´s finite, one condition is met and the problem is over).  My approach for these kind of problems used to be creating a function that just maps from the first set to the second, making permutations as necessary. But infinity is confusing me. So this is my approach so far:  Index each set with different index numbers, both natural numbers. $x$ for naturals, and $y$ for elements in $A$. So we would get $f(x_n)=y_i$, $f(x_{x+1})=y_{i+1}$ and so on. Then create another function:  $g(x_n) = \left\{    \begin{array}{l l}     f(x_n) &amp; \quad \text{if $\forall a&lt;n, f(x_a)\neq y_i$}\\     h(x_n) &amp; \quad \text{if $\exists a&lt;n/f(x_a)=y_i$}   \end{array} \right.$  The problem we're trying to avoid here is having two elements in $\mathbb{N}$ so that $f$ maps them to the same $y$. Here, the so called "$h$" function: what should it do? Or is there another approach I should be using instead? (Like, Axiom of Choice and its equivalents).