Random Proofs

Exercise 7S.1.1

Proposition

Let real function denote a function $f : \mathbb{R} \to \mathbb{R}.$

1. There exist order-preserving and non-order preserving real functions.
2. There exist metric-preserving and non-metric preserving real functions.
3. There exist addition-preserving and non-addition preserving real functions.

Proof

Clearly, the identity function $\id_\mathbb{R}$ is order-preserving, metric-preserving, and addition preserving.

Let $f : \mathbb{R} \to \mathbb{R}$ be defined as $x \mapsto x^2.$

It is not order-preserving since $-1 \leq 0$ but $f(-1) \not\leq f(0).$ It is not metric preserving, since $|0 - 0.1| = 0.1$ but $|0 - 0.1^2| = 0.01.$ It is not addition preserving, see freshman’s dream.

$\blacksquare$

Exercise 7S.1.11

Proposition

Let $A$ be a set with two partitions $\{A_p\}_{p \in P}$ and $\{A_{p'}\}_{p' \in P'}.$ Suppose for each $p \in P$ there exists a $p' \in P'$ with $A_p = A_{p'}.$

Then (1) for each $p \in P$ there exists at most one $p' \in P'$ such that $A_p = A_{p'},$ and (2) for each $p' \in P'$ there is a $p \in P$ such that $A_p = A_{p'}.$

Proof

Let $p \in P.$ If no $p' \in P'$ exists satisfying $A_p = A_{p'},$ we’re done. Suppose otherwise that there exists at least one suitable $p' \in P'.$ In that case, a different label $q \in P'$ has to give a disjoint subset from $A_{p'},$ hence $A_{p'} \neq A_{q},$ ruling out the possibility of multiple admissible $p' \in P'.$ This proves (1).

Fix $p' \in P'.$ Note that $A_{p'}$ is necessarily non-empty, by definition of a partition. Let $a \in A_{p'}$ be some element of that subset. Every element of $A$ belongs to exactly one subset among $\{A_p \mid p \in P\}.$ So, suppose $a \in A_{q}$ for some $q \in P.$ By hypothesis, we have a corresponding label $q' \in P'$ such that $A_q = A_{q'}.$ Then $a \in A_{q'}.$ By disjointness, $a \in A_{p'}$ and $a \in A_{q'}$ implies $A_{p'} = A_{q'}.$ Thus $A_{p'} = A_q,$ as required for (2).

$\blacksquare$

Semigroup $S$ with $2$-transitive $\mathrm{Aut}(S)$

1

Suppose $S$ is a semigroup such that $\mathrm{Aut}(S)$ acts $2$-transitively on $S$. Then $S$ is a left- or right-zero band.

Proof

Suppose $S$ has at least two distinct elements, say, $a,b \in S.$ For each pair of distinct elements $x,y \in S,$ let $f_{x,y}(z)$ denote an automorphism such that $f_{x,y}(a) = x$ and $f_{x,y}(b) = y.$

Let $x \in S$ and suppose that $x^2 \neq x.$ Then $f_{x,x^2}(a^2) = x^2$ and $f_{x,x^2}(b) = x^2.$ By injectivity of $f_{x,x^2},$ $a^2 = b.$ Similarly, $f_{x^2,x}(b^2) = f_{x^2,x}(a)$ forces $b^2 = a.$ Then $a = a^4$ and hence $a^3$ is idempotent. Then, since $f_{x,x^2}(a) = x$ and $f_{x,x^2}(a^4) = x^4$, $x^3$ is also idempotent. Thus $x \neq x^3.$ Now, $f_{x,x^3}(a^3) = f_{x,x^3}(b)$ forces $a^3 = b,$ and hence $a = b^2 = b,$ a contradiction. Thus, $x^2 = x.$

Suppose $ab \neq a.$ Then $f_{a,ab}(ab) = a^2b = ab = f_{a,ab}(b),$ so $ab = b.$ Hence, $ab \in \{a,b\}.$

Let $x,y \in S.$ If $x = y,$ then $xy = y^2 = y,$ and we’re done. If $x \neq y,$ then $f_{x,y}(ab) = xy,$ $f_{x,y}(a) = x,$ and $f_{x,y}(b) = y.$ If $ab = a,$ then $xy = x.$ Otherwise, $xy = y.$

$\blacksquare$

Note

If $S$ is a finite semigroup such that $\mathrm{Aut}(S)$ acts $1$-transitively, then $S$ is a rectangular band. This fails in the infinite case, for example if $S$ is the additive semigroup of positive real numbers.

2

Suppose $M$ is a magma such that $\mathrm{Aut}(M)$ acts $2$-transitively on $M.$ Let $w_1,w_2 \in \mathbf{F}\{a,b\}$ be elements of the free magma on two generators. If there exist distinct $u,v \in M$ such that $\mathrm{ev}_{u,v}(w_1) = \mathrm{ev}_{u,v}(w_2),$ then this identity holds for all elements of $M.$

Proof

For any distinct $x,y \in M$ there exists an automorphism sending $u$ to $x$ and $v$ to $y.$

$\blacksquare$

3

Suppose $M$ is a magma such that $\mathrm{Aut}(M)$ acts $2$-transitively on $M.$

Then $M$ is idempotent.

Proof

If $M$ is associative, earlier proof demonstrates that $M$ is a zero band. Suppose $M$ is not a zero band and let $a,b \in M$ such that $ab \notin \{a,b\}.$

Suppose $a \neq a^2.$ Then $f_{a,a^2}(a^2) = f_{a,a^2}(b)$ so $a^2 = b.$ Also, $f_{a,ab}(a^2) = a^2$ and $f_{a,ab}(b)=ab,$ hence $a^2 = b = ab.$ This is a contradiction. Thus, $a = a^2$ and for any distinct $x \in M$ such that $x \neq a,$ $x = f_{x,a}(a) = f_{x,a}(a^2) = x^2.$

$\blacksquare$