Let $G_1$ and $G_2$ be two finite groups such that for any finite group $H$, $\lvert\operatorname{Hom}(H,G_1)\rvert = \lvert\operatorname{Hom}(H,G_2)\rvert$. How can I show that $G_1 \cong G_2$ ?
Group Theory – Homomorphism Equality Implies Group Isomorphism
abstract-algebrafinite-groupsgroup-isomorphismgroup-theory
Related Solutions
Now that you've worked out the most, let me add some details (and the surjectivity part). For $f\colon G_1\longrightarrow G_2$ isomorphism (which exists by assumption), your candidate isomorphism is: \begin{alignat*}{2} \phi:\operatorname{Aut}(G_1)&\longrightarrow&\operatorname{Aut}(G_2) \\ \varphi&\longmapsto& \phi_\varphi: G_2 &\longrightarrow G_2 \\ &&g&\longmapsto \phi_\varphi(g):=(f\varphi f^{-1})(g) \\ \tag 1 \end{alignat*} First, you need to prove that $\phi$ is well-defined, which in this case means that $\phi_\varphi$ is indeed an automorphism of $G_2$, for every $\varphi\in\operatorname{Aut}(G_1)$. In fact:
- for every $\varphi\in\operatorname{Aut}(G_1)$, $\phi_\varphi=f\varphi f^{-1}$ is a composition of (right to left): a bijection from $G_2$ to $G_1$, a bijection from $G_1$ to itself, and a bijection from $G_1$ to $G_2$; therefore, $\phi_\varphi$ is a bijection from $G_2$ to itself;
- since $f,\varphi,f^{-1}$ are all operation-preserving maps, then, for every $\varphi\in\operatorname{Aut}(G_1)$ and $g,h\in G_2$: $\phi_\varphi(gh)=(f\varphi f^{-1})(gh)=$ $f(\varphi(f^{-1}(gh))=$ $f(\varphi(f^{-1}(g)f^{-1}(h)))=$ $f(\varphi(f^{-1}(g))\varphi(f^{-1}(h)))=$ $f(\varphi(f^{-1}(g)))f(\varphi(f^{-1}(h)))=$ $(f\varphi f^{-1})(g)(f\varphi f^{-1})(h)=$ $\phi_\varphi(g)\phi_\varphi(h)$.
Therefore, indeed $\phi_\varphi\in\operatorname{Aut}(G_2)$ for every $\varphi\in\operatorname{Aut}(G_1)$. This proves that $\phi$ in $(1)$ is well-defined.
Injectivity of $\phi$ (here you can avoid the contradiction argument): $\phi_\varphi=\phi_{\varphi'}\Longrightarrow$ $f\varphi f^{-1}=$ $f\varphi' f^{-1}\Longrightarrow$ $\varphi=\varphi'$.
Surjectivity of $\phi$: for every $\psi\in\operatorname{Aut}(G_2)$, we have that $f^{-1}\psi f\in\operatorname{Aut}(G_1)$ (the proof mimics exactly the one about the good-definiteness of $\phi$ above) and $\psi=$ $(ff^{-1})\psi (ff^{-1})=$ $f(f^{-1}\psi f)f^{-1}=$ $\varphi_{f^{-1}\psi f}$.
You have already shown that $\phi$ preserves the operation (composition).
The notation in part 3 can be made more precise:
Elements of $G_1/N_1 \times G_2/N_2$ are of the form $(g_1N_1, g_2N_2)$ for $g_1\in G_1, g_2\in G_2$, so while $(N_1, N_2)\in G_1/N_1 \times G_2/N_2$, it wouldn't make sense to say $N_1\times N_2\in G_1/N_1 \times G_2/N_2$.
If we wanted to expand, we could write $(N_1, N_2)$ as $(\{n_1: n_1\in N_1\},\{n_2: n_2\in N_2\})$ or $(n_1 N_1, n_2 N_2)$ for some $n_1\in N_1, n_2\in N_2$, but we can't just write $(n_1, n_2)$.
Similarly, to verify the identity element, I would just write $$(g_1 N_1, g_2 N_2)(N_1, N_2)=(g_1 N_1, g_2 N_2)(e_1N_1, e_2N_2)=((g_1e_1) N_1, (g_2 e_2)N_2)=(g_1 N_1, g_2 N_2),$$ where $e_1$ and $e_2$ are the identities of $G_1$ and $G_2$.
Finally, the last bullet is missing some details that WhatsUp pointed out.
Other than that, your solution looks good!
Best Answer
Hint: Using the in-and-out principle (aka "inclusion and exclusion"), you can compute the number of injective homomorphisms from a finite group $H$ to a finite group $G$ from the values of $\lvert\operatorname{Hom}(H/N,G)\rvert$ for every normal subgroup $N$ of $H$. Therefore, from your assumption that $\lvert\operatorname{Hom}(H,G_1)\rvert=\lvert\operatorname{Hom}(H,G_2)\rvert$ for every finite group $H$, it follows that every finite $H$ has the same number of injective homomorphisms to $G_1$ as to $G_2$, and in particular, that there is at least one injective homomorphism from $G_1$ to $G_2$ and vice versa, whence it easily follows that $G_1\cong G_2$. This argument applies to lots of other finite structures besides groups. I believe that it's due to László Lovász and that he discovered it as a high school student.
P.S. This has come up several times on Math Stack Exchange and Math Overflow, for example in this answer, which cites L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328.
P.P.S. I will try to present the argument using the in-and-out principle. (I still think this argument must be due to Lovász, even it it's not the one he gives in the work cited above. Unless the argument is wrong, in which case it must be due to me.)
Let $H$ and $G$ be finite groups. Let $H\setminus\{1_H\}=\{h_1,\dots,h_n\}$.
For $i\in[n]=\{1,\dots,n\}$, let $S_i=\{\varphi\in\text{Hom}(H,G):\varphi(h_i)=1_G\}$.
For $I\subseteq[n]$, let $S_I=\bigcap_{i\in I}S_i=\{\varphi\in\text{Hom}(H,G):\forall i\in I\ \varphi(h_i)=1_G\}$ if $I\ne\emptyset$, and $S_\emptyset=\text{Hom}(H,G)$.
Then $|S_I|=|\text{Hom}(H/N_I,G)|$ where $N_I$ is the normal subgroup of $H$ generated by $\{h_i:i\in I\}$. By the in-and-out principle,$$|\text{Mono}(H,G)|=|\text{Hom}(H,G)\setminus\bigcup_{i\in[n]}S_i|=\sum_{I\subseteq[n]}(-1)^{|I|}|S_I|=\sum_{I\subseteq[n]}(-1)^{|I|}|\text{Hom}(H/N_I,G)|.$$Therefore, if $H,G_1,G_2$ are finite groups, and if $|\text{Hom}(H/N,G_1)|=|\text{Hom}(H/N,G_2)|$ for every normal subgroup $N$ of $H$, then $|\text{Mono}(H,G_1)|=|\text{Mono}(H,G_2)|$.
P.P.P.S. This is not true for infinite groups. If $G_1$ and $G_2$ are nonisomorphic groups such that each is isomorphic to a subgroup of the other, then $|\text{Hom}(H,G_1)|=|\text{Hom}(H,G_2)|$ for every (finite or infinite) group $H$, although $G_1\not\cong G_2$.