$|N| = |N \times N|$ ($N \times N$ countable)  I tried to build a bijective function $f(n,m) \to n$. I saw some posts about this question but there wasn't any example nor a good explanation.
14753
I'm examining a proof I have read that claims to show that the Cartesian product $\mathbb{N} \times \mathbb{N}$ is countable, and as part of this proof, I am looking to show that the given map is surjective (indeed bijective), but I'm afraid that I can't see why this is the case. I wonder whether you might be able to point me in the right direction?  Indeed, the proof begins like this:  "For each $n \in \mathbb{N}$, let $k_n, l_n$ be such that $n = 2^{k_n - 1} \left(2l_n - 1 \right)$; that is, $k_n - 1$ is the power of $2$ in the prime factorisation of $n$, and $2 l_n - 1$ is the (necessarily odd) number $\frac{n}{2^{k_n - 1}}$."  It then states that $n \mapsto \left(k_n , l_n \right)$ is a surjection from $\mathbb{N}$ to $\mathbb{N} \times \mathbb{N}$, and so ends the proof.  I can intuitively see why this should be a bijection, I think, but I'm not sure how to make these feelings rigorous?   I suppose I'd say that the map is surjective since given any $\left(k_n , l_n \right) \in \mathbb{N} \times \mathbb{N}$ we can simply take $n$ indeed to be equal to $2^{k_n - 1} \left(2l_n - 1 \right)$ and note that $k_n - 1 \geq 0$ and thus $2^{k_n - 1}$  is both greater or equal to one so is a natural number (making the obvious inductive argument, noting that multiplication on $\mathbb{N}$ is closed), and similarly that $2 l_n - 1 \geq 2\cdot 1 - 1 = 1$ and is also a natural number, and thus the product of these two, $n$ must also be a natural number. Is it just as simple as this?  I suppose my gut feeling in the proving that the map is injective would be to assume that $2^{k_n - 1} \left(2 l_n - 1 \right) = 2^{k_m - 1} \left(2 l_m - 1 \right)$ and then use the Fundamental Theorem of Arithmetic to conclude that $n = m$. Is this going along the right lines? The 'implicit' definition of the mapping has me a little confused about the approach.    On a related, but separate note, I am indeed aware that if $K$ and $L$ are any countable sets, then so is $K \times L$, so trivially, taking the identity mapping we see trivially that this map is bijective and therefore that $\mathbb{N}$ is certainly countable (!), and thus so is $\mathbb{N} \times \mathbb{N}$. Hence, it's not really the statement that I'm interested in, but rather the exciting excursion into number theory that the above alternative proof provides.
99981
Is there a function that can be bijective, with the set of natural numbers as domain and range, other than $f(n) = n$?
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?
82895
If $m|n$. Why the map $f\colon \mathbb{Z}_n^\times \to \mathbb{Z}_m^\times$ given by $a \mod{n}\mapsto a \mod m$ is a surjective homomorphism of groups?  Attempt: I proved it is well a well defined homomorphism because the canonical projection $\overline{f}\colon \mathbb{Z}_n \to \mathbb{Z}_m$ is a surjective ring homomorphism, it extends $f$ and maps units to units.  But I can't prove surjectiveness. Given $a\in\mathbb{Z}$ such that $(a,m)=1$ I'm looking for a $k\in\mathbb{Z}$ such that $(a+k\cdot m,n)=1$. I don't know why one of the $n/m$ candidates for such $k$ makes the number $a+k\cdot m$ an unit modulo $n$.
93710
Statement: There are uncountably many surjections from $\mathbb N$ to $\mathbb N$.  Is the following proof valid:  The real numbers are uncountable.   There exists a bijection between the set of real numbers and the set of all functions from $\mathbb N$ to $\{0,1\}$.   Given a function, $f$, from $\mathbb N$ to $\{0,1\}$, construct a surjection from $\mathbb N$ to $\mathbb N$, denoted $g$, as follows:  We map the $n$th composite number to $n$, and the nth prime, to $f(n)$.   Clearly this is a surjection since the composite numbers are countable. Clearly different functions $f$ lead to different surjections $g$. Since there are uncountably many $f$s, there are uncountably many surjections $g$.
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.
114758
What my thought was that the bijection was a piecewise function:  $f(x) = 1/n+1$ if $x = 1/n$ for some $n \in \Bbb N$ and $x=1/n$ if $x \neq1/n$ for some $n \in \Bbb N$.  However, the textbook says this is incorrect. I don't actually see why. Was it a matter of brackets or the open variable $(0,1]$, which is what I tend to think.
69594
Is this statement true? i.e. If $f(n)$ is injective and $p_n \rightarrow L$, does $p_{f(n)} \rightarrow L$?? (I realize that it's technically only a rearrangement if $f(n)$ is bijective.)   My attempt at a proof:  Since $p_n \rightarrow L$, we have that, for all $n$ except $n \le N$, $d(p_n, L) &lt; \epsilon$.  Let $S = \{n \ | \ f(n)\le N\}$, let $n_0$ be the largest $n \in S$, we know there is such a largest $n$ because $f(n)$ is injective. Now we have that $\forall \ n &gt; n_0 \ f(n) &gt; N$ which implies that $p_{f(n)} \rightarrow L$, as required.  Is this correct? Does my proof work?
97553
How can one show that there is a bijection from $\mathbb N$ to $\mathbb Q \times \mathbb Q $?
83992
I learned that the set of all one-to-one mappings of $\mathbb{N}$ onto $\mathbb{N}$ has cardinality $|\mathbb{R}|$.  What about surjective functions and bijective functions?
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).
45786
Suppose that $\;f_1,\;f_2:\;A\to B$ such that $f_1$ is injective and $f_2$ is surjective.   I was trying to find out whether there exists $f_3:\;A\to B$ such that $f_3$ is bijective. Is it possible to construct it from $f_1$ and $f_2$?  I tried proving the statement non-constructively via a cardinality argument, but ended up hand-waving a lot (i.e., since the cardinality is the same, there exists a bijection, a bit of circular reasoning). But, I'd be more interested in a construction based argument, as I can't think of one.
30922
Find a bijection from $\mathbb R \to  \mathbb R-\mathbb N$. I want to set my function up such that all natural numbers get mapped to $n+.1$ and reals of the form $n+.1$ to $2n+.1$ is this correct?
59985
Define a bijection between $Z^{X \cup Y}$ and $Z^X \times Z^Y$, where $X, Y \in \mathcal{P}(\Omega) $ and $X \cap Y = \emptyset$  I was given the following task to prove. I know that we need a map $h : Z^{X \cup Y} \ \to Z^X \times Z^Y$ Firstly, we have to define a function $h(f)$ and the show that is both injective and surjective. However, I can't define it. I know that LHS should be $h(f)(x)(y)$. Is it correct ? What should be RHS?
54523
Show that $\mathbb{N} \times \mathbb{N} \sim\mathbb{N}$.  I found a bijection such that $g(k,l): \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ by  $$g(k,l) = {(k+l)(k+l-1) \over 2} - (l-1)$$  But I am having trouble showing that it is 1-1 and onto.  First I said let   $${(k_1+l_1)(k_1+l_1-1) \over 2} = {(k_2+l_2)(k_2+l_2-1) \over 2}$$  and I was trying to use that to show $k_1 + l_1 = k_2 + l_2$ but I don't know how to do that, and once I get there I'm not sure how to show that $l_1=l_2$ or $k_1=k_2$  for onto I said let $y \in k+l$.  Then $${y(y-1) \over 2} = y$$ so therefore $g(k,l)$ is onto.  therefore g is a bijection.
95380
I tried to solve this problem without any success. I really hope that you will know the answer. $f(n,m)$ presents the number of binary strings (empty string included) that include at most n times '1', and at most m times '0'.      Prove: $$f(n,m) = \binom{n+m+2}{n+1}-1$$
116458
Find the number of all bijective functions from A to A. Given set A   has n elements   First number of one-to-one functions from A to A is n! as first element has choice of n elements, but second element has only n-1 since by definition of one-to-one it can't go to the first element choice..... Now with onto functions I am stuck how to do .  I notice this question has been answered previously by induction, I just think a counting proof would be more helpful for me to learn. Also I am unable to follow that argument there.