Tour:Mind's eye test two (beginners)

This page is a mind's eye test (more info), part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Confidence aggregator two (beginners)| UP: Introduction two | NEXT: Examples peek two (beginners)
PREVIOUS SECTION MIND'S EYE TEST: Mind's eye test one|NEXT SECTION MIND'S EYE TEST: Mind's eye test three
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

The problems marked NEEDS SOME THOUGHT may require a bit of writing and checking the first time you try them. The problems marked NEEDS LOT OF THOUGHT require a lot of writing and checking, and combining more than one idea.

For each problem, particularly one that you weren't able to solve immediately, and needed to think about, identify what fact we have seen in part two that is most closely related to that problem, and review the result.

Notions seen so far

Quick recall:

• Magma: Set with binary operation
• Semigroup: Set with associative binary operation
• Monoid: Set with associative binary operation having two-sided neutral element
• Group: Monoid where every element has a two-sided inverse

Associativity and power structure

In a monoid $(S,*)$ with two-sided identity element $e$, we can define, for $x \in S$ and $n$ a natural number, $x^n = x * x * \dots * x$ where $x$ occurs $n$ times. The parenthesization is irrelevant by generalized associativity. We further define $x^0 = e$.

1. Prove that $x^{m + n} = x^m * x^n$ for $m,n$ natural numbers and $x \in G$.
2. Prove that $(x^m)^n = x^{mn}$ for $m,n$ natural numbers.

For a group $G$ and an element $x \in G$, we define:

• $x^m$ is the $m$-fold product of $x$ for $m$ a positive integer.
• $x^0$ is the identity element of $G$.
• $x^{-m}$ is defined as $(x^{-1})^m$ for $m$ a positive integer.

1. NEEDS SOME THOUGHT: Prove that for a group $G$, $x^{m+n} = x^mx^n$ for $m,n$ integers and $x \in G$.
2. NEEDS SOME THOUGHT: Prove that for a group $G$, $(x^m)^n = x^{mn}$ for $m,n$ integers and $x \in G$.

Inverses

1. Suppose $(S,*)$ is a magma with a two-sided neutral element $e$, such that every element has a unique left inverse and a unique right inverse. Prove that the left inverse map (the map sending every element to its left inverse) and the right inverse map (the map sending every element to its right inverse) are (two-sided) inverse maps to each other. Hence, prove that both maps are bijective. (Note: In the absence of associativity, we cannot conclude that the left and right inverse maps are the same.)
2. Prove that in a monoid, any left inverse to an element must equal any right inverse. (already seen in the tour)
3. NEEDS SOME THOUGHT: Prove that in a monoid, the set of elements that have left inverses is a submonoid (with the same identity element). [SHOW MORE]
   For full proof, refer: Left-invertible elements of monoid form submonoid
4. NEEDS SOME THOUGHT: Prove that in a monoid, the set of elements that have left inverses and the set of elements that have right inverses are both submonoids, and their intersection is a subgroup (i.e., a submonoid with the same identity element, that is a group under the induced operation). Further, prove that this is the largest possible subgroup of the monoid: it is the largest submonoid that is a group under the induced multiplication.
5. NEEDS SOME THOUGHT: Prove that if every element in a monoid has a left inverse, then the monoid is a group. [SHOW MORE]
   For full proof, refer: Monoid where every element is left-invertible equals group
6. Define: Using the preceding exercise, give an alternative, more minimal definition of group.
7. NEEDS LOT OF THOUGHT: Suppose $(S,*)$ is a semigroup with a left neutral element $e$ (i.e., $e * a = a \ \forall \ a \in S$) and such that for every $a \in S$, there exists $b \in S$ such that $b * a = e$. Prove that $S$ is a group under $*$ with identity element $e$.[SHOW MORE]
   For full proof, refer: Semigroup with left neutral element where every element is left-invertible equals group

Cancellation

This requires a little playing around with set theory, particularly the fact that for finite sets, injective maps are bijective. Solving these the first time may require some thought; however, the solutions, once obtained, are easy to store in the mind's eye.

