The task: prove that every bijection of a set into itself is representable as a composition of two symmetries (on this set). There is no presumption on finiteness or infinity of the set.   Proof (where I am at now and looking for insights):  1) Writing down the task into math language  Let $f$ be bijection of the set $X$ into itself: $f: X\leftrightarrow X$.  Let $h$ be a symmetry on the set $X$ that means: $h: X\leftrightarrow X$ and $h^{-1} = h$.  Let $g$ be a symmetry on the set $X$ that means: $g: X\leftrightarrow X$ and $g^{-1} = g$.  2) Need to prove that $$\forall f:X\leftrightarrow X \exists (h:X\leftrightarrow X, h^{-1}=h \; and\; g:X\leftrightarrow X, g^{-1}=g):f= g\circ h.$$  3) Proof  Prove that there are $h$ and $g$ so that $f=g\circ h$.  Here is where I am getting into the problem. While   I know that composition of two bijections is bijection. I feel intuitively that every bijection can be represented as a composition of two bijections (by permutation in the middle - not sure that permutation thinking is valid for infinite sets).   I am struggling to get to the proof of that for every bijection $f:X\leftrightarrow X$ among many of the compositions of bijections $X\leftrightarrow X$ that equals $f$ - there are at least one composition that consists of two symmetries.
17202
How can we prove that any bijection on any set is  a composition of 2 involutions ?  Since involutions are bijections mapping elements of a set to elements of the same set, I find it weird that this applies to any bijection.  Thanks for your help !
15770
The following could have shown up as an exercise in a basic Abstract Algebra text, and if anyone can give me a reference, I will be most grateful.  Consider a set $X$ with an associative law of composition, not known to have an identity or inverses. Suppose that for every $g\in X$, there is a unique $x\in X$ with $gxg=g$. Show that $X$ is a group.  Note that I’m not asking for a proof (though a really short one would please me!), just some place where this has been published.
76032
The Problem:  Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions.  (a) Show that if $g \circ f$ is injective, then so is $f$.  (b) If $g \circ f$ is surjective, must $g$ be surjective?  Where I Am:  So, I really have trouble with these, for some reason. I can draw pictures and make sense of the problems, but writing down proofs is very difficult for me.   Basically, for (a), I ended up with some complicated statement involving an implication implying another implication and then tried to derive a contradiction. It just got so convoluted that I couldn't make sense of it anymore, and I know there's a quick, elegant way to show it.  For (b), I know that $g$ need not be surjective. Once again, though, proving it directly from definitions has given me a bit of a headache.  Any help here would be appreciated. Thanks in advance.  The Proofs!  Ok, I did it. Thanks for the help, everyone! Let me know if there's anything wrong with these proofs, or if they could bet any better.  (a) Suppose $f$ is not injective. Then $$ f(x_1)=f(x_2) \implies x_1 \ne x_2 \text{        }(*).$$ Let $f(x_1)=y_0=f(x_2)$ and let $g(y_0)=z_0$. Then $$ (g \circ f)(x_1) = (g \circ f)(x_2) = g(y_0) = z_0. $$ Since $g \circ f$ is injective, $$ (g \circ f)(x_1) = (g \circ f_2) \implies x_1 = x_2. $$ However, this contradicts $(*)$. Therefore, $f$ must be injective.  (b) Suppose $g$ is not surjective. Then  $$ \forall y \in Y, \exists z \in Z \text{ such that } g(y) \ne z \text{         }(**).$$  Since, $g \circ f$ is surjective,  $$ \forall z \in Z, \exists x \in X \text{ such that } g(f(x)) = z \text{       } (***). $$  Let $f(x) = y$. Then,  $$ g(f(x)) = g(y) = z. $$  Because of $(***)$, this is true for all $z \in Z$, which contradicts $(**)$. Therefore, $g$ must be surjective.
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
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.
88526
We have a function $\varphi:G\rightarrow H$ is an isomorphism, show its inverse $\varphi^{-1}:H\rightarrow G$ is also an isomorphism  I am fine with showing it to be a homomorphism and surjective, this is my attempt at showing injectivity, I'm unsure if they would be sufficient  Assume: $\forall h\in H, \exists g\in G$ s.t. $\varphi(g)=h$ and $\forall g_1, g_2\in G, \varphi(g_1)=\varphi(g_2)\Rightarrow g_1=g_2$  Injectivity - Need to show $\varphi^{-1}(g_1)=\varphi^{-1}(g_2)\Rightarrow g_1=g_2$  $\varphi^{-1}(g_1)=\varphi^{-1}(g_2)\Rightarrow g_1=\varphi(\varphi^{-1}(g_2))$ from our surjectivity assumption on $\varphi$ we know there exists such a $\varphi^{-1}(g_2)\in H$ and from our injectivity assumption on $\varphi$ we know that this solution is unique.   [Sufficient? What more could be added? How could I do this clearer?]
109254
What I want to ask is the proof of the Proposition 10. in "Linear Representations of Finite Groups" by Jean-Pierre Serre.   Let $\rho_i : G \rightarrow GL(W_i)$ be the distinct irreducible representations of $G$.$(1 \le i \le h)$ We can extend $\rho_i$ to $\widetilde{\rho_i} : \mathbb{C}[G] \rightarrow \text{End}(W_i)$ by $\widetilde{\rho_i}(\sum_{g \in G} a_g g) = a_g \sum_{g \in G} \rho_i(g)$.   Then $\widetilde{\rho} = (\widetilde{\rho_i}) : \mathbb{C}[G] \rightarrow \prod_{i=1}^{h} \text{End}(W_i) \cong \prod_{i=1}^h M_{n_i}(\mathbb{C})$ is a homomorphism.  Then Proposition 10 states that it is an isomorphism.  Since dimensions of domain and codomain are same, it suffices to show that $\widetilde{\rho}$ is surjective.   In the proof of the book,   If $\widetilde{\rho}$ is not surjective, then there exists a nonzero linear form on $\prod M_{n_i}(\mathbb{C})$ vanishing on the image of $\widetilde{\rho}$. This gives a nontrivial relation on the coefficients of the representations $\rho_i$ which is impossible because of the orthogonality formulas of 2.2.  But I can not follow the above three lines in the proof. I will appreciate it if you give an explanation for the proof.   Thank you.
110608
Sometimes one needs two disjoint copies of a given set $X$. This can be canonically done by taking $\{0\} × X$ and $\{1\} × X$. Sometimes we want to identify one of the copies with the original set $X$. So I wonder, is it possible to take a disjoint copy of $X$ straight ahead? And can this be done canonically? More precisely, are the following claims true? $ \def\dom{\operatorname{dom}} \def\rng{\operatorname{rng}} \def\On{\mathbf{On}} $   For every $X$ there is a one-to-one function $f$ such that $\dom(f) = X$ and $\rng(X) ∩ X = ∅$. There is an explicit formula $φ(X, f)$ such that for every $X$ there is exactly one $f$ satisfying $φ(X, f)$ and this $f$ satisfies 1. for $X$.   Since such construction of a disjoint copy is intuitively trivial, I'm interested in proofs of 1. and 2. without using regularity, choice, or infinity.   Some ideas:   We may simply put $f(x) := (x, X)$, but we need regularity to show that $(x, X) ∉ X$. We may consider $α = \sup(X ∩ \On)$ and pair members of $X$ with some ordinals above $α$, but we need AC to well-order $X$, and we need global choice to obtain 2. Let $&lt;$ be the transitive hull of $∈$. If the relation $&lt;$ is narrow, i.e. $\{y: y &lt; x\}$ is a set for every $x$, then we may choose $z ∉ ⋃\{(\leftarrow, x)_&lt;: x ∈ X\}$ and put $f(x) := (x, z)$ since $(x, z) = y ∈ X$ would imply $z &lt; y$. Note that we don't need the axiom of infinity to define $&lt;$, but I don't know how to prove its narrowness without infinity.
123815
I have some difficulties with a task in algebra. I guess it's trivial and really easy but I can't figure out how to solve it.  I have a set $G$ and a binary operation on it, let it be $\circ$. I have that the operation is associative and that the equations $a\circ x = b$ and $x\circ a = b$ have unique solutions. I have to prove that $(G, \circ)$ is a group.  I already have that the operation is binary and associative, so I have to prove that there is unique identity element and unique inverse element and it will come from the equations, but how exactly?
74509
Wouldn't these two sets have the same cardinality?  If so, I am unsure of how to prove that two sets with the same cardinality have a bijective correspondence.
40530
Consider $f:A \to B$ and $g: B \to C$. If I know that both $f$ and $g$ are injective, then can I state that $$g  \circ f:A \to C$$ is injective?
55191
Here is the problem:  Suppose that $*$ is an associative binary operation on a set $S$. Let  $$H:= \{a \in  S\mid a * x = x * a \mbox{ for all }x\in S\}.$$  In other words, $H$ is consisting of all the elements of $S$ that commute with every element in $S$.  Show that $H$ is closed under $*$.
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$
69010
Suppose $\left(A,\leq_{A}\right)$   and $\left(B,\leq_{B}\right)$   are Posets and $f:A\to B$   is an order preserving bijection. I'm trying to show that $f^{-1}:B\to A$   is also order preserving. That is I want to show that given $b_{1},b_{2}\in B$   $$b_{1}\leq_{B}b_{2}\Longrightarrow f^{-1}\left(b_{1}\right)\leq_{A}f^{-1}\left(b_{2}\right)$$  Since $f$   is bijective there are uniquely defined $a_{1},a_{2}\in A$   such that $$b_{1}=f\left(a_{1}\right)\Longrightarrow a_{1}=f^{-1}\left(b_{1}\right)$$ $$b_{2}=f\left(a_{2}\right)\Longrightarrow a_{2}=f^{-1}\left(b_{2}\right)$$  If $a_{1},a_{2}$   are comparable and I assume $a_{2}\leq_{A}a_{1}$   I get a contradiction since $f$   is order preserving: $$b_{2}=f\left(a_{2}\right)\leq_{B}\, f\left(a_{1}\right)=b_{1}$$  So I deduce that if $a_{1},a_{2}$   are comparable then necessarily the required inequality holds. My question is whether it's possible that $a_{1},a_{2}$   are not comparable and the claim is actually false?
31727
This is from Fraleigh's First Course in Abstract Algebra (page 82, Theorem 8.16) and I keep having hard time understanding its proof. I understand only until they mention the map $\lambda_x (g) = xg$. Can someone explain this proof step by step? Thank you so much! Here is the proof:  Let $G$ be a group. We show that $G$ is isomorphic to a subgroup of $S_G$. Define a one-to-one function $\phi: G \to S_G$ such that $\phi(xy)=\phi(x) \phi(y)$ for all $x,y \in G$. For $x \in G$, let $\lambda_x: G \to G$ be defined by $\lambda_x (g) = xg$ for all $g \in G$. The equation $\lambda_x (x^{-1} c) = x(x^{-1} c) = c$ for all $c \in G$ shows that $\lambda_x$ maps $G$ onto $G$. If $\lambda_x (a) = \lambda_x (b)$, then $xa=xb$ so $a=b$ by cancellation. Thus $\lambda_x$ is also one to one, and is a permutation of $G$. We now define $\phi: G \to S_G$ by defining $\phi(x) = \lambda_x$ for all $x \in G$. To show that $\phi$ is one to one, suppose that $\phi(x) = \phi(y)$. Then $\lambda_x = \lambda_y$ as functions mapping $G$ into $G$. In particular $\lambda_x (e) = \lambda_y (e)$, so $xe=ye$ and $x=y$. Thus $\phi$ is one to one. It only remains to show that $\phi(xy) = \phi(x) \phi(y)$, that is, that $\phi_{xy} = \lambda_x \lambda_y$. Now for any $g \in G$, we have $\lambda_{xy} (g) = (xy)g$. Permutation multiplication is function composition, so $(\lambda_x \lambda_y)(g) = \lambda_x (\lambda_y (g)) = \lambda_x (yg) = x(yg)$. Thus by associativity, $\lambda_{xy} = \lambda_x \lambda_y$.
10929
Which bijections $f:\{1,2,3,\ldots\}\to\{1,2,3,\ldots\}$ have the property that for every sequence $\{a_n\}_{n=1}^\infty$, $$ \lim_{n\to\infty} \sum_{k=1}^n a_k = \lim_{n\to\infty} \sum_{k=1}^n a_{f(k)}, $$ where "$=$" is construed as meaning that if either limit exists then so does the other and in that case then they are equal?  It is clear that there are uncountably many of these.  Might it just be that $\{f(n)/n : n=1,2,3,\ldots\}$ is bounded away from both $0$ and $\infty$?  These bijections form a group.  Can anything of interest be said about them as a group?  PS: Here's another moderately wild guess (the one above appears to be wrong): Might it be just the bijections whose every orbit is finite?
107131
If we set $A$ and $B$. Assuming that there exist an injective map from $A$ to $B$ and an injective map from $B$ to $A$. How to prove that there is a bijection between $A$ and $B$.