Category Archives: Mathematics

Proof: characterisation of Jordan measurability

18/06/2017An introduction to measure theory, Books, Mathematics, Measure theory, SolutionsElementary measure, Jordan measure, Measure, Proofscidom

The following proof is a solution to exercise 1.1.5 of the book “An introduction to measure theory” by Terence Tao.

Some notation will be established before proceeding with the exercise. Let $\mathcal{E}(\mathbb{R}^d)$ be the set of elementary sets on $\mathbb{R}^d$ . Denote by $\mathcal{L}(E):=\left\{m(A):A\in\mathcal{E}(\mathbb{R}^d),A\subseteq E\right\}$ and by $\mathcal{U}(E):=\left\{m(B):B\in\mathcal{E}(\mathbb{R}^d),E\subseteq B\right\}$ the sets of elementary measures of all elementary subsets and supersets of a bounded set $E\subseteq\mathbb{R}^d$ , respectively. Let $m_{*}(E)=\sup{\mathcal{L}(E)}$ and $m^{*}(E)=\inf{\mathcal{U}(E)}$ be the Jordan inner and Jordan outer measures of $E$ , respectively.

Exercise 1.1.5 requires to prove the equivalence of the following three statements, as a way of characterising Jordan measurability:

$E$ is Jordan measurable, which means that $m_{*}(E)=m^{*}(E)$ .
For every $\epsilon>0$ there exist elementary sets $A\subseteq E\subseteq B$ such that $m(B\setminus A)\le\epsilon$ .
For every $\epsilon>0$ there exists an elementary set $A$ such that $m^{*}(A\triangle E)\le\epsilon$ .

It suffices to prove that $[1]\Rightarrow [2]\Rightarrow [3]\Rightarrow [1]$ . To provide further practice and familiarity with Jordan inner and outer measures, it will be additionally shown how to prove $[1]\Rightarrow [3]\Rightarrow [2]\Rightarrow [1]$ .

$\boxed{[1]\Rightarrow [2]}$

A reductio ad absurdum argument will be used. Assume that there exists $\epsilon_0>0$ such that for all elementary sets $A,B\in\mathcal{E}(\mathbb{R}^d)$ with $A\subseteq E\subseteq B$ the inequality $m(B\setminus A)>\epsilon_0$ holds.

Considering the set equality $B=A\cup (B\setminus A)$ , it follows from $A\subseteq B$ that $m(B\setminus A)=m(B)-m(A)$ . Hence, $m(B\setminus A)=m(B)-m(A)>\epsilon_0$ .

So, $m(A)+\epsilon_0\le m^{*}(E)$ , since $m(A)+\epsilon$ is a lower bound of $\mathcal{U}(E)$ and $m^{*}(E)=\inf{\mathcal{U}(E)}$ . In turn, $m^{*}(E)-\epsilon_0$ is an upper bound of $\mathcal{L}(E)$ and $m_{*}(E)=\sup{\mathcal{L}(E)}$ , therefore $m_{*}(E)\le m^{*}(E)-\epsilon_0$ .

Thus, $m_{*}(E)<m^{*}(E)$ , which contradicts the assumption $m_{*}(E)=m^{*}(E)$ .

$\boxed{[2]\Rightarrow [3]}$

Assume that there exists $\epsilon_0>0$ such that $\forall C\in\mathcal{E}(\mathbb{R}^d)$ holds $m^{*}(C\triangle E)>\epsilon_0$ .

According to the assumed statement [2], for $\epsilon=\epsilon_0$ , $\exists A, B\in\mathcal{E}(\mathbb{R}^d)$ with $A\subseteq E\subseteq B$ such that $m(B\setminus A)\le\epsilon_0$ .

Pick $C=B$ , so $m^{*}(B\triangle E)=m^{*}(C\triangle E)>\epsilon_0$ . It follows from $E\subseteq B$ and $B\triangle E=(B\setminus E)\cup(E\setminus B)$ that $B\triangle E=B\setminus E$ , so $m^{*}(B\setminus E)=m^{*}(B\triangle E)>\epsilon_0$ .

$B\setminus E\subseteq B\setminus A$ , since $A\subseteq E$ . By also taking into account that $B\setminus A$ is elementary and the inequality $m(B\setminus A)\le\epsilon_0$ , the conclusion is $m^{*}(B\setminus E)\le m(B\setminus A)\le\epsilon_0$ .

A contradiction has been reached, as it has been deduced $m^{*}(B\setminus E)>\epsilon_0$ and $m^{*}(B\setminus E)\le\epsilon_0$ on the basis of the negation of statement [3].

$\boxed{[3]\Rightarrow [1]}$

Before proceeding with the proof of $[3]\Rightarrow [1]$ , four lemmas will be proved.

Lemma 1

The Jordan inner measure $m_{*}(E)$ of any bounded set $E\subseteq\mathbb{R}^d$ is less than or equal to its Jordan outer measure $m^{*}(E)$ , i.e. $m_{*}(E)\le m^{*}(E)$ .

Proof of lemma 1

For any elementary sets $A,B$ with $A\subseteq E\subseteq B$ , the set relation $A\subseteq B$ yields $m(A)\le m(B)$ . This means that any $m(A)\in\mathcal{L}(E)$ is a lower bound of $\mathcal{U}(E)$ , therefore $m(A)\le m^{*}(E)$ . Since the last inequality holds for any $m(A)\in\mathcal{L}(E)$ , it follows that $m^{*}(E)$ is an upper bound of $\mathcal{L}(E)$ , thus $m_{*}(E)\le m^{*}(E)$ .

Lemma 2

The elementary and Jordan measures of any elementary set $X$ coincide, that is $m_{*}(X)=m^{*}(X)=m(X)$ .

Proof of lemma 2

It suffices to notice that $X\subseteq X$ , whence $m^{*}(X)\le m(X)$ and $m(X)\le m_{*}(X)$ , thereby $m^{*}(X)\le m_{*}(X)$ . It is also known from lemma 1 that $m_{*}(X)\le m^{*}(X)$ , so $m_{*}(X)=m^{*}(X)$ . Finally, $m^{*}(X)\le m(X)$ , $m(X)\le m_{*}(X)$ and $m_{*}(X)=m^{*}(X)$ yield $m(X)=m_{*}(X)=m^{*}(X)$ .

Lemma 3

Let $E\subseteq\mathbb{R}^d$ be a bounded set and $B\in\mathcal{E}(\mathbb{R}^d)$ with $E\subseteq B$ . It then holds that $m(B)-m_{*}(E)\le m^{*}(B\setminus E)$ .

Proof of lemma 3

Recall that for a set $X\subseteq\mathbb{R}$ the following equivalences hold:

