I know that is possible to build a bijection between the set of natural numbers $\mathbb{N}$ and the natural plane (the cartesian product of $\mathbb{N}$ by itself, $\mathbb{N} \times \mathbb{N} = \mathbb{N}^2$. This is done by diagonally traversing the plane from zero upwards with triangles of growing size.  Is there a simple algebraic form for that bijection? That is, is it possible to write explicitly some invertible $f(i, j): \mathbb{N} \times \mathbb{N} \leftrightarrow \mathbb{N}$?  I need to index in a simple way couples of natural numbers.
98667
I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I can't figure out what such a bijection would be. The paper that I'm reading gives an example of an injective function $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$, $f(n)=(0,n)$, and an injective function $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $g(a,b)=2^a3^b$. I was thinking perhaps if there were some way to combine these two, I could find a bijection, but I have no idea how to go about that or if it's even possible.  What is an example of a bijection between these two sets, and please explain the process by which you found it?
69916
I need to find if set $I$ of all injective functions $\mathbb{N} \rightarrow \mathbb{N}$ is equinumerous to $\mathbb{R}$. Still, I have no idea how to work with set of functions, it's something new to me since I have only encountered sets of numbers before.
2845
Let $A,B,C$ be sets, and $B \cap C=\emptyset$. Show $|A^{B \cup C}|=|A^B \times A^C|$ by defining a bijection $f:A^{B \cup C} \rightarrow A^B \times A^C$.  Any hints on this one?  Thank you!
104109
I found a problem in which I had to construct a bijection between set of all binary sequences and set of all subsets of $\mathbb N$. Is my solution correct? $\phi : 2^{\mathbb N}\to \{0,1\}^{\mathbb N}$ is defined by, $\phi(\{n_1,n_2,.....\})=$Binary sequence with $1$ only at the positions $n_k$ and $0 $ elsewhere.Is this correct?
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?
74387
I'm trying an old problem here:   Suppose $n\mid m$, and I have a natural ring homomorphism $\varphi\colon \mathbb{Z}/m\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}$ defined by $\varphi(j)=j\mod{n}$. I can verify that this is a ring homomorphism, but why does it induce a surjective group homomorphism on the unit groups $(\mathbb{Z}/m\mathbb{Z})^\times\to(\mathbb{Z}/n\mathbb{Z})^\times$?  My question in particular is why is it surjective? I take $k\in(\mathbb{Z}/n\mathbb{Z})^\times$. Then there exist integers $s,t$ such that $sn+tk=1$. Since $n\mid m$, I can also write $m=na$. So multiplying through I get $sm+tka=a$. I'm lost here. How can I find a unit in $(\mathbb{Z}/m\mathbb{Z})^\times$ which maps to $k$ to show surjectivity?
80253
This is a problem from Discrete Mathematics and its Applications:   Explain why $A \times B \times C$ and $(A \times B) \times C$ are not the same.   I understand the process behind the Cartesian product of two sets:  Let $A$ and $B$ be sets. The Cartesian Product of $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a,b)$, where $a \in A$ and $b \in B$. Hence, $$A \times B = \{(a,b)\mid a \in A \land b \in B\}.$$  Youre forming a set of all the possible ordered pairs where one element is a member of the first set and the other element is a member of the other set. How would you start this proof or explanation? To me these should be the same because it involves the same operation (Cartesian cross product). Usually when there are three expressions that are applied the same operation, you just go left to right, say 4 * 5 * 6. I don't understand how you would explain A x B x C is not equal to (A x B) x C. To me, using my last example, that's like explaining 4 * 5 * 6 is not equal to (4 * 5) *6.
80640
$Z$ is the set of non-negative integers including $0$. Show that $Z \times Z \times Z$ is countable by constructing the actual bijection $f: Z\times Z\times Z \to \mathbb{N}$ ($\mathbb{N}$ is the set of all natural numbers). There is no need to prove that it is a bijection.   After searching for clues on how to solve this, I found $(x+y-1)(x+y-z)/z+y$ but that is only two dimensional and does not include $0$.  Any help on how to solve this?
77615
How would I show the following have a bijection. Which is one to one and onto ofcourse.  $\mathbb{Z}\rightarrow \mathbb{N}$  I know I need to find a function. But I do not see the pattern that makes integer go to natural. I already did this problem from natural to integer but now I want to see it done this way.  I have listed some numbers  $,..,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,..$  $1,2,3,4,5,6,7,8,9,10,11,12,13,14,.$
115
Prove that the interval $(0, 1)$ and the Cartesian product $(0, 1) \times (0, 1)$ have the same cardinality  using the SB theorem? Also how does one find a bijection on $f:(0, \infty) \to (0,1)$ such that they have the same cardiniality?
28615
This has always been one of my most favorite exercises from Group Theory, and I was surprised to see that this hasn't been asked before. To repeat:     Characterize the natural numbers $n$ such that there is a surjective group homomorphism from $S_n$ to $S_{n-1}$.   I have a solution which I will post in a couple days (if someone doesn't recreate it), but I am more interested in seeing how other people would approach this problem. I am very interested in alternate proofs of this characterization.
82640
I was wondering if it is possible to produce an explicit bijection $h\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$. If we can produce an explicit injection $i\colon \mathbb{R} \rightarrow \mathbb{R}/\mathbb{Q}$, can the  be used constructively?  It is clear that the two sets have the same cardinality, so the existence of such a bijection is trivial. What I am really looking for is a nice-looking bijection, or a proof that no such nice-looking bijection exists, for a definition of "nice-looking" which I cannot quite figure out.  One problem which I think makes finding such a bijection difficult is that any natural injection of $\mathbb{R}/\mathbb{Q}$ (ie, those injections in which one representative is chosen from each coset) produces a non-measurable set, specifically a .  I hate to ask such a vague question, but I'm really not sure about whether the correct answer is constructive, or whether it is a proof that any such bijection is in some sense "very complicated."  As a final note, the motivation for this question came from , in which I was somewhat astonished to see such a clear, constructive bijection given between $\mathbb{R}$ and $\mathbb{R} \setminus S$, where $S$ is countable.
56817
I have alot of questions.   Do Infinite sets have the same cardinality when there is a bijection between them? Are $\mathbb{N}$ and $\mathbb{Z}$ infinite sets? I assume they are, but why? Why does there not exist a bijection between them? Why do $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ have the same cardinality? I assume there exists a bijection between them, but how can I find this function?
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.
83432
Explain why $\mathbb{Z \times Z}$ and $\mathbb{R \times R}$ is not a field and that why any external direct sum of two fields cannot be a field. I believe it has much to do with the lack of every non-zero element having an inverse, however I am having difficulty seeing it.
59512
I need to give an explicit bijection between $(0, 1]$ and $[0,1]$ and I'm wondering if my bijection/proof is correct. Using the hint that was given, I constructed the following function $f: (0, 1] \to [0,1]$: $$ x \mapsto \left\{ \begin{array}{ll} 2 - 2^{-i} - 2^{-i-1} - x &amp; \text{if } x \in (1-2^{-i}, 1-2^{-i-1}]\text{ for an } i \in \mathbb{N}_0 \\ 1 &amp; \text{if } x = 1 \end{array}\right. $$  It's easy to see that for every $x \in (0, 1)$, there exists such an $i$.  Now define $\tilde{f}: [0,1] \mapsto (0,1]$ with  $$ x \mapsto \left\{ \begin{array}{ll} 2 - 2^{-i} - 2^{-i-1} - x &amp; \text{if } x \in [1-2^{-i}, 1-2^{-i-1})\text{ for an } i \in \mathbb{N}_0 \\ 1 &amp; \text{if } x = 1 \end{array}\right. $$  I want to prove that $\tilde{f}(f(x)) = f(\tilde{f}(x)) =  x$, so it has an inverse and therefore is a bijection. The case $x=1$ is trivial, so assume that $x \in (0,1)$ with $x \in (1-2^{-i}, 1-2^{-i-1}]$ for some $i \in \mathbb{N}_0$. This interval has length $1-2^{-i-1} - (1-2^{-i}) = 2^{-i-1}$, so we can write $x = 1-2^{-i} + \epsilon\cdot 2^{-i-1}$ for some $\epsilon \in (0, 1]$. We now calculate $f(x)$: \begin{align*} f(x) &amp;= 2 - 2^{-i} - 2^{-i-1} - x\\ &amp;= 2 - 2^{-i} - 2^{-i-1} - (1-2^{-i} + \epsilon\cdot 2^{-i-1})\\ &amp;= 1 - 2^{-i-1}(1+\epsilon). \end{align*} We conclude that $f(x) \in [1-2^{-i}, 1-2^{-i-1})$. We now use the definition of $\tilde{f}$, so if we calculate $\tilde{f}(f(x))$, we get \begin{align*} \tilde{f}(f(x))  &amp;= 2 - 2^{-i} - 2^{-i-1} - f(x) \\ &amp;= 2 - 2^{-i} - 2^{-i-1} - (2-2^{-i} - 2^{-i-1} - x) \\ &amp;= x. \end{align*}  We conclude that $f$ has an inverse. Using exactly the same reasoning, we get that $f(\tilde{f}(x)) = x$ for all $x \in [0,1]$. Therefore it's inverse exists and it has to be a bijection.  I know there are less cumbersome methods of proving this fact, but as of now this is the only thing I can come up with.
72729
I need help with this question.  Construct an explicit bijection from [0,1] to (0,1) over the real numbers.  I have one that works over naturals but however I cannot not figure it out over the reals. Any and all help is appreciated.