8
$\begingroup$

This is my first attempt at a formally written proof so I would appreciate any pointers as far as proof-writing technique or the validity of the actual proof itself.

Note: I have not formally taken abstract algebra or a proof-writing course so I am sure that I am lacking in many proof-writing aspects, so I would really love a lot of constructive criticism both on the actual proof itself, and the way I wrote the proof. I also go into greater detail than might be appropriate for this type of proof because I am shaky on a lot of the math foundations so I figure that any imperfections in my knowledge will be more easily seen with a more explicit construction of this proof. Thank you all in advance.

Let $G$ be a finite group, and let $S$ be a nonempty subset of $G$. Suppose $S$ is closed with respect to multiplication. Prove that $S$ is a subgroup of $G$. (HINT: It remains to prove that $S$ contains $e$ and is closed with respect to inverses. Let $S$ = {$a_1$ ... $a_n$}. If $a_i$ $∈$ $S$, consider the distinct elements $a_ia_1$, $a_ia_2$, $...$ $a_ia_n$

Proof:

First we will define a function $A_1 : S \rightarrow S$ that maps $s \mapsto a_1s$. This function is injective because $$a_1y = a_1x$$ $$a^{-1}_1a_1y = a^{-1}_1a_1x$$ $$y = x$$

The function is then surjective because $A_1(S) \subseteq S$ and since $A_1$ is injective, it contains $|S|$ elements. Therefore $A_1$ maps onto every element in $S$ and is therefore surjective as well.

This means that $a_1$ is in the image of $A_1$. Therefore $$A_1(a_1) = a_1$$ $$a_1s = a_1$$ $$s = e$$

Since $S$ is closed under multiplication, $e \in S$.

Next, we will define a function $A_2 : S \rightarrow S$ that maps $s \mapsto a^2_1s$. This function is also injective $$a^2_1x = a^2_1y$$ $$x = y$$

It follows that this function is also surjective since it too is injective and contains |S| elements.

This means that $a_1$ is in the image of $A_2$ as well. Therefore $$A_2(z) = a_1$$ $$a^2_1z = a_1$$ $$z = a^{-1}_1$$

Since $S$ is closed under multiplication $a^{-1}_1 \in S$.

Therefore $e, a^{-1}_1 \in S$ so $S$ is a subgroup of $G$.

Please tear this apart! Thanks in advance.

$\endgroup$
  • $\begingroup$ Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. $\endgroup$ – Shaun Feb 23 at 22:45
3
$\begingroup$

You don't need to use the second map $A_2$. Once you know that $e \in S$, you know by the first part of your proof that $A_1$ is surjective, so for some $s \in S, a_1s=e$. Then $s=a^{-1}$.

Another way to prove this result, by the way, is to just take all possible powers of $a_1$, which all are contained within $S$ because $S$ is multiplicatively closed. They have to repeat at some point because $S$ is finite. If $a^m=a^{m+k}=a^ma^k$, then $a^k=e \in S$, and $aa^{k-1}=a^k=e \Rightarrow a^{k-1}=a^{-1} \in S$.

As for proof-writing, one small nit. I don't think the line $A_1(a_1) = a_1$ conveys your intended meaning. I think you mean to say $a_1 \in A_1(S)$.

$\endgroup$
  • $\begingroup$ Wow, I didn't realize that I could just reuse $A_1$ like that again, thanks for the heads up. You're also correct about $A_1(a_1) = a_1$ not conveying the meaning I thought it did, thanks for that too. As far as the other proof, I've seen it quite a bit but I still have a hard time getting an intuitive understanding for the fact that the sequence must repeat at some point. I guess I somewhat understand it, but I'm trying to find a more 'geometric' (I guess?) understanding of what it even means to have the sequence repeat. Does that mean its cyclic? Why does it necessarily even need to repeat? $\endgroup$ – ForIgreaterthanJ Feb 23 at 15:47
  • $\begingroup$ The pigeonhole principle forces it to repeat. You’re cramming an infinite sequence ($\{a^n\}$) into a finite set of boxes (the elements of $S$), so at least two members of that sequence have to fall within the same box; i.e., they must be the same element of $S$. And yes, the sequence does cycle. $\endgroup$ – Robert Shore Feb 23 at 16:28
2
$\begingroup$

The proof presented here by our OP ForIgreaterthan_I appears to be logically valid; indeed, I like it because it is clever and innovative.

The way I would approach this, which alas is standard and not in fact overly clever, being as it is indeed rather obvious and straightforward, is as follows:

Let

$s \in S; \tag 1$

consider the powers

$s^i \in S; \tag 2$

since

$S \subset G \tag 3$

and

$\vert G \vert < \infty, \tag 4$

we have

$\vert S \vert < \infty \tag 5$

as well; thus the sequence

$s, s^2, s^3, \ldots, s^i, s^{i + 1}, \ldots \tag 6$

must repeat itself at some point; that is,

$\exists k, l \in \Bbb N, \; l \ge k + 1, \tag 7$

with

$s^l = s^k; \tag 8$

then

$s^{l - k} = e; \tag 9$

thus

$e = s^{l - k} \in S; \tag{10}$

it follows then that

$s^{l - k - 1}s = e \tag{11}$

and clearly

$s^{l - k - 1} \in S; \tag{12}$

thus the group identity $e \in S$, and every $s \in S$ has an inverse in $S$; $S$ is thus a subgroup of $G$.

$\endgroup$
  • $\begingroup$ Thanks for the contribution! I've seen this proof that you've posted quite a bit, but I always have a hard time wrapping my head around why the sequence must repeat. I'm not even sure I have a well-defined idea of what 'repeating' means in this context. Does that mean the sequence is cyclic? Or that one value just repeats forever? In that case doesn't that mean the sequence is infinite? I apologize for the ill-defined questions but I for some reason am just having a hard time pinning down what one really means when they say the sequence repeats. Regardless, thank you for that clean proof! $\endgroup$ – ForIgreaterthanJ Feb 23 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.