I am having trouble proving that the function $$f: N\times N \rightarrow N, \ \ f(i,j)=2^{i-1}(2j-1)$$ is surjective.   Work: I know that using the theorem in which $n$ is the product of prime numbers play an important role. For instance, $n=2^{i-1}p$, $p$ is the product of all prime factors of $n$. However, from here I don't know how to proceed. What makes it difficult for me is that how am I suppose to find an arbitrary $n\in N$ such that $f(i,j)=n$?
120977
I am having trouble with the following problem:   $f: N\times N\rightarrow N$ and $f(i,j)=2^{i-1}(2j-1)$. Prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent.   Work: I am told that Euclid's Lemma will be useful to proving injection and also that for any positive integer $n$, $n$ is a product of prime numbers.   For injection, I set $f(a,b)=f(x,y)\rightarrow 2^{a-1}(2b-1)=2^{x-1}(2y-1)$.  Then I distributed across to get $2^ab-2^{a-1}=2^xy-2^{x-1} \rightarrow 2^ab-2^xy=2^{a-1}-2^{x-1} \rightarrow 2(2^{a-1}b-2^{x-1}y)=2^{a-1}-2^{x-1}$.   From here, I am unsure how to apply Euclid's Lemma to arrive at the injection result.  I am even more unsure how to prove surjection.
95705
Let $f: X \rightarrow Y$ and $g: Y \rightarrow X$  If $f \circ g$ is surjective, then f is surjective, too.  I think that is true.   Question: How can I proove that? I have so far:   $\forall y \in Y: \exists x \in X : f(x)=y$  $\forall x \in Y : \exists y \in Y : f \circ g(y)= x$
32187
Let $A_1,...A_k$ be countable sets, I need to prove that the union $\bigcup_{i=1}^{k}A_i$ is countable by explicitly building a surjection.  I can't assume that the sets are disjoint.  I can easily build an injection $g:\bigcup_{i=1}^{k}A_i\rightarrow \mathbb{N}\times\mathbb{N}$ by defining $g(a)=(f_{i}(a),i)$ where $f_i$ is the first bijection from the bijections $f_i,...f_k$ that maps $A_i\rightarrow\mathbb{N}$ such that $a\in A_i$.  However, this map $g$ obviously isn't surjective.  Any ideas for building such map?
19243
Let $f : G \longrightarrow G^\prime$  be a group homomorphism. Then $f$ is injective iff $\ker(f) = \{1\}$ where $1$ represents the identity of $G.$  First I tried to prove  that if $f$ is injective then $\ker(f) = \{1\}.$  Since $f$ is homomorphism, $f(1)=1^\prime$ (identity elt of $G^\prime$) then $1\in  \ker(f),$ so $\{1\} \subset \ker(f),$ and f is injective $\ker(f) = \{1\}$   For this part, I got help from professor but I can't exactly understand the bold and italic part.  This is my proof for other side ( if $\ker(f) = \{1\}$, then $f$ is injective. )  let $f(a)=f(b)$, then $f(a) * f(b)^{-1} = 1^\prime$ and $f(ab^{-1}) = 1^\prime$ so $ab^{-1}$ is in $\ker(f) = \{1\}$ then $a=b.$
123135
Let $n \in \mathbb{N}$ and $p$ be a prime number. Let $f(x),g(x) \in \mathbb{Z}_{p^n}[x]$ such that, in $\mathbb{Z}_{p^n}[x]$, $f(x)g(x)=0$. Prove that $a_ib_j=0$ for all $i,j$, where $a_i$ and $b_j$ are the coefficients of $f(x)$ and $g(x)$.  I have the set of equations (for degree $r$ and degree $s$): $$a_rb_s=0, a_rb_{s-1}+a_{r-1}b_s=0,...,a_0b_0=0.$$ From these, how do I conclude $a_ib_j=0$ for all $i,j$? Also, I found that for $n=1$, the polynomial ring is an integral domain, so the conclusion holds. I had an idea to use induction on $n$, but do not know how to proceed.
105759
Prove or disprove: if $f:G \rightarrow H$ is a surjective group homomorphism, then   1) $f(A)$ normal implies $A$ normal.  2) $S$ is a p-Sylow subgroup of $G$ implies $f(S)$ is a Sylow-p subgroup of $H$.   I believe 1 is false since I believe we need injectivity, but I cannot think of a counterexample...  I believe 2 is true but do not know how to show it...
42566
For nonempty sets $A$ and $B$ and functions $ f: A \to B$ and $g: B \to A$, suppose that $ g \circ f = i_A$. Prove that if $f$ is onto, then $g$ is $1-1$.   Here is what I started, I don't think it's correct.   Suppose $f$ is onto  i.e for each element $b \in B$ there is an element of $a\in A$, $f(a)=b$. (definition of onto).   Let $y,\ z$ be any two elements of $B$.Then $y=f(a)$ and $z=f(b)$ for some $a,b \in A$.   If $g(y)=g(z)$, then $g(f(a)) = g(f(b))$,which implies that $a=b$, so $f(a)=f(b)$, so $y=z$.   Thus, whenever $g$ maps $y$ and $z$ to the same element in $A$, $y=z$, so $g$ is one-to-one.   PS: New to proof writing, any constructive criticism is much appreciated.
45862
Prove that the function $f: R\to R$ given $f(x)=x\cdot |x|$ is a bijection  Proof 1: f is injective  Suppose $$f(a) = f(b) \implies a\cdot |a| = b\cdot |b|$$ $$\implies (a\cdot |a|)^2 = (b\cdot |b|)^2$$ $$\implies a^4 =b^4$$ $$a=b$$ Thus, f is injective  Proof 2: f is surjective  Pick $n\in R$, we want to show $n=f(x)$ for some $x\in R$  $$\implies n= a\cdot |a|$$ for some $a\in R$  I dont know how to complete the surjective proof
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$
33608
Let $f$ and $g$ be functions such that $f\colon A\to B$ and $g\colon B\to C$. Prove or disprove the following a) If $g\circ f$ is injective, then $g$ is injective  Here's my proof that this is true. Let $A = \{4,5\}$, $B = \{3,9\}$, $C = \{1,2\}$ $f(4) = 3$; $f(5) = 9$ $g\circ f(4) = 1$ and $g\circ f(5) = 2$ Since no 2 elements map to the same element in the range $g\circ f$ and $g$ are both injective.  b) If $f$ and $g$ are surjective, then $g\circ f$ is surjective.  Here's my proof that this is true. Let $A = \{1,2\}$, $B = \{4\}$, $C = \{5\}$, $f(1) = 4$; $f(2) = 4$ $g\circ f(1) = 5$ and $g\circ f(2) = 5$. Since no elements are left unmapped then $g\circ f$ and $f$ and $g$ are surjective Are these proofs valid? **Edit: Ok so I revised my proof for a. I will disprove it using a counterexample. Let A = {4}, B = {3,9}, C={1}. g∘f(4) = 1 and g(3) = 1 and g(9) = 1 g∘f is injective but g is not injective because 3 and 9 both map to 1. Is that a valid disproof? Now I'm just having some trouble disproving or proving b. If anyone could lend some tips. Also this is not homework. Just reviewing for an exam.
99128
I need help with proving this:  $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$  $C\subseteq Y$  Thanks.
104389
I don't follow understand what this theorem is saying: "Every function $f: A \to{\cal P}(A)$ is not surjective."   Is this saying so for example let A = {1,2,3} then the power set of A is {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} Is this saying that there is no surjective function that takes every element in each of its power sets to atleast 1 element in A?  Is my understanding correct?
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
119044
Let   $\varphi(n)$ be the totient-function  $\sigma(n)$ be the divisor-sum-function    It is clear that every prime number $n$ is the arithmetic mean of $\varphi(n)$ and $\sigma(n)$, in other words , the equality $$\varphi(n)+\sigma(n)=2n$$ holds.      Can the given equality hold for a composite number $n$ ?   Upto $10^8$, I did not find an example. I conjecture that the equality can only hold for primes or $n=1$. How can I prove it ?
111850
Given an arbitrary set $A$, let $f : A \rightarrow\wp(A)$, be the function defined for all $a\in A$ by "$f(a) = \{a\}$"   Is $f$ injective?  Is $f$ surjective?    I am struggling with this question.  How am i able to identify if the function is injective? Can somebody give an example?  What confuses me is the function "f(a) = {a}"
23678
I'm actually in a course of Abstract Algebra, and the teacher asked some interesting questions at the end of a course on the material we had seen. I found the answer to the first question, but the other two leave me perplexed. Could you give me your opinion on the questions (2) and (3)?  (1) Is the function $f : \mathbb{N} \to \mathbb{N} $ such that $$f= \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; ...\\ f(1) &amp; f(2) &amp; f(3) &amp; f(4) &amp; ... \end{pmatrix} = \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; 4 &amp; ...\\ 2 &amp; 3 &amp; 4 &amp; 5 &amp; ... \end{pmatrix}$$ is a permutation? Answer : no, because $1$ isn't an element in the image.  (2) Is there a function $ f \in S_E$  that is factorisable into disjoint cycle of infinite order such that $\mid \{n \in \mathbb{N} : f(n) \not= n\}\mid &lt; \infty$ ?  Definitions :    $S_E$ is the set of all permutation of E.  Let the set $E \not= \emptyset$. W say that a map $f : E \to E$ has an inverse function, if there is a mapping $g : E \to E$ such that both composition $f \circ g$ and $g \circ f$ are the application identity for each $x$ element of $E$. We say that $f$ is a permutation (bijection) of $E$ .    (3) Does the subset of functions $\in S_{\mathbb{N}}$ ($S_E$ with $E=\mathbb{N}$) consistent with $\mid \{n \in \mathbb{N} : f(n) \not= n\}\mid &lt; \infty$ form a group?
43379
I need help solving the next question, I think that it's actually a refutation:     let $f,g: \mathbb{N} \rightarrow \mathbb{N}$  so that $\forall n ∈ \mathbb{N} : f(n) = g(2n)$   Prove that if $f$ is surjective $g$ is not injective