Tour:Mind's eye test three (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: Factsheet three (beginners)| UP: Introduction three | NEXT: Confidence aggregator three (beginners)
PREVIOUS SECTION MIND'S EYE TEST: Mind's eye test two|NEXT SECTION MIND'S EYE TEST: Mind's eye test four
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

Redoing the results for groups, in weaker algebraic structures

A quick recall of some of the variations of group we saw in part two:

• 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
• Quasigroup: Magma $(S,*)$ such that for any $a,b \in S$, there are unique $x,y \in S$ such that $a * x = y * a = b$

While looking at the problems below, try to recall the corresponding definitions, statements and proofs for groups. Then see whether the same proof can be imitated in the more general structure. In cases where the proof cannot be imitated, or breaks down, try to pin down what special thing we're using about groups that fails to generalize.

Intersections and joins

1. A submonoid of a monoid is a subset that contains the identity element, and is closed under the multiplication. Prove that an arbitrary intersection of submonoids of a monoid is a submonoid.
2. Define: Give equivalent definitions of the submonoid generated by a subset, analogously to the equivalent definitions we gave for subgroup generated by a subset. Using this, define the join of submonoids.
3. Explore: In a group, how is the submonoid generated by a subset related to the subgroup generated by that subset?
4. A subquasigroup of a quasigroup is a multiplicatively closed subset that forms a quasigroup under the induced multiplication. Yes/no plus prove: Is an arbitrary intersection of subquasigroups of a quasigroup, again a subquasigroup?
5. Define: Give equivalent definitions of the subquasigroup generated by a subset (note that you need to fill in, not only the products of elements, but also their ratios). Using this, define the join of subquasigroups.
6. Explore: In a group, how does the subquasigroup generated by a subset relate to the subgroup generated by that subset?
7. Prove that in a monoid, a union of two submonoids, neither of which is contained in the other, may be a submonoid (you may want to look at some of the later exercises for interesting examples). Explore: What is the fact about groups that fails to be true for monoids?
8. Let $G$ be a quasigroup, $H$ and $K$ be subquasigroups, and $L$ be a subquasigroup contained in $H \cup K$. Prove that either $L$ is contained in $H$ or $L$ is contained in $K$. Explore: What is the crucial similarity between groups and quasigroups that allows the proof to generalize?

Cosets

Given a monoid $M$ and a submonoid $N$, define the left coset of an element $x \in M$ as the subset $xN$. Keep in mind the example of the monoid of integers under multiplication (remember that zero is also there in this monoid):

1. Prove that the so-called left cosets are not necessarily pairwise disjoint.
2. Prove that there is no bijection between the left cosets via left multiplication (there is still a map, but the map fails to be bijective on one of the left cosets).
3. Prove that for a cancellative monoid, there is a bijection between the left cosets via left multiplication, even though the left cosets need not be pairwise disjoint (for instance, think of the multiplicative group of nonzero integers).
4. Prove that if $M$ is a monoid and $G$ is a subgroup of $M$, then the left cosets of $G$ in $M$, i.e., the sets of the form $mG, m \in M$, form a partition of $M$.

Illustration of the concepts for groups

The results here should be easy to store in the mind's eye. While getting them the first time may require a few moments of thought, they shouldn't take long to reconstruct after the initial flash of insight.

Subgroups and cosets

