6
$\begingroup$

I'm finally attempting to conquer D&F (3rd ed) and I want to build good proof habits and fix mistakes early on. Here is the exercise (Ch. 1 ex. 32) and the following is my proof.

Prove that for $x \in G$, where $G$ is a group and $x$ has finite order $n$, all of $1, x, x^2, \ldots, x^{n-1}$ are distinct and deduce that $|x| \leq |G|$.

Proof. Let $a,b \in [0,n-1]\cap \mathbb{N}$ such that $x^a=x^b$. Then $1 = x^ax^{-a}=x^bx^{-a} = x^{b-a}$. Since $1 \leq a \lt n$ and $1 \leq b \lt n$, $b-a\lt n$. So $x^{b-a}=1 \implies b-a=0$ and $a=b$. Since $a$ and $b$ were arbitrarily chosen, $x^c$ is distinct for all $c \in [0,n-1] \cap \mathbb{N}$. We know $x^c\in G$ for all $c \in [0, n-1]\cap \mathbb{N}$ by definition of group closure, and $|[0,n-1]\cap \mathbb{N}|=n$. So $G$ contains at least $n$ elements, and $|x|\leq |G|$.

Is this a convincing proof? I feel like there might be some circular logic, and perhaps not enough detail. I was thinking of establishing that the elements form a cyclic group, and show this group is a subgroup of $G$. Any tips or comments would be greatly appreciated.

$\endgroup$
1
  • 2
    $\begingroup$ It looks good to me. $\endgroup$
    – Asinomas
    Aug 2 '16 at 16:16
7
$\begingroup$

Almost.

You assert $b-a < n$. I think you want to assume $b \ge a$ (without loss of generality) from the start, to make $b-a$ nonnegative as well. Otherwise you need to handle the case when it's not.

$\endgroup$
6
  • $\begingroup$ isn't $b-a \lt n$ even if $b-a$ is negative? I was thinking about clarifying that but I didn't think it would change anything $\endgroup$
    – m1cky22
    Aug 2 '16 at 16:23
  • $\begingroup$ @m1cky22: true, but you're appealing to the definition of order of an element, which is usually nonnegative. $\endgroup$ Aug 2 '16 at 16:25
  • $\begingroup$ @m1cky22 Yes, it's less than $n$. But when it's less than $0$ you are dealing with a negative power in what follows. That needs work. $\endgroup$ Aug 2 '16 at 16:26
  • $\begingroup$ I see. So it's more about keeping the consistency/logic of the definition of order rather than "the proof breaks if it's negative." Thanks, I think I can finally move on to the next chapter! $\endgroup$
    – m1cky22
    Aug 2 '16 at 16:27
  • 3
    $\begingroup$ @m1cky22 Proofs are all about keeping consistent to definitions. $\endgroup$ Aug 2 '16 at 16:28
3
$\begingroup$

Logically, everything looks good, except for @Ethan's point. If you are worried about circularity, make sure you understand why your statement “$x^{b-a} = 1 \implies b-a =0$” is true.

I think notations like

Let $a,b\in[0,n-1] \cap \mathbb{N}$ such that $x^a = x^b$.

are a bit cumbersome. Personally, I would rewrite the first sentence as

Let $a$ and $b$ be integers such that $0 \leq a \leq b \leq n-1$ and $x^a = a^b$.

Or perhaps even

Suppose $x^a = x^b$ for some integers $a$ and $b$ with $0 \leq a\leq b\leq n-1$.

In essence, you want to show $x^a = x^b \implies a=b$, so writing the first sentence that way aligns the paragraph with that logical statement.

Having a higher density of symbols does not make a more mathematically sophisticated argument.

$\endgroup$
2
$\begingroup$

Your proof is perfectly fine. Good Job!

One remark: One prof of me uses the following convention: $[0:n] := [0, n] \cap \mathbb N$.

This is an elegant way to write such "discrete intervals" and makes proofs more readable. Just an idea of me. Maybe you want to use it :)

$\endgroup$
1
  • $\begingroup$ I was looking for better notation and didn't know what people use! I didn't want to write $1 \leq a \lt n$ so I chose my route, but yours is definitely better. Thanks! $\endgroup$
    – m1cky22
    Aug 2 '16 at 16:24
1
$\begingroup$

I got confused when you brought $c$ into the mix.

Here is your proof with a lot of the argument removed. I don't think I have removed too much and it may be easier to follow.

Suppose the powers of $x$ are not all distinct.

Then there exist $a,b \in [0,n-1]\cap \mathbb{N}$ such that $b>a$ and $x^b=x^a$.

This implies that $0\lt b-a<n$, and $1=x^ax^{-a}=x^bx^{-a} = x^{b-a}$.

Since the order of $x$ is $n$, $x^{b-a}=1$ implies $n\, |\, b-a$.

This is a contradiction, since no number greater than $0$ and less than $n$ can be divisible by $n$.

So the original supposition, that the powers of $x$ are not all distinct, leads to a contradiction and must therefore be false.

$\endgroup$

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.