For all the questions below, we use the following new term: A quasigroup is a magma $S$ with binary operation $*$, where for any $a,b \in S$, there exist unique $x,y \in S$ such that $a * x = y * a = b$.

1. Prove that in a quasigroup, every element is both left and right cancellative. [SHOW MORE]
   For full proof, refer: Quasigroup implies cancellative
2. Prove that any group is a quasigroup. [SHOW MORE]
   For full proof, refer: Group implies quasigroup
3. NEEDS SOME THOUGHT: Prove that for a finite magma (a magma whose underlying set is finite), being a quasigroup is equivalent to every element being cancellative.
4. NEEDS LOT OF THOUGHT: Prove that a nonempty semigroup that is also a quasigroup is a group (split this in two parts: find an identity element, and find inverses). [SHOW MORE]
   For full proof, refer: Associative quasigroup equals group
5. Define: Use the result of the previous problem to give an alternative definition of group. (This alternative definition, in fact, predates the modern definition of group).
6. Using the results above, prove that a finite group is the same thing as a nonempty finite cancellative semigroup.

This gives an alternative proof that any subsemigroup of a finite group is a subgroup.

Left and right multiplication maps

Suppose $(S,*)$ is a magma. For $g \in S$, let $l_g:S \to S$ be the map given by left multiplication by $g$, and $r_g:S \to S$ be the map given by right multiplication by $g$. In other words:

$l_g = x \mapsto g * x \qquad r_g = x \mapsto x * g$