1. Prove that if $S$ is a subset of a group $G$, such that $S$ occurs as the left coset of a subgroup, then that subgroup is determined by $S$ (this is easy to prove from one of the equivalent definitions we gave for left coset, so revisit the guided tour page for left coset for the equivalent definitions if you're stuck on this).
2. NEEDS SOME THOUGHT: Suppose $H$ is a nonempty subset of a group $G$ with the property that the identity element is in $H$, and the sets $xH$, $x \in G$, form a partition of $G$ (in other words, either $xH = yH$ or $xH \cap yH$ is empty). Prove that $H$ is a subgroup. [SHOW MORE]
   For full proof, refer: Subset containing identity whose left translates partition the group is a subgroup

Cosets and Lagrange's theorem

1. Prove that in a finite group, any proper subgroup has size at most half the size of the group. Here, proper means that the subgroup is not equal to the whole group. [SHOW MORE]
   For full proof, refer: Subgroup of size more than half is whole group
2. Consider a finite group $G$, and a chain of subgroups of $G$:

$H_0 \le H_1 \le H_2 \le \dots \le H_n = G$

where each $H_i$ is a proper subgroup of $H_{i+1}$ (i.e., $H_i \ne H_{i + 1}$). Prove that $n$ is less than the sum of exponents of the prime divisors of $|G|$, viz., if:

$|G| = p_1^{k_1}p_2^{k_2} \dots p_r^{k_r}$

then:

$n \le k_1 + k_2 + \dots + k_r$

Cosets in infinite groups

Recall Lagrange's theorem. These questions deal with infinitary versions of Lagrange's theorem, i.e., situations where the whole group is infinite.

1. Prove that given an infinite group, there cannot exist a proper subgroup (subgroup other than the whole group) whose set-theoretic complement in the group is finite. In other words, every proper subgroup misses infinitely many elements. [SHOW MORE]
   For full proof, refer: Proper subgroup of infinite group is coinfinite
2. NEEDS SOME THOUGHT: Find a counterexample to the analogous statement for monoids, i.e., find an infinite monoid and a submonoid whose set-theoretic complement is finite and nonempty. (Hint: Consider the monoid of nonnegative integers under addition).
3. Prove that in an infinite group, any subgroup of finite index is infinite.
4. Using the fact that a union of finitely many infinite sets of the same cardinality again has the same cardinality, prove that any subgroup of finite index in an infinite group has the same cardinality as the whole group.
5. Further, prove that the index of a finite subgroup of an infinite group has the same cardinality as that infinite group.
6. Using the fact that a union of countably many infinite sets of the same uncountable cardinality again has the same cardinality, prove that any countable subgroup of an uncountable group has index equal to the cardinality of the group, and prove that any subgroup of countable index in an uncountable group has the same uncountable cardinality.

Generating sets

1. Prove that if $S$ is a subset of $T$, where $S$ and $T$ are subsets of a group $G$, then the subgroup generated by $S$ is contained inside the subgroup generated by $T$.
2. Prove that the subgroup generated by a subset $S$ of a group $G$ is the same as the subgroup generated by the subset $S^{-1}$: the set of inverses of elements of $S$.
3. Prove that the only group with a generating set of size zero is the trivial group. Further, prove that the subgroup generated by the empty set, in any group, is the trivial subgroup.
4. Suppose $G$ is a group and $H,K$ are subgroups, with $A$ a generating set for $H$ and $B$ a generating set for $K$. Then, prove that $A \cup B$ is a generating set for $\langle H, K \rangle$.
5. NEEDS SOME THOUGHT: Suppose $G$ is a group and $H,K$ are subgroups with generating sets $A$ and $B$ respectively. Prove that $A \cap B$ need not be a generating set for $H \cap K$ (use the group of integers).
6. Prove that the set $\{ 2,3 \}$ is a generating set for $\mathbb{Z}$, and that it is irredundant: no proper subset of it generates $\mathbb{Z}$. This gives an example of an irredundant generating set that does not have the smallest possible size (the generating set of smallest possible size is $\{ 1 \}$).
7. Prove that for a finite group, any generating set of minimum cardinality is irredundant.
8. NEEDS SOME THOUGHT: Suppose $S = \{ x_1, x_2, \dots, x_n \}$ is a generating set for a group $G$. Construct the following ascending chain of subgroups:

$\{ e \} \le \langle x_1 \rangle \le \langle x_1, x_2 \rangle \le \dots \le \langle x_1, x_2, \dots, x_n \rangle = G$

Suppose that $S$ is an irredundant generating set, i.e., $S \setminus \{ x_i \}$ is not a generating set for any $i$ (so, nothing can be removed from $S$). Then, prove that the above chain of subgroups is strictly increasing: each subgroup properly contains its predecessor. Use this and a previous exercise to bound the size of $S$ in terms of the order of $G$, when $G$ is finite.

Generating sets and commutativity

1. Prove that in any group, the subgroup generated by one element is abelian.
2. Prove that if $a,b$ commute, then $a^m$ commutes with $b^n$ for any integers $m,n$. (the proof should make use of associativity).
3. NEEDS SOME THOUGHT: Prove that if $S$ is a generating set of $G$, and any two elements of $S$ commute, then every element of $G$ can be written as $a_1^{n_1}a_2^{n_2}\dots a_r^{n_r}$ where all the $a_i$ are distinct elements of $S$ and the $n_i$ are (positive or negative negative) integers.
4. NEEDS SOME THOUGHT: Prove that if $S$ is a generating set of $G$, and any two elements of $S$ commute, then $G$ is an abelian group.
5. Prove that a group $G$ is abelian if and only if for every $a,b \in G$, the subgroup of $G$ generated by $a$ and $b$ is abelian. [SHOW MORE]
   For full proof, refer: Abelianness is 2-local

Intersections and joins (combined with cosets and Lagrange's theorem)

1. Suppose $H,K$ are subgroups of a finite group $G$. Prove that the order of $H \cap K$ divides the greatest common divisor of the orders of $H$ and $K$. Further, prove that the index of $H \cap K$ is a multiple of the least common multiple of the index of $H$ and the index of $K$.
2. Suppose $H,K$ are subgroups of a finite group $G$. Prove that the order of $\langle H, K \rangle$ is a multiple of the least common multiple of the orders of $H$ and $K$. Further, prove that the index of $\langle H, K \rangle$ divides the greatest common divisor of the index of $H$ and the index of $K$.
3. Prove that if $H,K$ are finite subgroups of $G$ such that the order of $H$ and the order of $K$ are relatively prime, then $H \cap K$ is the trivial subgroup.
4. Prove that if $H,K$ are subgroups of a finite group $G$ such that the index of $H$ and the index of $K$ are both finite and relatively prime, then $\langle H,K \rangle$ (the subgroup generated by them) is $G$ (Note: the result holds for infinite groups as well, but requires a little more machinery in that case).
5. Suppose $H$ and $K$ are two subgroups of $G$, and the order of $H$ and $K$ are respectively $2m$ and $3m$ for some integer $m$. Prove that:

$4m \le |H \cup K| \le 5m - 1$

and:

$6m \le \langle H,K \rangle$

Unions of subgroups

1. A cyclic group is a group that has a generating set of size one. Prove that every group is a union of cyclic subgroups, and hence, every group is a join of cyclic subgroups. [SHOW MORE]
   For full proof, refer: every group is a union of cyclic subgroups
2. Suppose $G$ is a group, and for every natural number, we have a subgroup $H_m$, such that $H_m \le H_n$ for $m < n$. Prove that the union of all the subgroups $H_m$ is a subgroup of $G$. [SHOW MORE]
   (Note: This generalizes to unions of arbitrary chains of subgroups, as well as to unions of directed sets of subgroups. For full proof, refer: Directed union of subgroups is subgroup)

Joins, unions and commutativity

1. Prove that $H, K \le G$ are subgroups such that every element of $H$ commutes with every element of $K$, then the join of $H$ and $K$ is the product $HK$, i.e., any element in the join of $H$ and $K$ can be written as $hk, h \in H, k \in K$.
2. Prove that if $(G,+)$ is an abelian group, the join of subgroups $H$ and $K$ of $G$ is the subgroup $H + K$: the set of elements of the form $h + k$ with $h \in H$ and $k \in K$.
3. Suppose $G$ is a group, and for every natural number, we have an abelian subgroup $H_m$, such that $H_m \le H_n$ for $m < n$. Prove that the union of all the subgroups $H_m$ is an abelian subgroup of $G$. [SHOW MORE]
   (Note: This generalizes to unions of arbitrary chains of subgroups, as well as to unions of directed sets of subgroups. For full proof, refer: Abelianness is directed union-closed)

Cosets and intersections

1. Prove that if $H \le K \le G$ are groups, then every left coset of $H$ is contained in a left coset of $K$. For full proof, refer: Subgroup containment implies coset containment
2. NEEDS SOME THOUGHT: Suppose $H,K$ are subgroups of a group $G$ such that there exists a left coset of $H$ contained in a left coset of $K$. Prove that $H$ is a subgroup contained inside $K$. [SHOW MORE]
   For full proof, refer: Coset containment implies subgroup containment
3. NEEDS LOT OF THOUGHT: Suppose $H_i, i \in I$ is a family of subgroups of a group $G$, and $g_i, i \in I$ are elements of $G$. Prove that if the intersection of the left cosets $g_iH_i$ is nonempty, it is a coset of the intersection $\cap_{i \in I} H_i$. [SHOW MORE]
   For full proof, refer: Nonempty intersection of cosets is coset of intersection
4. NEEDS LOT OF THOUGHT: Prove that for any nonempty subset $S$ of a group $G$, there is a unique left coset of a subgroup containing $S$ that is contained in every left coset of a subgroup containing $S$. Use this to define the notion of left coset generated by a nonempty subset.

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