$\ell=\inf{X}\Leftrightarrow(\forall\epsilon>0)(\exists x\in X)x<\ell+\epsilon$ .
$u=\sup{X}\Leftrightarrow(\forall\epsilon>0)(\exists x\in X)u-\epsilon < x$ .

According to the former equivalence, for any $\epsilon>0$ there exists an elementary set $B\setminus E\subseteq C$ such that

$m(C)<m^{*}(B\setminus E)+\epsilon /2\ \ \ \ (1)$ .

By using the latter equivalence, there exists an elementary set $A\subseteq B$ such that

$m_{*}(B)-\epsilon /2<m(A)\ \ \ \ (2)$ .

It follows from lemma 2 and inequality (2) that $m(B)-m_{*}(E)<m(A)-m_{*}(E)+\epsilon /2$ . $B\setminus E\subseteq C$ and $A\subseteq B$ lead to $A\setminus C\subseteq E$ , so $m(A\setminus C)\le m_{*}(E)$ , which in turn gives

$m(B)-m_{*}(E)<m(A)-m(A\setminus C)+\epsilon /2\ \ \ \ (3)$ .

Inequality (3) connects the statement of lemma 3 to an analogous simpler statement for elementary sets; in particular, it will be shown that

$m(A)-m(C)\le m(A\setminus C)\ \ \ \ (4)$ .

Indeed, $(A\setminus C)\cup (A\cap C)=A$ , so $m(A)-m(A\cap C)=m(A\setminus C)$ . Moreover, $A\cap C\subseteq C$ , which means $m(A\cap C)\le m(C)$ , therefore $m(A)-m(C)\le m(A)-m(A\cap C)$ . Inequality (4) has thus been reached.

(3) and (4) yield $m(B)-m_{*}(E)<m(C)+\epsilon/2$ , which is combined with (1) to give

$m(B)-m_{*}(E)<m^{*}(B\setminus E)+\epsilon\ \ \ \ (5)$ .

For two reals $x, y$ , if $(\forall\epsilon>0) x\le y+\epsilon$ , then $x\le y$ . This can be shown by assuming $x>y$ , whence $0<x-y\le\epsilon\Rightarrow x=y$ , contradiction. As inequality (5) holds for any $\epsilon>0$ , the conclusion $m(B)-m_{*}(E)\le m^{*}(B\setminus E)$ follows.

Lemma 4

The Jordan outer measure of the union of two bounded sets $X\subseteq\mathbb{R}^d$ and $Y\subseteq\mathbb{R}^d$ is less than or equal to the sum of the Jordan outer measures of the two sets, i.e. $m^{*}(X\cup Y)\le m^{*}(X)+m^{*}(Y)$ .

Proof of lemma 4

Let $V\subseteq\mathbb{R}^d,W\subseteq\mathbb{R}^d$ be elementary sets with $X\subseteq V,Y\subseteq W$ .

Start by noticing the set equality $V\cup W=V\cup(W\setminus V)$ . So, $m(V\cup W)=m(V)+m(W\setminus V)$ . Moreover, $W\setminus V\subseteq W$ implies that $m(W\setminus V)\le m(W)$ . Thus,

$m(V\cup W)\le m(V)+m(W)\ \ \ \ (6)$ .

Inequality (6) holds for elementary sets, thereby it is a special case of lemma 4.

$m^{*}(X\cup Y)\le m(V\cup W)$ , since $X\cup Y \subseteq V\cup W$ . By taking into account inequality (6), $m^{*}(X\cup Y)\le m(V)+m(W)$ . So, $m^{*}(X\cup Y)-m(V)$ is a lower bound of $\mathcal{U}(Y)$ and $m^{*}(X\cup Y)-m(V)\le m^{*}(Y)$ . Furthermore, $m^{*}(X\cup Y)-m^{*}(Y)$ is a lower bound of $\mathcal{U}(X)$ , so $m^{*}(X\cup Y)-m^{*}(Y)\le m^{*}(X)$ , quod erat demonstrandum.

Proof of $\boldsymbol{[3]\Rightarrow [1]}$ using the lemmas

The main idea of the proof of $\boldsymbol{[3]\Rightarrow [1]}$ is to show that for any $\epsilon>0$ the inequality $m^{*}(E)-m_{*}(E)\le \epsilon$ holds.

It is known from statement [3] that for any $(\epsilon>0)(\exists X\in\mathcal{E}(\mathbb{R}^d))$ such that

$m^{*}(X\triangle E)\le\epsilon/3\ \ \ \ (7)$ .

Using the relevant property of infimum, for any $\epsilon>0$ there exists an elementary superset $E\setminus X\subseteq Y$ of $E\setminus X$ such that

$m(Y)<m^{*}(E\setminus X)+\epsilon/3\ \ \ \ (8)$ .

Introduce the set $B:=X\cup Y$ . Obviously $B$ is an elementary set and $E\subseteq B$ , so $m^{*}(E)\le m(B)$ . It thus follows from lemma 3 that

$m^{*}(E)-m_{*}(E)\le m^{*}(B\setminus E)\ \ \ \ (9)$ .

$B\setminus E=(X\cup Y)\setminus E=(X\setminus E)\cup (Y\setminus E)$ , so by lemma 4

$m^{*}(B\setminus E)\le m^{*}(X\setminus E)+m^{*}(Y\setminus E)\ \ \ \ (10)$ .

$X\setminus E\subseteq X\triangle E\Rightarrow \mathcal{U}(X\triangle E)\subseteq\mathcal{U}(X\setminus E)$ , so $m^{*}(X\setminus E)=\inf{\mathcal{U}(X\setminus E)}\le \inf{\mathcal{U}(X\triangle E)}=m^{*}(X\triangle E)$ . Consequently, inequality (10) gives

$m^{*}(B\setminus E)\le m^{*}(X\triangle E)+m^{*}(Y\setminus E)\ \ \ \ (11)$ .

In a similar way, $E\setminus X\subseteq X\triangle E$ implies

$m^{*}(E\setminus X)\le m^{*}(X\triangle E)\ \ \ \ (12)$ .

Finally, $Y\setminus E\subseteq Y$ means that

$m^{*}(Y\setminus E)\le m(Y)\ \ \ \ (13)$ .

All the components of the proof have been established. More concretely, inequalities (9), (11), (7), (13), (8) and (12) produce $m^{*}(E)-m_{*}(E)\le \epsilon$ for any $\epsilon>0$ , so $m_{*}(E)=m^{*}(E)$ .

$\boxed{[1]\Rightarrow [3]}$

Assume that $(\exists\epsilon_0>0)(\forall X\in\mathcal{E}(\mathbb{R}^d))m^{*}(X\triangle E)>\epsilon_0$ .

As $m^{*}(E)=\inf{\mathcal{U}(E)}$ , it is deduced that there exists an elementary set $E\subseteq B$ such that

$m(B)<m^{*}(E)+\epsilon_0/2\ \ \ \ (14)$ .

Since $m_{*}(E)=\sup{\mathcal{L}(E)}$ , there exists an elementary set $A\subseteq E$ such that

$m_{*}(E)-\epsilon_0/2<m(A)\ \ \ \ (15)$ .

$A\subseteq E\subseteq B\Rightarrow E\setminus A\subseteq B\setminus A$ , so $m^{*}(E\setminus A)\le m(B\setminus A)$ . Moreover, $A\subseteq B$ means $m(B\setminus A)=m(B)-m(A)$ , hence

$m_{*}(E\setminus A)\le m(B)-m(A)\ \ \ \ (16)$ .

Combining (14), (15) and (16) gives $m_{*}(E\setminus A)<m^{*}(E)-m_{*}(E)+\epsilon_0$ . By the assumed statement [1], $m_{*}(E)=m^{*}(E)$ , thus $m_{*}(E\setminus A)<\epsilon_0$ . This is a contradiction, as the assumed negation of statement [3] gives $m_{*}(A\triangle E)=m_{*}(E\setminus A)>\epsilon_0$ for $A\subseteq E$ .

$\boxed{[3]\Rightarrow [2]}$

The proof of $[3]\Rightarrow [2]$ is similar in spirit to the proof of $[3]\Rightarrow [1]$ . It will be shown that for any $\epsilon >0$ there exist $A,B\in\mathcal{E}(\mathbb{R}^d)$ with $A\subseteq E\subseteq B$ such that $m(B\setminus A)\le \epsilon$ .

It is known from statement [3] that for any $(\epsilon>0)(\exists X\in\mathcal{E}(\mathbb{R}^d))$ such that

$m^{*}(X\triangle E)\le\epsilon/4\ \ \ \ (17)$ .

According to the relevant property of infimum, for any $\epsilon>0$ there exists an elementary set $Y$ with $E\setminus X\subseteq Y$ such that

$m(Y)<m^{*}(E\setminus X)+\epsilon/4\ \ \ \ (18)$ .

Consider the set $B:=X\cup Y$ , which is an elementary set and $E\subseteq B$ , so $m^{*}(E)\le m(B)$ . By application of lemma 3,

$m(B)-m_{*}(E)\le m^{*}(B\setminus E)\ \ \ \ (19)$ .

It is noted that $B\setminus E=(X\cup Y)\setminus E=(X\setminus E)\cup (Y\setminus E)$ , so by lemma 4

$m^{*}(B\setminus E)\le m^{*}(X\setminus E)+m^{*}(Y\setminus E)\ \ \ \ (20)$ .

$X\setminus E\subseteq X\triangle E$ , so $m^{*}(X\setminus E)\le m^{*}(X\triangle E)$ . Thus, inequality (20) leads to

$m^{*}(B\setminus E)\le m^{*}(X\triangle E)+m^{*}(Y\setminus E)\ \ \ \ (21)$ .

Similarly, $E\setminus X\subseteq X\triangle E$ implies

$m^{*}(E\setminus X)\le m^{*}(X\triangle E)\ \ \ \ (22)$ .

Moreover, $Y\setminus E\subseteq Y$ gives

$m^{*}(Y\setminus E)\le m(Y)\ \ \ \ (23)$ .

Finally, there exists an elementary set $A$ with $A\subseteq E$ such that

$m_{*}(E)-\epsilon /4<m(A) \ \ \ \ (24)$ .

Inequalities (19), (21), (17), (23), (18) and (22) produce

$m(B)-m_{*}(E)\le 3\epsilon /4 \ \ \ \ (25)$ .

Combining inequalities (24) and (25) confirms that for any $\epsilon > 0$ there exist elementary sets $A,B$ with $A\subseteq E\subseteq B$ such that $m(B)-m(A)\le \epsilon$ , which completes the proof of $[3]\Rightarrow [2]$ .

$\boxed{[2]\Rightarrow [1]}$

It is known from lemma 1 that $m_{*}(E)\le m^{*}(E)$ . Assume the negation of statement [1], that is assume $m_{*}(E)\neq m^{*}(E)$ . So, $m_{*}(E)< m^{*}(E)$ .

Set $\epsilon_0=(m^{*}(E)-m_{*}(E))/2>0$ . From the assumed statement [2], it is known that there exist $A,B\in\mathcal{E}(\mathbb{R}^d)$ with $A\subseteq E\subseteq B$ such that

$m(B\setminus A)=m(B)-m(A)\le \epsilon_0=(m^{*}(E)-m_{*}(E))/2 \ \ \ \ (26)$ .

Note that $A\subseteq E\Rightarrow m(A)\le m_{*}(E)$ and $E\subseteq B\Rightarrow m^{*}(E)\le m(B)$ , which leads to

$m^{*}(E)-m_{*}(E)\le m(B)-m(A) \ \ \ \ (27)$ .

It follows from equation (26) that $2(m(B)-m(A))\le m^{*}(E)-m_{*}(E)$ , which is combined with equation (27) to give $2(m(B)-m(A))\le m(B)-m(A)$ , and finally $m(B)-m(A)\le 0$ . Moreover, equation (27) yields $0 < 2\epsilon_0=m^{*}(E)-m_{*}(E)\le m(B)-m(A)$ , i.e. $m(B)-m(A)>0$ . Thus, a contradiction has been reached.

Proof: uniqueness of elementary measure

29/05/2017An introduction to measure theory, Books, Mathematics, Measure theory, SolutionsElementary measure, Measure, Proofscidom

The following proof is a solution to exercise 1.1.3 of the book “An introduction to measure theory” by Terence Tao.

A box $B\in\mathbb{R}^d$ , $d\in\mathbb{N}$ , is a Cartesian product $B:={\sf X}_{i=1}^d I_i$ , where each interval $I_i$ is $I_i=(a, b)$ or $I_i=(a, b]$ or $I_i=[a, b)$ or $I_i=[a, b]$ for $a,b\in\mathbb{R}$ with $a\le b$ . An elementary set $E=\cup_{i=1}^n B_i\subseteq\mathbb{R}^d$ is a finite union of disjoint boxes $B_i\in\mathbb{R}^d$ . Let $\mathcal{E}(\mathbb{R}^d)$ denote the collection of elementary sets in $\mathbb{R}^d$ . The measure $m:\mathcal{E}(\mathbb{R}^d)\rightarrow R^{+}\cup\left\{0\right\}$ is defined as $m(E)=\displaystyle\lim_{N\rightarrow\infty}\frac{1}{N^d}\#\left(E\cap\frac{1}{N}\mathbb{Z}^d\right)$ , where $\#(\cdot)$ denotes set cardinality and $\displaystyle\frac{1}{N}\mathbb{Z}^d:=\left\{\frac{\mathbf{z}}{N}:\mathbf{z}\in\mathbb{Z}^d\right\}$ .

Let $m^{'}:\mathcal{E}(\mathbb{R}^d)\rightarrow R^{+}\cup\left\{0\right\}$ be a function satisfying the non-negativity ( $m^{'}(E)\ge 0$ for any elementary set $E$ ), finite additivity ( $m^{'}(\displaystyle\cup_{i=1}^n E_i)\le \sum_{i=1}^{n}m^{'}(E_i)$ for disjoint elementary sets $E_i$ ) and translation invariance ( $m^{'}(E+\mathbf{x})=m^{'}(E)$ for any elementary set $E$ and any $\mathbf{x} \in \mathbb{R}^d$ ) properties.

It will be shown that there exists a positive constant $c\in\mathbb{R}^+$ such that $m^{'}=cm$ , i.e. the functions $m^{'}$ and $m$ are equal up to a positive normalization constant $c$ .

Observe that $\left[0,1\right)=\displaystyle\cup_{i=0}^{n-1}\left[\frac{i}{n},\frac{i+1}{n}\right)$ . Due to translation invariance, $m^{'}\left(\displaystyle\left[\frac{i}{n},\frac{i+1}{n}\right)\right)=m^{'}\left(\displaystyle\left[\frac{i}{n},\frac{i+1}{n}\right)-\frac{i}{n}\right)=m^{'}\left(\left[0,\frac{1}{n}\right)\right)$ . Using finite additivity, it follows that $m^{'}\left(\left[0,1\right)^d\right)=n^dm^{'}\left(\left[0,\frac{1}{n}\right)^d\right)$ . So, $m^{'}\left(\left[0,\frac{1}{n}\right)^d\right)=\displaystyle\frac{c}{n^d}$ for $c:=m^{'}\left(\left[0,1\right)^d\right)$ . Since $m\left(\left[0,\frac{1}{n}\right)^d\right)=\displaystyle\frac{1}{n^d}$ , it follows that $m^{'}\left(\left[0,\frac{1}{n}\right)^d\right)=c m\left(\left[0,\frac{1}{n}\right)^d\right)$ .

This result generalizes to intervals $\left[0,q\right)$ for any rational $q=\displaystyle\frac{s}{n}$ with $s\in\mathbb{N}$ and $n\in\mathbb{N}$ . Since $\left[0,q\right)=\displaystyle\cup_{i=0}^{s-1}\left[\frac{i}{n},\frac{i+1}{n}\right)$ , finite additivity and translation invariance lead to $m^{'}\left(\left[0,q\right)^d\right)=c m\left(\left[0,q\right)^d\right)=cq^d$ .

It will be shown that the result holds also for intervals $\left[0,p\right)$ for any irrational $p\in\mathbb{P}$ .

The set of rationals is dense, which means that $(\forall \epsilon>0)(\forall x\in\mathbb{R})(\exists q\in\mathbb{Q})|x-q|<\epsilon$ . For some irrational $x=p$ and for each $n\in\mathbb{N}$ , set $\epsilon=\displaystyle\frac{1}{n}$ , so $(\forall n\in\mathbb{N})(\exists q_n\in\mathbb{Q})|p-q_n|<\displaystyle\frac{1}{n}$ . Pick some $n_0\in\mathbb{N}$ with $n_0>\displaystyle\frac{2}{p}$ . For all $n\in\mathbb{N}$ with $n>n_0$ , it holds that $\displaystyle \frac{2}{n}<\frac{2}{n_0}<p$ , whence $0<\displaystyle\frac{1}{n}<p-\frac{1}{n}<q_n$ . So, $(\exists n_0\in\mathbb{N})(\forall n\in\mathbb{N})$ with $n>n_0$ , it is true that $0<q_n-\displaystyle\frac{1}{n}<p<q_n+\frac{1}{n}$ and consequently $\left[0,q_n-\displaystyle\frac{1}{n}\right)^d\subseteq\left[0,p\right)^d\subseteq\left[0,q_n+\displaystyle\frac{1}{n}\right)^d$ .

For any two elementary sets $E\subseteq F$ , it can be shown that $m^{'}(E)\le m^{'}(F)$ via the equality $F=E\cup(F\setminus E)$ , non-negativity and finite additivity. Hence, $m^{'}\left(\left[0,q_n-\displaystyle\frac{1}{n}\right)^d\right)\le m^{'}\left(\left[0,p\right)^d\right)\le m^{'}\left(\left[0,q_n+\displaystyle\frac{1}{n}\right)^d\right)$ .

Since $q_n\pm\displaystyle\frac{1}{n}$ are rationals, it is deduced that $m^{'}\left(\left[0,q_n\pm\displaystyle\frac{1}{n}\right)^d\right)=c\left(q_n\pm\displaystyle\frac{1}{n}\right)^d$ . Thus, $c\left(q_n-\displaystyle\frac{1}{n}\right)^d\le m^{'}\left(\left[0,p\right)^d\right)\le c\left(q_n+\displaystyle\frac{1}{n}\right)^d$ .

$0<q_n-\displaystyle\frac{1}{n}<p<q_n+\frac{1}{n}$ gives $0<p-\displaystyle\frac{1}{n}<q_n<p+\frac{1}{n}$ , hence the sandwich theorem yields $\displaystyle\lim_{n\rightarrow\infty}q_n=p$ .

Combining $c\left(q_n-\displaystyle\frac{1}{n}\right)^d\le m^{'}\left(\left[0,p\right)^d\right)\le c\left(q_n+\displaystyle\frac{1}{n}\right)^d$ and $\displaystyle\lim_{n\rightarrow\infty}q_n=p$ gives $cp^d\le m^{'}\left(\left[0,p\right)^d\right)\le cp^d$ , so $m^{'}\left(\left[0,p\right)^d\right)=cp^d$ for any irrational $p$ .

This effectively completes the proof. There remains to show that $m^{'}=cm$ is true for Cartesian products of unequal intervals $\left[0,x_i\right)$ in each coordinate $i=1,2,\dots,d$ , for any $x_i\in\mathbb{R}$ , and for any subinterval of the real line. These are all trivial given the existing foundations.

Proof: the symmetry group of a complete graph is vertex transitive

15/02/2017Books, Geometric group theory, Graph theory, Groups, graphs and trees, MathematicsGraph, Proof, Symmetry groupscidom

The following self-contained post relates to definition 1.17, p. 11, of the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier.

Let $K_n$ be a complete graph and $\mbox{Sym}(K_n)$ its symmetry group. It will be shown that $K_n$ is vertex transitive, i.e. that for any two vertices $v_i\in K_n$ and $v_j\in K_n$ there exists a symmetry $a\in\mbox{Sym}(K_n)$ such that $a(v_i)=v_j$ .

The proof is constructive. Given any two vertices $v_i\in K_n$ and $v_j\in K_n$ , it suffices to provide a symmetry $a_{ij}:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)\in\mbox{Sym}(K_n)$ such that $a_{ij}(v_i)=v_j$ . Although the suggested symmetry is different for every $v_i$ and $v_j$ , the simpler notation $a$ is preferred in place of $a_{ij}$ .

Given $v_i\in K_n$ and $v_j\in K_n$ , a suitable symmetry can be constructed by swapping $v_i$ with $v_j$ , by redirecting all edges with one end in $v_i$ to edges with one end in $v_j$ and vice versa, and by leaving all other vertices and edges intact.

To formalize the construction, given $v_i\in K_n$ and $v_j\in K_n$ , the symmetry $a$ is set to satisfy the following seven properties:

$a(v_i)=v_j$ ,
$a(v_j)=v_i$ ,
$a(v_k)=v_k$ for all vertices $v_k$ other than $v_i,~v_j$ ,
$a(e_{ij})=e_{ij}$ , where $e_{ij}$ denotes the edge connecting $v_i$ with $v_j$ ,
$a(e_{ik})=e_{jk}$ for all $k$ other than $i,~j$ , where $e_{ik}$ denotes the edge connecting $v_i$ with $v_k$ and $e_{jk}$ the edge connecting $v_j$ with $v_k$ ,
$a(e_{jk})=e_{ik}$ for all $k$ other than $i,~j$ , and
$a(e_{kl})=e_{kl}$ for all $k,~l$ other than $i,~j$ , where $e_{kl}$ denotes the edge connecting $v_k$ with $v_l$ .

Note that all edges exist in the above construction since $K_n$ is complete, so the symmetry is well-defined.

It is easy to check that the proposed symmetry maps vertices to vertices, edges to edges, and preserves the connectivity of $\Gamma$ according to the definition of symmetry provided in this blog post. For instance, $\mbox{ends}(e_{ik})=\{v_i,v_k\}$ , $a(e_{ik})=e_{jk}$ , $a(v_i)=v_j$ and $a(v_k)=v_k$ yield $\mbox{ends}(a(e_{ik}))=\mbox{ends}(e_{jk})=\{v_j,v_k\}=\{a(v_i),a(v_k)\}$ , which is an edge in $K_n$ .

Clarifying the concept of symmetry group of a graph

11/02/2017Books, Geometric group theory, Graph theory, Groups, graphs and trees, MathematicsGraph, Symmetry groupscidom

The following self-contained post clarifies the definition of symmetry group of a graph (definition 1.14, p. 10-11, and example 1.15, p. 11, in the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier).

The symmetry group of a graph, also referred to as the automorphism group of a graph, is informally the set of all possible rearrangements of the graph that preserve its edge-vertex connectivity.

A practical way of understanding what rearrangements are permitted by the symmetry group of a graph is to assign labels to the vertices and edges of the graph. Consider moving around the vertices and edges of the graph in such way so that each graph resulting from the reconfiguration connects the same labelled vertices via the same labelled edges.

For example, the figure below displays a graph $\Gamma$ with labelled vertices $\{v_1, v_2, v_3, v_4\}$ and edges $\{e_1, e_2, e_3, e_4, e_5, e_6\}$ :

group_symmetry_of_graph_original

Six symmetries come from permuting the edges $\{e_4, e_5, e_6\}$ connecting the vertices $\{v_1, v_4\}$ and one symmetry comes from reflecting through a horizontal axis. The symmetry arising from a reflection through the horizontal axis is shown below:

group_symmetry_of_graph_reflected

On the other hand, the graph below does not belong to the symmetry group of the initial graph $\Gamma$ because of connecting $v_2$ with $v_4$ through $e_2$ , which introduces a connection not present in $\Gamma$ :

group_symmetry_of_graph_wrong

Let’s count the graphs in the symmetry group of $\Gamma$ . Six graphs symmetric to $\Gamma$ arise from permuting the edges $\{e_4, e_5, e_6\}$ , and this set of six graphs is isomorphic to the symmetric group $\mbox{Sym}_3$ . The original graph $\Gamma$ along with its reflection through the horizontal axis gives a set of two graphs isomorphic to $\mbox{Sym}_2$ . So the symmetry group of $\Gamma$ contains $6\times 2 =12$ graphs, and is isomorphic to the direct product $\mbox{Sym}_3\bigoplus\mbox{Sym}_2$ .

The main aim of this blog post is to provide a mathematically rigorous definition of the symmetry group of a graph starting by the concept of graph symmetry. A symmetry of a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$ is a permutation $f$ of the vertex set $V$ such that the pair of vertices $\{v_1,v_2\}$ form an edge in $\Gamma$ if and only if the pair $\{f(v_1), f(v_2)\}$ also form an edge in $\Gamma$ .

Unfortunately, there is an error in this first definition. In the previous example, if the edges $e_4$ and $e_5$ are permuted, a new distinct graph from the symmetry group of $\Gamma$ arises, which is not accounted by the definition due to permuting the edges but not the vertices of $\Gamma$ .

A more mathematically accurate definition is provided in John Meier’s book “Groups, graphs and trees: an introduction to the geometry of infinite groups” (definition 1.14, p. 10-11). According to Meier’s definition, a symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f$ taking vertices to vertices and edges to edges such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$ , then $\mbox{ends}(f(e))=\{f(v_1),f(v_2)\}$ in $\Gamma$ , where $\mbox{ends}(e)=\{v_1,v_2\}$ denotes the set of two vertices $v_1$ and $v_2$ connected by an edge $e$ .

Meier’s definition corrects the issue of the previous definition, but does not tell what is the domain and range of $f$ . In fact, trying to define the domain and range of $f$ does not seem to be obvious due to the dubious notation $f(e)$ and $f(v_1)$ .

One possible way round this problem is to define graph symmetry to be a set of two separate bijections, one on the vertices and one on the edges of the graph. The third definition would take the following form; a symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a set $\{f_1,f_2\}$ of bijections $f_1:V(\Gamma)\rightarrow V(\Gamma)$ and $f_2:E(\Gamma)\rightarrow E(\Gamma)$ such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$ , then $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$ .

Note that the converse holds in the above definition, i.e. $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma\Rightarrow\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$ . To prove this, assume that $\mbox{ends}(e)=\{q,r\}\ne \{v_1,v_2\}$ . From the definition, $\mbox{ends}(e)=\{q,r\}\Rightarrow\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}$ . Given that $\{q,r\}\ne \{v_1,v_2\}$ , assume without loss of generality that $q\ne v_1$ and $q\ne v_2$ . Since $f_1$ is a bijection, it follows that $f_1(q)\ne f_1(v_1)$ and $f_1(q)\ne f_1(v_2)$ , which is a contradiction since the edge $f_2(e)$ connects two vertices according to $\{f_1(v_1),f_1(v_2)\}=\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}$ .

In light of the validity of the inverse, one can define graph symmetry using the equivalence $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma\iff \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$ .

However, this third definition raises one more question. Having two separate bijections, one for vertices and one for edges, does not allow to define graph symmetry as a single function. The solution is to define a symmetry $f$ of a graph $\Gamma$ by $f(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}$ .

So the third definition can now be corrected. A symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ defined by $f(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}$ , where $f_1:V(\Gamma)\rightarrow V(\Gamma)$ and $f_2:E(\Gamma)\rightarrow E(\Gamma)$ are two bijections such that if $\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma$ , then $\mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\}$ in $\Gamma$ .

This corrected third definition coincides with Meier’s definition if the latter is clarified formally as follows; a symmetry of a graph $\Gamma$ with vertices $V(\Gamma)$ and edges $E(\Gamma)$ is a bijection $f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ with the following three properties:

$v\in V(\Gamma)\Rightarrow f(v)\in V(\Gamma)$ ,
$e\in E(\Gamma)\Rightarrow f(e)\in E(\Gamma)$ ,
$\mbox{ends}(e)=\{v_1,v_2\}$ in $\Gamma\Rightarrow\mbox{ends}(f(e))=\{f(v_1),f(v_2)\}$ in $\Gamma$ .

Having defined graph symmetry, the symmetry group of a graph becomes simply the collection of all graph symmetries. Formally, the symmetry group $\mbox{Sym}(\Gamma)$ of a graph $\Gamma$ is the set of symmetries of $\Gamma$ equipped with the operation of composition of graph symmetries.

Note that the composition $f\circ g$ of two graph symmetries $f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ and $g:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)$ is essentially a composition of two vertex or edge permutations.

Understanding the concept of group action via an example

26/01/2017Books, Geometric group theory, Groups, graphs and trees, MathematicsGroup action, Homomorphismscidom

The following self-contained post clarifies the definition of group action (definition 1.2, p. 3, in the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier) by adapting an example from chapter 7, p. 72-74, of the book “A book of abstract algebra” by Charles C. Pinter.

A rigorous definition of group action and of its group homomorphism representation was provided in a previous post. This post presents the group action on the symmetries of the square to exemplify the concept.

Consider a square with numbered vertices, as shown in the figure below. The set of vertices of the square is $X=\left\{1,2,3,4\right\}$ .

square_vertices

A symmetry of the square can be informally thought of as a way of moving the square so that it coincides with its former position. Every such move is fully described by its effect on the vertices, in the sense that every new vertex position coincides with a distinct former vertex position.

There are exactly 8 symmetric moves of the square, each of which can be described by a permutation of the square’s vertices. Here is the list of the 8 symmetries of the square:

The identity $R_0=\left(\begin{matrix}1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4 \end{matrix}\right)$ , which does not move the square.
Clockwise rotation of the square about its centre $P$ by an angle of $90^{\circ}$ : $R_1=\left(\begin{matrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1\end{matrix}\right)$ .
Clockwise rotation of the square about its centre $P$ by an angle of $180^{\circ}$ : $R_2=\left(\begin{matrix}1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2\end{matrix}\right)$ .
Clockwise rotation of the square about its centre $P$ by an angle of $270^{\circ}$ : $R_3=\left(\begin{matrix}1 & 2 & 3 & 4\\ 4 & 1 & 2 & 3\end{matrix}\right)$ .
Flip of the square about its diagonal $A$ (see figure below): $R_4=\left(\begin{matrix}1 & 2 & 3 & 4\\ 1 & 4 & 3 & 2\end{matrix}\right)$ .
Flip of the square about its diagonal $C$ : $R_5=\left(\begin{matrix}1 & 2 & 3 & 4\\ 3 & 2 & 1 & 4\end{matrix}\right)$ .
Flip of the square about its vertical axis $B$ : $R_6=\left(\begin{matrix}1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3\end{matrix}\right)$ .
Flip of the square about its horizontal axis $D$ : $R_7=\left(\begin{matrix}1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1\end{matrix}\right)$ .

square_dihedral_group

The set of all 8 symmetries of the square is denoted by $D_4=\left\{R_0,R_1,R_2,R_3,R_4,R_5,R_6,R_7\right\}$ . Define the operation $\circ : D_4\times D_4\rightarrow D_4$ to be the function composition $R_i\circ R_j(x)=R_i(R_j(x))$ for $x\in X\left\{1,2,3,4\right\}$ . For example,

$R_1\circ R_6$ is the result of first flipping the square about its vertical axis $B$ and then rotating it clockwise by $90^{\circ}$ :

$R_1\circ R_6 =\left(\begin{matrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1\end{matrix}\right)\circ\left(\begin{matrix}1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3\end{matrix}\right)=\left(\begin{matrix}1 & 2 & 3 & 4\\ 3 & 2 & 1 & 4\end{matrix}\right)=R_5$ .

$R_1\circ R_6 =R_5$ means that first flipping the square about its vertical axis $B$ and then rotating it clockwise by $90^{\circ}$ is the same as flipping the square about its diagonal $C$ .

The set of symmetric permutations $D_4$ of the square along with the operation of permutation composition induces the so-called dihedral group $(D_4, \circ)$ of the symmetries of the square. $|D_4|$ denotes the order of group $(D_4, \circ)$ , which is the number of elements of $D_4$ . Obviously, $|D_4|=8$ .

The symmetric group $(\mbox{Sym}(X), \circ)$ of $X=\left\{1,2,3,4\right\}$ is the set of all the permutations of $X$ , i.e. the set of all the bijective functions from $X$ to $X$ . Since $\mbox{Sym}(X)$ has $4!$ elements, the order of $\mbox{Sym}(X)$ is $|\mbox{Sym}(X)|=24$ .

Note that $D_4\subseteq \mbox{Sym}(X)$ and that $(D_4, \circ)$ is a subgroup of $(\mbox{Sym}(X), \circ)$ .

Any function $\phi:D_4\times X\rightarrow X$ is a group action as long as it satisfies

$\phi(R_0, x)=x$ for all $x \in X=\left\{1,2,3,4\right\}$ (identity property) and
$\phi(R_i\circ R_j, x)=\phi(R_i, \phi(R_j, x))$ for all $i, j=0,1,2,3,4,5,6,7$ and for all $x \in X=\left\{1,2,3,4\right\}$ (compatibility property).

One way of picking a specific group action $\phi$ relies on defining the type of associated group homomorphism $h:D_4\rightarrow\mbox{Sym}(X)$ in a way that respects the identity and compatibility properties of $\phi:D_4\times X\rightarrow X$ .

The simplest possible example would be to choose the group homomorphism $h:D_4\rightarrow\mbox{Sym}(X)$ to be the identity function $h(R_i)=R_i,~i=0,1,2,3,4,5,6,7$ , in which case the group action $\phi$ takes the form $\phi(R_i, x)=R_i(x)$ .

It is easy to check that the the group action $\phi(R_i, x)=R_i(x)$ , which arises by setting the group homomorphism $h$ to be the identity function, satisfies the properties of identity and compatibility:

$\phi(R_0, x)=R_0(x)=x$ ,
$\phi(R_i\circ R_j, x)=R_i\circ R_j(x)=R_i(R_j(x))=R_i(\phi(R_j,x))=\phi (R_i,\phi (R_j, x))$ .

It is also easy to see for instance that the group action $\phi(R_i, x)=R_i(x)$ maps $(R_1, 2)\in D_4\times X$ to $3\in X$ , since $\phi(R_1, 2)=R_1(2)=3$ .

The group action $\phi(R_i, x)=R_i(x)$ is interpreted as the function that maps every symmetric move (permutation) $R_i$ of the square and every square vertex $x$ to the square vertex $R_i(x)$ .

The group homomorphism $h(R_i)=R_i$ is the identity, so it is an injective function. As elaborated in this previous post, since $h$ with $h(R_i)=R_i$ is injective, the group action $\phi$ with $\phi(R_i, x)=R_i(x)$ is faithful.

An example of how to select ideals to obtain quotient rings with desirable properties

22/01/2017A book of abstract algebra, Abstract algebra, Books, MathematicsIdeal, Integral domain, Quotient ringscidom

The following self-contained post demonstrates how to construct quotient rings with desirable properties by elaborating on an example taken from chapter 19, p. 194, of the book “A book of abstract algebra” by Charles C. Pinter.

The fundamental homomorphism theorem for rings employs the kernel $K$ of a homomorphism $f:A\rightarrow B$ to construct a quotient ring $A/K$ isomorphic to ring $B$ . Conversely, the homomorphic image $A/J$ of a ring $A$ is useful for factoring out unwanted features of $A$ to obtain a quotient ring $A/J$ with the desirable properties. Selecting an appropriate ideal $J$ is the key for acquiring the desired quotient ring $A/J$ .

In some cases, picking a suitable ideal $J$ can be done methodically by tracing the desired property of $A/J$ back to an analogous property of $J$ . To demonstrate the process of selecting $J$ , the simple example of obtaining a quotient ring $A/J$ that doesn’t contain any divisors of zero will be considered.

The example under consideration is stated as follows. Let $A$ be a commutative ring with unity. An ideal $J$ of $A$ is prime if and only if $A/J$ is an integral domain (see chapter 19, p. 194, in Charles Pinter’s book “A book of abstract algebra”).

Briefly recall the associated definitions. An integral domain is a commutative ring with unity that doesn’t have any divisors of zero. An ideal $J$ of a commutative ring $A$ is prime if $\forall a,b\in A$ with $ab\in J$ it follows that $a\in J$ or $b \in J$ .

It is straightforward to prove the equivalence of this example. To prove that the integral domain has no divisors, it suffices to observe that $a\in J \Leftrightarrow J=J+a$ . Emphasis will be shifted towards understanding why one would think of using a prime ideal to retain the cancellation property in $A/J$ , i.e. to ensure that there are no divisors of zero in $A/J$ .

Think first how the lack of divisors of zero is stated for $A/J$ . The product of two cosets $J+a$ and $J+b$ in $A/J$ is $(J+a)(J+b)=J+ab$ . Moreover, the zero element of $A/J$ is the coset $J=J+0$ , so to say that $A/J$ has no divisors of zero implies that $J+ab=J\Rightarrow J+a=J$ or $J+b=J$ .

Recall also that for any $x\in A$ , $x\in J \Leftrightarrow J+x=J$ . It then becomes obvious that the property $J+ab=J\Rightarrow J+a=J$ or $J+b=J$ in $A/J$ corresponds to the property $ab\in J\Rightarrow a\in J$ or $b\in J$ , which is the defining property of a prime ideal $J$ .

So it appears that in some cases it is easy to choose an ideal $J$ whose properties are conveyed to a quotient ring $A/J$ .

Group actions as group homomorphisms

18/01/2017Books, Geometric group theory, Groups, graphs and trees, MathematicsGroup action, Homomorphism, Proofscidom

The following self-contained post relates to definition 1.2, p. 3, of the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier.

I have found the interpretation of the definition of group action as a group homomorphism to be verbose. This blog post provides a formalistic exposition of the equivalence between a group action and its induced homomorphism.

Let $G$ be a group and $X$ a set. A group action $\phi$ of $G$ on $X$ is a function $\phi : G \times X \rightarrow X$ that satisfies the properties of

identity, i.e $(\forall x\in X)\phi(e, x)=x$ , where $e$ is the identity element of $G$ ,
and compatibility, i.e. $(\forall g, s\in G)(\forall x\in X)\phi(gs, x)=\phi(g, \phi(s, x))$ .

For convenience, the shortands $ex=x$ and $(gs)x=g(sx)$ are used in place of $\phi(e, x)=x$ and $\phi(gs, x)=\phi(g, \phi(s, x))$ , respectively.

Let $\mbox{Sym}(X)$ denote the symmetric group of $X$ , that is the group of bijective functions from $X$ to $X$ . Consider the family of bijective functions $\left\{f_g:g\in G\right\}\subseteq\mbox{Sym}(X)$ , where $f_g:X\rightarrow X$ and $f_g(x)=\phi(g, x)=gx$ .

It is now possible to define the function $h:G\rightarrow \mbox{Sym}(X)$ as $h(g)=f_g$ . In words, $h$ maps an element $g\in G$ to the bijective function $f_g:X\rightarrow X$ defined by $f_g(x)=\phi(g, x)=gx$ .

The common representation of a group action as a homomorphism relies on the following equivalence; a function $\phi : G \times X \rightarrow X$ is a group action if and only if the function $h:G\rightarrow \mbox{Sym}(X),~h(g)=f_g$ , with $f_g(x)=\phi(g, x)=gx$ , is a group homomorphism. The main point of this blog post has been to formalize this statement. For the sake of completeness, its proof will be provided, albeit being simple.

Firstly assume that $\phi$ is a group action. It will be shown that $h$ is a homomorphism. By definition, $h(gs)=f_{gs}$ . Moreover, $h(g)h(s)=f_gf_s$ , where the product $f_gf_s$ denotes function composition, the operation of the symmetric group $\mbox{Sym}(X)$ . Since $\phi$ is a group action, it follows that $(\forall x\in X) f_{gs}(x)=(gs)x=g(sx)=(f_gf_s)(x)$ , therefore $h(gs)=h(g)h(s)$ , so $h$ is a group homomorphism.

Conversely, assume that $h$ is a homomorphism. It will be shown that $\phi$ is a group action.

The identity $e\in G$ belongs to the kernel of $h$ ; $h(e)=h(ee)$ , whence $h(e)=h(e)h(e)$ , so $h(e)=\varepsilon$ , with $\varepsilon(x)=x$ being the identity function in $\mbox{Sym}(X)$ . Furthermore, $h(e)=f_e$ , so $f_e=\varepsilon$ , which means that $(\forall x\in X)ex=f_e(x)=\varepsilon(x)=x$ . The property of identity is thus satisfied for $\phi$ .

Since $h$ is a homomorphism, it follows that $h(gs)=h(g)h(s)$ , so $f_{gs}=f_g f_s$ . Finally, $(\forall x\in X)(gs)x=f_{gs}(x)=(f_gf_s)(x)=g(sx)$ , hence the compatibility property of $\phi$ is also satisfied, and $\phi$ is a group action.

Proof: any element of a group of prime order generates the group

09/01/2017A book of abstract algebra, Abstract algebra, Books, MathematicsCyclic group, Finite, Lagrange, Order, Prime, Proofscidom

The following self-contained post clarifies the proof of theorem 4, chapter 13, p. 129, of the book “A book of abstract algebra” by Charles C. Pinter.

Let $G$ be a group of prime order $|G|=p$ . It will be shown that for any $a\in G$ with $a\ne e$ it holds that $\langle a\rangle=G,$ where $\langle a\rangle$ is the set generated by $a$ and $e$ is the identity element of $G$ .

Since the order of group $G$ is $|G|=p<\infty$ , the order $\mbox{ord}(a)$ of element $a$ is also finite, i.e. $\mbox{ord}(a)=n<\infty$ for some positive integer $n$ .

Note that the set $\langle a\rangle=\left\{a^0,a^1,\ldots,a^{n-1}\right\}$ generated by $a$ is a subgroup of $G$ , since $\langle a\rangle$ is closed with respect to multiplication and with respect to inverses. Indeed, for any $a^i,a^j\in\langle a\rangle$ , the division algorithm of integers ensures that there exist integers $q,r$ with $0\le r <n$ such that $a^i a^j = a^{i+j}=a^{nq+r}=(a^n)^q a^r=e a^r=a^r\in \langle a \rangle$ . Moreover, the inverse of any $a^i\in \langle a \rangle$ is $(a^i)^{-1}=a^{n-i}\in \langle a \rangle$ .

The order $|\langle a \rangle|$ of the cyclic subgroup $\langle a \rangle$ of $G$ is equal to the order of generator $a$ , that is $|\langle a \rangle|=\mbox{ord}(a)=n$ .

By Lagrange’s theorem, $n$ is a factor of $p$ . Since $p$ is a prime, $n=1$ or $n=p$ . It follows from $a\ne e$ that $n\ne 1$ , so $n=p$ , which means that $|\langle a \rangle|=|G|$ .

$\langle a \rangle\subseteq G$ and $|\langle a \rangle|=|G|\Rightarrow\langle a \rangle=G$ .

Clarification on the proof of isomorphism of finite cyclic groups

07/01/2017A book of abstract algebra, Abstract algebra, Books, MathematicsCyclic group, Order, Proofscidom

The following self-contained post clarifies the proof of theorem 1, chapter 11, p. 113-114, of the book “A book of abstract algebra” by Charles C. Pinter.

In order to show that any two cyclic groups of finite order $n$ are isomorphic to each other, it suffices to show that every cyclic group $\langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\}$ of finite order $n$ is isomorphic to the group $\mathbb{Z}_n$ of integers modulo $n$ with the operation of addition modulo $n$ , where $\mathbb{Z}_n=\left\{0,1,2,\ldots,n-1\right\}$ .

Towards this end, it can be shown that the function $f:\mathbb{Z}_n\rightarrow\langle a\rangle$ defined as $f(i)=a^i$ is a group isomorphism. Recalling the definition of group isomorphism, it suffices to show that $f$ is a bijective homomorphism. It is straightforward to check that $f$ is a bijective function. The fact that $f$ is a homomorphism is proven also easily using laws of exponents for groups, as follows: $f(i+j)=a^{i+j}=a^i a^j=f(i)f(j)$ .

Proving the homomorphic property of $f$ as above works well if $f$ is taken to be $f:\mathbb{Z}\rightarrow\langle a\rangle,~f(i)=a^i,$ that is from the additive group of integers to the cyclic group $\langle a\rangle=\left\{\ldots,a^{-2},a^{-1},a^0,a^1,a^2,\ldots\right\}$ of infinite order generated by $a$ . However, in the case of $f:\mathbb{Z}_n\rightarrow\langle a\rangle$ with $\langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\}$ , there is a slight oversight; the addition implied by $f(i+j)$ is addition modulo $n$ .

Let’s denote the addition modulo $n$ by $\oplus$ . So, now the proof of homomorphic property takes the form $f(i\oplus j)=a^{i\oplus j}=a^i a^j=f(i)f(j)$ . The identity $a^{i+j}=a^i a^j$ is not the same as $a^{i\oplus j}=a^i a^j$ ; the former is one of the common exponent laws for groups, while the latter is not.

What needs to be shown is that the exponents of addition and of addition modulo $n$ coincide, i.e. $a^{i+j}=a^{i\oplus j}$ . The proof of this identity is simple, yet it is useful to be aware of such potential oversight.

According to the division algorithm for integers, there exist unique integers $q$ and $r$ such that $i+j = nq+r$ and $0\le r < n$ . Thus, $a^{i+j}=a^{nq+r}=(a^n)^q a^r$ . Since the cyclic group $\langle a\rangle$ is of order $n$ , it holds that $a^n=e$ , where $e$ is the identity element of $\langle a\rangle$ . So, $a^{i+j}=a^r$ .

Notice that $r$ coincides with the result of the addition modulo $n$ , that is $r=i\oplus j$ . It follows that $a^{i+j}=a^{i\oplus j}$ , which completes the proof.

"There is no royal road to geometry". Euclid

A math blog by Theodore Papamarkou