This question exists, but both cases have a specific answer for the OP's situation. I do not know how to prove that $\mathbb{Q}$ is countable.  Questions I am referring to:  and
123292
I have this problem:     Prove that $\mathbb{|Q| = |Q\times Q|}$   I know that $\mathbb Q$ is countably infinite.  But then how can I prove that $\mathbb{|Q\times Q|}$ is countably infinite?  Thanks you!
25400
I need to find the cardinality of the set $S$ of all infinite subsets of $\mathbb{Q}$.   It's easy to prove $\operatorname{card} S=\mathfrak c$ if you first prove that the cardinality of the set of all finite subsets of $\mathbb{Q}$ is $\aleph_0$.   But is there some other proof for the statement without using the second one (about finite subsets)? Probably there is =)
107495
Question: Is $\mathbb{Z}= \{\dots, -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable?  My attemp so far: Let us create the following one-to-one correspondence between $\mathbb{Z}$ and $\mathbb{N}$. $$\begin{matrix}1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; \dots \\ \updownarrow &amp; \updownarrow &amp; \updownarrow &amp; \updownarrow &amp; \updownarrow &amp; \updownarrow &amp; \updownarrow &amp; \dots\\0 &amp; 1 &amp; -1 &amp; 2 &amp; -2 &amp; 3 &amp; -3 &amp; \dots\end{matrix}$$ In order for $\mathbb{Z}$ to be countable we must define a function $f:\mathbb{N} \to \mathbb{Z}$ so that $\mathbb{Z} \sim \mathbb{N}$. $$\displaystyle f(n) = \begin{cases} \frac{n}{2} &amp; n \text{ is even} \\ -\frac{n-1}{2} &amp; n\text{ is odd} \end{cases}$$ To show that $\mathbb{Z} \sim \mathbb{N}$ we require $f$ to be bijective. From the picture above, we can clearly see that $f$ is surjective since $\forall z \in \mathbb{Z}\  \exists n \in \mathbb{N}$ such that $f(n) = z$. Hence we must now show that $f$ is injective. We need to consider three cases:  $n_1, n_2$ are odd $n_1, n_2$ are even $n_1$ is odd and $n_2$ is even  Case 1: \begin{align}f(n_1) &amp;= f(n_2) \\ \implies -\frac{n_1 -1}{2} &amp;= -\frac{n_2 -1}{2} \\ \implies n_1 -1 &amp; = n_2 -1 \\ \implies n_1 &amp;= n_2\end{align} Case 2: \begin{align}f(n_1) &amp;= f(n_2) \\ \implies \frac{n_1}{2} &amp;= \frac{n_2}{2} \\ \implies n_1 &amp;= n_2\end{align} I am, however, experiencing some difficulty showing the injective property for the $3^{rd}$ case. Can anyone please give me some assistance with that specific case?
39733
Here is the proof I tried to weave while trying to prove this theorem:     Theorem. Every infinite subset of a countable set is countable.      Proof. Let $A$ be a countable set and $E\subset A$ be infinite. Then $A\thicksim\mathbb{N}$. This implies that there is a sequence $\left\{x_{n}\right\}_{n\in\mathbb{N}}$ where $x_{n}\in A$. Construct a sequence $\left\{n_{k}\right\}_{k\in\mathbb{N}}$ where $x_{n_{k}}\in A$, $n_{1}$ is the smallest positive integer such that $x_{n_{1}}\in A$, and $n_{k+1}&gt;n_{k}$. Then      $$ E=\bigcup_{k=1}^{\infty}x_{n_{k}}, $$      and $E$ is countable, because $E\thicksim\mathbb{N}$. $\blacksquare$   Is it convincing?
34293
Let ${{E_n}}_{n\in \mathbb{N}}$ be a sequence such that every $E_n$ is countable.  Let $g_n : \mathbb{N} \to E_n$ be a bijection for every $n\in \mathbb{N}$.  Let $\alpha (n,k) = g_n(k)$  Let $A$ be the union of $E_n$'s.  Then $\alpha : \mathbb{N} × \mathbb{N} \to A$ is a surjective function.  Since $\mathbb{N} \times \mathbb{N}$ is equipotent with $\mathbb{N}$, there exists a surjective function $f: \mathbb{N}\to A$.  Let $[n]$={$m\in \mathbb{N}$|$f(m)=f(n)$} for every $n\in \mathbb{N}$.  Since $f$ is surjective, for every $n\in \mathbb{N}$, $[n]\ne \emptyset$.  Since $[n] \subset \mathbb{N}$, $[n]$ is well-ordered.  Let $l_n$ designate the least element of $[n]$.  Let $B=\{l_n \in \mathbb{N} | n\in \mathbb{N}\}$  Then $f_{[B]}$ : $B\to A$ is a bijection.  Since $B\subset \mathbb{N}$, $B$ is at most countable. Since $A$ is infinite, $B$ is countable, hence $A$ is countable.  I don't know where i used AC in my argument. Help
102239
Proof: Since $\mathbb{Q}$ is a field, then $\mathbb{Q}$ is a domain.  (Theorem: if $R$ is a domain, then $R[x]$ is a field.)  By the theorem, $\mathbb{Q}[x]$ is a field.  So, letting $x = \sqrt{2}$, we get $\mathbb{Q}[\sqrt{2}]$ is a field. QED.  I am wondering if this is an acceptable proof? Also, I am wondering if it can be proven using facts of irreducibility? Isn't this what Galois Theory is about? I am curious, thanks.
64074
I have an intuition problem regarding a certain claim.  I've learned that since $\mathbb{Q}$ is measurable than  $$\lambda(\mathbb{Q})= \inf\left\{\sum_{n \ge 1} \lambda([a_n,b_n)) : \mathbb{Q} \subset \bigcup_{n \ge 1} [a_n,b_n)\right\}$$  This is because Lebesgue measure is the Caratheodory extension over the semiring whose elements are $[a,b)$.  But it seems so false, since as we know $\lambda(\mathbb{Q}) = 0$, But I can't even imagine a countable family of sets such that $\mathbb{Q} \subset \bigcup_{n \ge 1} [a_n,b_n)$ and  $\sum_{n \ge 1} \lambda([a_n,b_n)) &lt; \infty$.  How can the infimum of the above set be $0$?
24061
It's true that a set with a linear order where every initial segment is finite is necessarily countable? I don't think so but I can't find a counterexample (or make a proof)
8795
${ \mathbb{N} }^{ \left\{ 0,1 \right\}  }$ and ${ \left\{ 0,1 \right\}  }^{ \mathbb{N} }$ to be more specific, and is there a countable subset in each one of them? How do I find them?
122676
Hi everyone I'd like to know if the following reasoning is correct, any suggestion would be great. Thanks.  Proposition: Let $Y$ be a set and let $f: \mathbb{N}\rightarrow Y$ be a function. Then $f[\mathbb{N}]$ is at most countable.   Proof: If $Y$ is finite the result follows, this is because$f[\mathbb{N}]\subset Y$ and any subset of a finite set  is finite and has at most the size of the set in which is contained.   We may assume  that the set $Y$ is infinite. We set $A:= \{\,n\in\mathbb{N}:f(i)\not=f(n) \,\,\text{ for  any }i&lt; n\, \}$. And we define the function $g:A \rightarrow f[\mathbb{N}]$ as the restriction of $f$ in $A$. We claim that the function $g$ is a bijective map. From the definition of $A$ we already know that the map is $1:1$. We will show that also is onto.   Let $y\in f[\mathbb{N}]$. Suppose for the sake of contradiction that there is no $n\in A$ such that $g(n)=y$. Since $y$ lies in the image of $f$, then there is some $j\in \mathbb{N}$ for which $y=f(j)$. Then either $f(j)\not= f(i)$ for any $i&lt;j$ or there exists some $i&lt;j$ such that $f(j)= f(i)$. For the former, $j$ lies in $A$ (by its definition). For the latter, the set $\{\, n\in \mathbb{N}: f(j)=f(n)\, \text{and }\,n\not=j \}$ is non empty, and hence has a minimum element. Let $m$ be its minimum element. Then $f(m)\not=f(n)$ for any $n&lt;m$ and thus $\,m\in A$ but $g(m)=f(m)= f(j)=y$. Thus any case leads to a contradiction. The result follows by reductio ad absurdum. Hence $f$ is surjective and injective, i.e., a bijective map.   Since there is a bijection between $A$ and the images of the natural numbers under $f$, both have the same cardinality. Also we already know that $A\subset \mathbb{N}$ and any set of the natural numbers is denumerable, thus $f[\mathbb{N}]$ is countable. $\Box$
120355
Given $(X, \mathcal{T})$ a topological space. Let $\mathcal{S}$ be a subbasis on $(X, \mathcal{T})$     Claim: If $\mathcal{S}$ is countable, then $\mathcal{T}$ has a   countable basis $\mathcal{B}$   I am not sure how to go about approaching this quetion but here's my attempt:  I want to show that there exists a surjection $g$ from $\mathcal{S}$ to $\mathcal{B}$, and there is an injection $f$ from $\mathcal{B}$ and $\mathcal{S}$ thus $|\mathcal{S}| = \aleph_0 = |\mathcal{B}|$  Define $g$ as  $$g(S_1, S_2, \ldots, S_n) = S_1 \cap S_2 \cap \ldots \cap S_n = B$$  where $S_1, \ldots, S_n \in \mathcal{S}$, and $B \in \mathcal{B}$  But how does the countability of $\mathcal{S}$ come in? I'm really lost    Per Henno's suggestion re-attempt:   Let $\mathcal{S}$ be a countable subbase of $(X, \mathcal{T})$. Then $\mathcal{S}$ can be listed as $\{S_1, S_2, \ldots \}, S_i \in S, i    \in \mathbb{N}$   By definition, each basis element is the finite intersection of subbasic elements written as $\bigcap\limits_{i \in F_n} S_i$, where $F_n$ is a finite set in $\mathbb{N}$.   Since there exists countably many finite sets in $\mathbb{N}$, we can list all the finite sets as $\{F_1, F_2, \ldots\}$   Then correspondingly we can list all the basis elements as:$\{\bigcap\limits_{i \in F_1} S_i, \bigcap\limits_{i \in F_2} S_i,    \ldots\}$ which is a countable set.    Hence $\mathcal{B}$ is countable.
33430
Is the set of partial order relations over $ \mathbb{N}$ countable? I think it's uncountable but don't know how to prove this. I would be very helpful if someone could also give some kind of a strategy for proving uncountability, in particular how to find injective or surjective functions that help proving this.
79918
How to prove that the set of integer coefficient polynomials is countable?
26129
Can someone point me to a proof that the set of irrational numbers is uncountable? I know how to show that the set $\mathbb{Q}$ of rational numbers is countable, but how would you show that the irrationals are uncountable?
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!
86430
Problem: Consider the subfield $$E = \mathbb{Q} \big(\left\{\sqrt[n]{2} \mid n \in \mathbb{N} \setminus \left\{0\right\} \right\} \big)$$ of $\mathbb{R}$. Prove that $[E: \mathbb{Q}]$ is not finite.  Attempt: I proved that $E$ is algebraic over $\mathbb{Q}$. Because let $u \in E$. Then there is a $n \in \mathbb{N} \setminus \left\{0\right\}$ such that $u = \sqrt[n]{2}$. Then $f(x) = x^n - 2 \in \mathbb{Q}[x]$ is the minimal polynomial of $u$ over $\mathbb{Q}$ such that $f(u) = 0$. Hence $E$ is algebraic over $\mathbb{Q}$.  I now want to prove the degree of extension is not finite. I assume it is finite. Suppose then $[E: \mathbb{Q}] = k \in \mathbb{N}$. I don't know how to derive a contradiction from this.   I know that if $u$ is algebraic over $\mathbb{Q}$ and $f$ is the minimal polynomial of $u$ over $\mathbb{Q}$, then $[\mathbb{Q}(u) : \mathbb{Q}] = \deg(f)$.   Help/suggestions are appreciated.
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!