I have to show that  $$ \bigcup_{n=1}^{\infty}A_{n} := (a: \exists n \in \mathbb{N}: a \in A_{n}) $$  EDIT: So beneath this edit were just my thoughts. Above is the task. Is there any elementary way to prove that this Union of countable sets is countable? (besides counting like $\mathbb Q$)  As far as I understand countability, I have to show that the union is a bijection to $\mathbb{N}$.  $$ f: \bigcup_{n=1}^{\infty}A_{n} \to \mathbb{N} $$  Well, surjection is given by definition above, isn't it?  Now I only have to show injection. So if $f(a)=f(b)$ then $a=b$. How do I show that for the union?
123822
How do you prove that any collection of sets $\{X_n : n \in \mathbb{N}\}$ such that for every $n \in \mathbb{N}$ the set $X_n$ is equinumerous to the set of natural numbers, then the union of all these sets, $\bigcup_{i\in \mathbb{N}}$ $X_i$ is also equinumerous to the set of natural numbers? (By equinumerous I mean there exists a one-to-one and onto function $f:X_n \to \mathbb{N}$.)  Is this statement false as it stands?
23628
Prove that $\mathbb{N}^k$ is countable for every $k \in \mathbb{N}$.  I am told that we can go about this inductively.   Let $P(n)$ be the statement: “$\mathbb{N}^n$ is countable” $\forall n \in \mathbb{N}$.  Base Case: $\mathbb{N}^1 = \mathbb{N}$ is countable by definition, so $\checkmark$  Inductive Step: $\mathbb{N}^{k+1}$ $“=”$ $\mathbb{N}^k \times \mathbb{N}$  We know that $(A,B)$ countable $\implies$ $A \times B$ is countable. I am stuck on the part where I have to prove the rest, but I know that, for example, $(1,2,7) \in \mathbb{N}^3 \notin \mathbb{N}^2 \times \mathbb{N}$ but instead $((1,2),7) \in \mathbb{N}^2 \times \mathbb{N}$. So how would I go about proving the statement.
108507
I don't understand a proof right at the beginning of this document found .   This proof is on why any base for the open sets in a second countable space has a countable subfamily that is a base.  My trouble comes in the second paragraph of the first proof. It says $\{B_{i_x}\mid x\in C_k\}$ is a countable set whose union is $C_i$. First, why is the set countable? If you take a set $B_{i_x}$ for any $x\in C_k$, what if $C_k$ is not countable itself? And why is the union $C_i$? Should it instead be $C_k$? I don't see $C_i$ mentioned anywhere in the second paragraph.
120389
I am assuming already that a) the union of countably many countable sets is countable and  b) $\omega_1$ is the least uncountable ordinal, so $x &lt; \omega_1$ if and only if $x$ is a countable ordinal.   I'm not sure if it is relevant but this question also allows The Axiom of Choice.   Thanks
29057
Some explanations:  A set S is  if there exists an injective function $f$ from $S$ to the natural numbers ($f:S \rightarrow \mathbb{N}$).  $\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ are all countable.  $\mathbb{R}$ is not countable.  The  $\mathcal P(A) $ is defined as a set of all possible subsets of A, including the empty set and the whole set.  $\mathcal P (\{\})=\{\{\}\}, \mathcal P (\mathcal P(\{\}))=\{\{\}, \{\{\}\}\} $  $\mathcal P(\{1,2\})=\{\{\}, \{1\},\{2\},\{1,2\}\}$  My question is:  Is $\mathcal P(\mathbb{N})$ countable? How would an injective function $f:S \rightarrow \mathbb{N}$ look like?
12018
Let $U$ be an open set in $\mathbb R$. Then $U$ is a countable union of disjoint intervals.    This question has probably been asked. However, I am not interested in just getting the answer to it. Rather, I am interested in collecting as many different proofs of it which are as diverse as possible. A professor told me that there are many. So, I invite everyone who has seen proofs of this fact to share them with the community. I think it is a result worth knowing how to prove in many different ways and having a post that combines as many of them as possible will, no doubt, be quite useful. After two days, I will place a bounty on this question to attract as many people as possible. Of course, any comments, corrections, suggestions, links to papers/notes etc. are more than welcome.
90330
I'm teaching my self topology using a book I found. This is the second part of a 4 part question. First part is .  I'm trying to prove the following problem from a book I found:     Let $X$ be a topological space and let $\mathscr{A}$ be a collection of subset of $X$. Prove  $\overline{ \bigcup \limits_{A \in \mathscr{A}} A}\supseteq \bigcup \limits_{A \in \mathscr{A}} \overline{A}$   *where the over line indicates closure.  First I'm going to show an example the them being equal, and then show an example of a proper superset. I know the examples are not needed for the proof, but I find them insightful, and these posts are like a notebook that I can refer back to later. Then I will attempt to prove this.     (I) Example of $\overline{ \bigcup \limits_{A \in \mathscr{A}} A} = \bigcup \limits_{A \in \mathscr{A}} \overline{A}$   I find that with "most" collections of subsets, the two sides come up equal. Let $X$ be $\mathbb{R}$ with the standard Euclidean metric. Also let, $\mathscr{A}=\{(1,6),(3,10)\}$. So then $ \bigcup \limits_{A \in \mathscr{A}} A= (1,10)$, and  $\overline{ \bigcup \limits_{A \in \mathscr{A}} A} =[1,10]$. Next the right side would be: $\bigcup \limits_{A \in \mathscr{A}} \overline{A}= [1,6] \cup [3,10]=[1,10]$. So it is possible for the two sides to be equal.     (II) Example of $\overline{ \bigcup \limits_{A \in \mathscr{A}} A} \supset \bigcup \limits_{A \in \mathscr{A}} \overline{A}$   The only way I know of involves a collection of subsets that "expands" in a way that converges - ie  $\bigcup_{n=1}^{\infty} \overline {B_{\frac{R \cdot n}{n+1}}}(x)=B_{R}(x)$. Let $X$ be $\mathbb{R}$ with the standard Euclidean metric. Also let, $\mathscr{A}=(1,\frac{10n}{n+1}), n\in\mathbb N$. So then $ \bigcup \limits_{A \in \mathscr{A}} A= (1,10)$, and  $\overline{ \bigcup \limits_{A \in \mathscr{A}} A} =[1,10]$.   Next the right side would be: $\bigcup \limits_{A \in \mathscr{A}} \overline{A}= \lim \limits_{n \rightarrow \infty} [1, \frac{10n}{n+1}]= [1,10)$ . And $[1,10] \supset [1,10)$. So it is possible for Closure of Unions to contain Union of Closures.     Proof: $\overline{ \bigcup \limits_{A \in \mathscr{A}} A}\supseteq \bigcup \limits_{A \in \mathscr{A}} \overline{A}$   (II) illustrates that the infinite union of closed sets can make an open (or half open) set. So: * $\bigcup \limits_{A \in \mathscr{A}} \overline{A}$ can be (half)open.  * $\overline{ \bigcup \limits_{A \in \mathscr{A}} A}$ must be closed. Since we're dealing with the same collection of subsets, then the difference will be at the boundary points. And thus, the closed set will contain the (half)open set.  QED  The part of the proof i'm not sure about is at the end where I say, "the difference will be at the boundary points." In (II) that is the case, but will that always be the case when dealing with the most general topological spaces?
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!
112359
This is part of a bigger problem I'm trying to prove, but my argument relies of the validity of the following idea. Note that when I say countable, I don't mean finite -- I mean countable infinity.   Consider the set of natural numbers, $\mathbb{N}$. Now take a countable subset of them, call it $\mathsf{S}_1$. Then take a countable subset of $\mathbb{N}\setminus{\mathsf{S}_1}$ and call it $\mathsf{S}_2$. Then take a countable subset of $\mathbb{N}\setminus\{{\mathsf{S}_1}\cup{\mathsf{S}_2}\}$ and call it $\mathsf{S}_3$. Continue in this manner to construct $\mathsf{S}_i$'s such that ${\mathsf{S}_i}\cap{\mathsf{S}_j}=\emptyset$ for $i≠j$.  My question is this: is it necessarily the case that eventually there will be finitely many $\mathsf{S}_i$'s with $\mathbb{N}\setminus\bigcup_{i}{\mathsf{S}_i}={P}$ where $P$ is either empty or finite? My guess is yes, but I'm not how to prove it or how to find a counterexample.
10969
Consider a set $E=\bigcup_{j=1}^{\infty}E_{j}$.  How can I re-express $E$ in such a way that all of the contributions to $E_{n}$ are covered only once.  Presumably, such a re-expression of $E$ will be some kind of countable union of disjoint sets.  The end-goal is to answer the following problem: to show that if $m'$ is any map from the Lebesgue measurable sets of $\mathbb{R}^{d}$ to $[0,\infty]$ which obeys countable additivity and $m'(\emptyset)=0$, then $m'$ also obeys monotonicity and sub-additivity.  Showing that $m'$ obeys monotonicity is easy.  Sub-additivity seems easy at first glance, until you actually have to prove it.  Perhaps there are better ways to do it, but my strategy is to write $E=\bigcup_{j=1}^{\infty}E'_{j}$ where the $E'_{j}$ are all disjoint "components" of $E$.  Then applying additivity I could expand out $m\left(\bigcup_{j=1}^{\infty}E'_{j}\right)$ using additivity (I assume the $E'$ will be  sets formed by multiple set operations of the original $E_{j}$, so applying additivity could be potentially tricky).  Once this expression is obtained, I presume it will be easy to compare it to $\sum_{j=1}^{\infty}m'(E_{j})$ and show that it is smaller, hence proving sub-additivity.  UPDATE  From the answer below...  \begin{align*} m'(E) &amp;=m\left(\bigcup\limits_{j=1}^{\infty}E_{j}\right)\\ &amp;=m\left(\bigcup\limits_{j=1}^{\infty}\left(E_{j}-\bigcup\limits_{k=1}^{j-1}E_{k}\right)\right)&amp;\text{(remove duplicate inersections)}\\ &amp;=\sum\limits_{j=1}^{\infty}m\left(E_{j}-\bigcup\limits_{k=1}^{j-1}E_{k}\right)&amp;\text{(apply assumed additivity)}\\ &amp;\leq\sum\limits_{j=1}^{\infty}m(E_{j}) &amp;\text{(apply aleady proved monotonicity)} \end{align*} so that $m'$ is also sub-additive as required.
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.
51374
I am doing some homework exercises and stumbled upon this question. I don't know where to start.      Prove that the union of countably many countable sets is countable.   Just reading it confuses me.   Any hints or help is greatly appreciated! Cheers!
94485
I'm pretty sure I've asked way too many questions on sets already(still, a big thanks to everyone who helped) and even though I'm starting to see what's going on there are still some issues, for example this question:  Prove that $\bigcup P(X)=X$, where $P(X)$ is the power set for the set $X$  So, what I can do is the following:  $a \in \bigcup P(X) \implies \exists b \subset X$ s.t. $a\in b \implies a \in X$ and for the other direction I can take $b=X$.  However, I'm not sure whether this is correct, and in particular, the bit with $b \subset X, a\in b \implies a \in X$  If I take $X=\{\{1\},\{2\}\}$, then $P(X)=\{\emptyset,\{1\},\{2\},\{\{1\},\{2\}\}\}$, hence $\bigcup P(X)=\{1,2,\{1\},\{2\}\}$ which is not equal to $X$ by ZF$1$  Where's the problem?  Thanks
103098
The collection of all subsets of $\mathbb{Z}$ is uncountable, due to   But how can I prove that the collection of all finite subsets of $\mathbb{Z}$ is countable?
91996
This is a question from my proofs course review list that I have had trouble understanding.   I understand the concept of disjoint sets.  I'm not sure what they mean by countable. How would one prove a set is countable and furthermore, that the union of two countable sets is countable.  Please help me get started with the question by understanding this concept.
55314
While I was reading Enderton's "A mathematical introduction to Logic", I came across the proof of the following sentence: "The set of all finite sequences of members of the countable set A is also countable".   Proof: The set S of all such finite sequences can be characterized by the equation  $$S=\bigcup_{n \in N} A^{n+1}$$ Since A is countable, we have a function f mapping A one-to-one into N. The basic idea is to map S one-to-one into N by assigning to $(a_0,a_1,...,a_m)$ the number $2^{f(a_0)+1}3^{f(a_1)+1}\cdot ... \cdot p_m^{f(a_m)+1}$, where $p_m$ is the $(m+1)$st prime. This suffers from the defect that this assignment might not be well-defined. For conceivably there could be $(a_0,a_1,...,a_m)=(b_0,b_1,...,b_n)$, with $a_i$ and $b_j$ in A but with $m\neq n$. But this is not serious; just assign to each member of S the smallest number obtainable in the above fashion. This gives us a well-defined map; it is easy to see that it is one-to-one.  Note: P is a finite sequence of members of A iff for some positive integer $n$, we have $P=(x_1,...,x_n)$, where each $x_i \in A$.  First of all, I cannot understand why the former assignment might not be well-defined and the latter assignment is well-defined. Secondly, I cannot understand what Enderton means by "just assign to each member of S the smallest number obtainable in the above fashion". By the way, is $(a,b,c,d) = ((a,b),(c,d))$ true? Also, in which cases can I omit/add parentheses in a tuple so as to have an equal tuple?
7674
(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$  (b) $S = \bigcup_{k=1}^\infty S_k$   Work: For (a), I am not too sure about what approach I should use. I think finding a bijective function between the $S_k$ and $\mathbb{N}$ is hard to do . I also thought about using the Schroeder-Bernstein theorem and find injective functions $f:\mathbb{N}\rightarrow S_k$and $g:S_k\rightarrow\mathbb{N}$ in order to prove that $S_k$ and $\mathbb{N}$ are numerically equivalent. However, I have a hard time finding and proving these injective functions. I haven't really looked at (b) as I have yet to complete (a).