1. Prove that $S$ is a semigroup if and only if $l_g \circ r_h = r_h \circ l_g$ for all $g,h \in S$. Here, $\circ$ denotes function composition.
2. Prove that $S$ is a semigroup if and only if $l_g \circ l_h = l_{g * h}$ for all $g,h \in S$.
3. Prove that $S$ is a semigroup if and only if $r_g \circ r_h = r_{h * g}$ for all $g,h \in S$.
4. Prove that $g \in S$ is left-cancellative if and only if $l_g$ is injective, and right-cancellative if and only if $r_g$ is injective.
5. Prove that $S$ is a quasigroup if and only if $l_g, r_g$ are bijective for all $g \in S$. In particular, prove that $l_g, r_g$ are bijections if $S$ is a group.
6. Prove that if $T$ is a nonempty submagma of $S$, and $g \in T$, then $l_g$ sends $T$ to $T$.
7. Prove that if $H$ is a subgroup of a group $G$, and $g \in H$, then $l_g$ restricts to a bijection from $H$ to itself.
8. Prove that if $(S,*)$ is a magma that has at least one right-cancellative element, then for $g,h \in S$ such that $g \ne h$, $l_g \ne l_h$. Formulate an analogous statement with left-cancellative elements and right multiplication maps.
9. NEEDS LOT OF THOUGHT: Prove that if $(S,*)$ is a monoid, and $f: S \to S$ is such that $f \circ l_g = l_g \circ f$ for all $g \in S$, then $f = r_h$ for some $h \in S$. (Hint: You need to use something special about monoids. The result isn't true for semigroups that are not monoids.)

Defining subobjects

These again require some thought, and possibly a review of the proof ideas we've already seen, but should be easy to hold in the mind's eye once cracked.

1. Define: Formulate two definitions of submonoid, one as a subset that is closed under the multiplication and has its own neutral element (identity element), and the other as a subset that is closed under multiplication and has the same identity element. Use the monoid $\{ 0, 1 \}$ under multiplication to prove that these two definitions are not equivalent.
2. Prove that for a cancellative monoid (a monoid where every element is both left and right cancellative) the two definitions of submonoid are equivalent.
3. Define: Formulate two definitions of subquasigroup, one as a subset that is closed under the multiplication and such that the induced operation forms a quasigroup, and another, as a subset that is closed under multiplication and under the left and right quotient operations. Prove that the two definitions are equivalent.
4. An algebra loop is a quasigroup with a two-sided neutral element (identity element) that we call $e$. Define: Formulate two possible definitions of subloop of an algebra loop (one, postulating only closure under the binary operation such that the condition for being an algebra loop is satisfied, and the other, postulating that it contains the identity element). Prove that the two definitions are equivalent.
5. Prove that in an algebra loop, every element has a unique left inverse and a unique right inverse. Further, prove that any subloop of an algebra loop is closed under both the left and the right inverse maps.

Subset-hereditariness

These are ready-to-verify statements, that require practically zero justification:

1. Prove that associativity inherits to subsets: thus, any subset of a semigroup, closed under the multiplication, is a subsemigroup.
2. Prove that cancellation inherits to subsets; thus, any subset of a cancellative magma, closed under the binary operation, is cancellative.
3. Prove that commutativity inherits to subsets; thus, any subset of a commutative magma, closed under the binary operation, is commutative.
4. Prove that the existence of inverse elements doesn't inherit to subsets. So, we can find a subset of a group, closed under the multiplication, that is not closed under taking inverses.

More notions

Left, middle and right associative

1. An element $a$ in a magma $(S,*)$ is termed left-associative (or left nuclear) if $(a * b) * c = a * (b * c)$. Prove that the left-associative elements of a magma form a submagma.[SHOW MORE]
   For full proof, refer: Left-associative elements of magma form submagma
2. By analogy with the preceding exercise, formulate definitions of middle-associative or right-associative and formulate statements analogous to the preceding exercise. Then, prove those statements.[SHOW MORE]
   For full proof, refer: middle-associative elements of magma form submagma, right-associative elements of magma form submagma

Further element properties

1. An element $a$ in a magma $(S,*)$ is termed idempotent if $a * a = a$. Prove that in a cancellative monoid (and hence, in a group), the only idempotent element is the identity element.
2. An element $n$ in a magma $(S,*)$ is termed a left nil if $n * a = n$ for all $a \in S$. Analogously, define right nil. Prove that any left nil and right nil must be equal. Also, prove that any nil is idempotent, and a cancellative element cannot be a nil unless the magma has exactly one element.
3. Prove that any left neutral element is left associative.
4. Prove that in a magma, every element is left neutral if and only if every element is a right nil. Further, prove that such a magma is a semigroup. Finally, prove that every subset of this magma is a subsemigroup.

Breakdown for small sizes

1. Prove that the empty magma (the empty set, with multiplication defined vacuously) is a semigroup, but not a monoid.
2. Prove that there is only one way to define a multiplication on a magma with one element. This gives a commutative, associative multiplication, and the magma thus obtained is a group: the trivial group.
3. Prove that there are different possible multiplications on a set with two elements, and they need not be commutative, associative, have identity elements, have nil elements, have inverses, etc.

Notions in groups

Manipulating equations for subsets and their products

1. Prove that if $A$ is a finite subset of a group $G$, and $x \in G$, the subset $Ax = \{ ax \mid a \in A \}$ has the same size as $A$.
2. Prove that if $A$ is a subset of a group $G$, and $x \in G$, then $Ax \cap A$ is nonempty if and only if there exist $a,b \in A$ such that $x = a^{-1}b$.
3. Prove that if $A,B$ are finite subsets of $G$, and $AB$ is defined as the set of all $ab, a \in A, b \in B$, then $|AB| \le |A||B|$.
4. NEEDS SOME THOUGHT: Prove that if $A$ is a subset of a finite group $G$, such that $|G| > |A|^2$, then there exists an element $x \in G$ such that $Ax \cap A$ is empty.
5. NEEDS LOT OF THOUGHT: Prove that if $A,B$ are subsets of a finite group $G$ such that $|G| < |A| + |B|$, then $AB = G$, i.e., every element of $G$ can be written in the form $ab, a \in A, b \in B$. <toggledisplay>Further information: Product of subsets whose total size exceeds size of group equals whole group