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$
    – Asinomás
    Commented Aug 2, 2016 at 16:16

4 Answers 4

8
$\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
    Commented Aug 2, 2016 at 16:23
  • 1
    $\begingroup$ @m1cky22: true, but you're appealing to the definition of order of an element, which is usually nonnegative. $\endgroup$ Commented Aug 2, 2016 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$ Commented Aug 2, 2016 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
    Commented Aug 2, 2016 at 16:27
  • 4
    $\begingroup$ @m1cky22 Proofs are all about keeping consistent to definitions. $\endgroup$ Commented Aug 2, 2016 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
    Commented Aug 2, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .