Tag Archives: Proof

Proof: characterisation of Jordan measurability

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:

  1. E is Jordan measurable, which means that m_{*}(E)=m^{*}(E).
  2. For every \epsilon>0 there exist elementary sets A\subseteq E\subseteq B such that m(B\setminus A)\le\epsilon.
  3. 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

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} andn\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

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.

Group actions as group homomorphisms

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

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

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 identitya^{i+j}=a^i a^j is not the same asa^{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.

Proof: every cycle expresses as a product of transpositions

The following self-contained post provides a proof of the fact that every cycle can be expressed as a product of one or more transpositions, as stated in chapter 8, p. 83, of the book “A book of abstract algebra” by Charles C. Pinter.

To show that a cycle (a_1~a_2~\dots~a_{r-1}~a_r) can be written as a product of one or more transpositions, it suffices to prove the validity of the identity (a_1~a_2~\dots~a_{r-1}~a_r)=(a_r~a_{r-1})\dots (a_r~a_2)(a_r~a_1), which will be done by using mathematical induction.

Assume that the identity holds for k. It will be shown that it also holds for k+1, as in (a_1~a_2~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_2)(a_{k+1}~a_1).

Start by noticing that (a_1~a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})(a_{k+1}~a_1).

Due to the induction assumption, which says that a k-length cycle can be decomposed into a product of transpositions, (a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1}) can be written as (a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_3)(a_{k+1}~a_2).

By combining the last two equations, the conclusion follows for k+1.

Proof: the product of disjoint cycles of a permutation is unique

Theorem 1, p. 82, in the book “A book of abstract algebra” by Charles C. Pinter states that “Every permutation is either the identity, a single cycle, or a product of disjoint cycles”. The theorem is proved in the book. After the proof, it is stated that it is easy to see that the product of cycles is unique, except for the order of factors. I have seen online proofs of this claim of uniqueness based on the concept of orbit. In what follows, an alternative proof is offered without relying on orbits.

Assume that there exists a permutation \pi which can be written as a product of disjoint cycles in two ways. So, there are two collections, each consisting of disjoint cycles, C=\left\{c_1,c_2,\dots,c_n\right\} and S=\left\{s_1,s_2,\dots,s_m\right\} such that C\ne S and \pi=\prod_{i=1}^{n}c_i=\prod_{i=1}^{m}s_i.

C\ne S\Rightarrow C\not\subseteq S~\mbox{or}~S\not\subseteq C. Without loss of generality, assume that C\not\subseteq S. Thus, (\exists~\mbox{cycle}~c_i \in C)(\forall~\mbox{cycles}~s_k\in S) c_i\ne s_k.

Let a_q be some element in cycle c_i. Since a_q\in c_i and the cycles in C are disjoint, a_q is permuted by \pi. Therefore, \exists~\mbox{cycle}~s_l\in S such that a_q\in s_l.

The cycles c_i and s_l are disjoint from the rest of cycles in C and S, respectively. Thus, c_i(a_q)=s_l(a_q)=\pi(a_q).

Since c_i\ne s_l, there exists an element a_p that breaks the equality arising from the successive implementation of permutation \pi in each of the two cycles c_i and s_l starting from a_q. Thereby, there exists an element a_p in c_i and in s_l with c_i(a_p)\ne s_l(a_p). This is a contradiction, since the permutation \pi is a function, so a_p should be mapped to a unique element \pi(a_p).

Proof: the Hausdorff metric is finite under the boundedness assumption

Let (E,\rho) be a metric space and \mathcal{F} the family of non-empty, closed and bounded subsets of E. For any X,Y\in\mathcal{F}, define

d(X, Y)=\max\{\sup\{\rho(x,Y):x\in X\},\sup\{\rho(y,X):y\in Y\}\},

where \rho(x,Y) denotes the distance of point x\in X from set Y and \rho(y,X) is the distance of point y\in Y from set X, that is

\rho(x,Y)=\inf\{\rho(x,y):y\in Y\},~\rho(y,X)=\inf\{\rho(y,x):x\in X\}.

It can be shown that (\mathcal{F},d) is a metric space, and the metric d is known as the Hausdorff metric. In order to prove that d:\mathcal{F}\times\mathcal{F}\rightarrow \mathbb{R} is a metric, the following three properties of (the definition of) metric need to be shown:

  1. d(X,Y)=0\Leftrightarrow X=Y,
  2. d(X,Y)=d(Y,X),
  3. d(X,Y)\le d(X,Z)+d(Z,Y).

Proofs of the validity of these three properties for the Hausdorff metric are readily available in several books of topology. To ensure that the Hausdorff metric is well-defined, its finiteness will be shown.

Let x\in X and y\in Y. Then, since

\rho(X,Y)=\inf\{\rho(x,y):(x,y)\in X\times Y\},

it follows that for every n\in\mathbb{N} there exist z\in X and w\in Y such that

\rho(z,w)\le\rho(X,Y)+\frac{1}{n}.\ \ \ \ (1)

Indeed, assume that (1) is not true. Then there exists n_0\in\mathbb{N} such that for all z\in X and w\in Y it holds that



\inf\{\rho(z,w):(z,w)\in X\times Y\}=\rho(X,Y)\ge \rho(X,Y)+\frac{1}{n_0}\Rightarrow\frac{1}{n_0}\le 0,

so a contradiction has been reached, which means that (1) actually holds.

According to the triangle inequality of metric \rho,

\rho(x,y)\le \rho(x,z)+\rho(z,w)+\rho(w,y).\ \ \ \ (2)

It thus follows from (1) and (2) that for every n\in\mathbb{N}

\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y)+\frac{1}{n}.\ \ \ \ (3)

Note that (3) holds because the sets X,~Y are bounded, which means that their respective diameters \delta(X),~\delta(Y) satisfy

\rho(x,z)\le\delta(X)=\sup\{\rho(q,q):q\in X\}<\infty,

\rho(w,y)\le\delta(Y)=\sup\{\rho(q,q):q\in Y\}<\infty.

Since (3) holds for all n\in\mathbb{N}, it follows that

\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (4)

Indeed, assume that (4) is not true. Then it holds that


and, in combination with (3), it is deduced that for any n\in\mathbb{N}


which is a contradiction because it follows from the Archimedean property that there exists n_0\in\mathbb{N} such that


hence (4) is true.

Recalling that

\rho(x,Y)=\inf\{\rho(x,y):y\in Y\}\le\rho(x,y),

it follows from (4) that for any x\in X

\rho(x,Y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (5)

Since (5) holds for any x\in X, it follows that the set \{\rho(x,Y):y\in Y\} has an upper bound, therefore according to the completeness axiom for real numbers, \{\rho(x,Y):y\in Y\} has a supremum. In particular,

\sup\{\rho(x,Y):x\in X\}\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (6)

By means of symmetry of (6), this also means that

\sup\{\rho(y,X):y\in Y\}\le \delta(X)+\rho(X,Y)+\delta(Y),\ \ \ \ (7)

which completes the proof.