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
Contents
- 1 Redoing the results for groups, in weaker algebraic structures
- 2 Illustration of the concepts for groups
- 2.1 Subgroups and cosets
- 2.2 Cosets and Lagrange's theorem
- 2.3 Cosets in infinite groups
- 2.4 Generating sets
- 2.5 Generating sets and commutativity
- 2.6 Intersections and joins (combined with cosets and Lagrange's theorem)
- 2.7 Unions of subgroups
- 2.8 Joins, unions and commutativity
- 2.9 Cosets and intersections
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
such that for any
, there are unique
such that
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
- 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.
- 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.
- Explore: In a group, how is the submonoid generated by a subset related to the subgroup generated by that subset?
- 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?
- 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.
- Explore: In a group, how does the subquasigroup generated by a subset relate to the subgroup generated by that subset?
- 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?
- Let
be a quasigroup,
and
be subquasigroups, and
be a subquasigroup contained in
. Prove that either
is contained in
or
is contained in
. Explore: What is the crucial similarity between groups and quasigroups that allows the proof to generalize?
Cosets
Given a monoid and a submonoid
, define the left coset of an element
as the subset
. Keep in mind the example of the monoid of integers under multiplication (remember that zero is also there in this monoid):
- Prove that the so-called left cosets are not necessarily pairwise disjoint.
- 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).
- 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).
- Prove that if
is a monoid and
is a subgroup of
, then the left cosets of
in
, i.e., the sets of the form
, form a partition of
.
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
- Prove that if
is a subset of a group
, such that
occurs as the left coset of a subgroup, then that subgroup is determined by
(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).
- NEEDS SOME THOUGHT: Suppose
is a nonempty subset of a group
with the property that the identity element is in
, and the sets
,
, form a partition of
(in other words, either
or
is empty). Prove that
is a subgroup. [SHOW MORE]
Cosets and Lagrange's theorem
- 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]
- Consider a finite group
, and a chain of subgroups of
:
where each is a proper subgroup of
(i.e.,
). Prove that
is less than the sum of exponents of the prime divisors of
, viz., if:
then:
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.
- 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]
- 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).
- Prove that in an infinite group, any subgroup of finite index is infinite.
- 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.
- Further, prove that the index of a finite subgroup of an infinite group has the same cardinality as that infinite group.
- 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
- Prove that if
is a subset of
, where
and
are subsets of a group
, then the subgroup generated by
is contained inside the subgroup generated by
.
- Prove that the subgroup generated by a subset
of a group
is the same as the subgroup generated by the subset
: the set of inverses of elements of
.
- 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.
- Suppose
is a group and
are subgroups, with
a generating set for
and
a generating set for
. Then, prove that
is a generating set for
.
- NEEDS SOME THOUGHT: Suppose
is a group and
are subgroups with generating sets
and
respectively. Prove that
need not be a generating set for
(use the group of integers).
- Prove that the set
is a generating set for
, and that it is irredundant: no proper subset of it generates
. 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
).
- Prove that for a finite group, any generating set of minimum cardinality is irredundant.
- NEEDS SOME THOUGHT: Suppose
is a generating set for a group
. Construct the following ascending chain of subgroups:
Suppose that is an irredundant generating set, i.e.,
is not a generating set for any
(so, nothing can be removed from
). 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
in terms of the order of
, when
is finite.
Generating sets and commutativity
- Prove that in any group, the subgroup generated by one element is abelian.
- Prove that if
commute, then
commutes with
for any integers
. (the proof should make use of associativity).
- NEEDS SOME THOUGHT: Prove that if
is a generating set of
, and any two elements of
commute, then every element of
can be written as
where all the
are distinct elements of
and the
are (positive or negative negative) integers.
- NEEDS SOME THOUGHT: Prove that if
is a generating set of
, and any two elements of
commute, then
is an abelian group.
- Prove that a group
is abelian if and only if for every
, the subgroup of
generated by
and
is abelian. [SHOW MORE]
Intersections and joins (combined with cosets and Lagrange's theorem)
- Suppose
are subgroups of a finite group
. Prove that the order of
divides the greatest common divisor of the orders of
and
. Further, prove that the index of
is a multiple of the least common multiple of the index of
and the index of
.
- Suppose
are subgroups of a finite group
. Prove that the order of
is a multiple of the least common multiple of the orders of
and
. Further, prove that the index of
divides the greatest common divisor of the index of
and the index of
.
- Prove that if
are finite subgroups of
such that the order of
and the order of
are relatively prime, then
is the trivial subgroup.
- Prove that if
are subgroups of a finite group
such that the index of
and the index of
are both finite and relatively prime, then
(the subgroup generated by them) is
(Note: the result holds for infinite groups as well, but requires a little more machinery in that case).
- Suppose
and
are two subgroups of
, and the order of
and
are respectively
and
for some integer
. Prove that:
and:
Unions of subgroups
- 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]
- Suppose
is a group, and for every natural number, we have a subgroup
, such that
for
. Prove that the union of all the subgroups
is a subgroup of
. [SHOW MORE]
Joins, unions and commutativity
- Prove that
are subgroups such that every element of
commutes with every element of
, then the join of
and
is the product
, i.e., any element in the join of
and
can be written as
.
- Prove that if
is an abelian group, the join of subgroups
and
of
is the subgroup
: the set of elements of the form
with
and
.
- Suppose
is a group, and for every natural number, we have an abelian subgroup
, such that
for
. Prove that the union of all the subgroups
is an abelian subgroup of
. [SHOW MORE]
Cosets and intersections
- Prove that if
are groups, then every left coset of
is contained in a left coset of
. For full proof, refer: Subgroup containment implies coset containment
- NEEDS SOME THOUGHT: Suppose
are subgroups of a group
such that there exists a left coset of
contained in a left coset of
. Prove that
is a subgroup contained inside
. [SHOW MORE]
- NEEDS LOT OF THOUGHT: Suppose
is a family of subgroups of a group
, and
are elements of
. Prove that if the intersection of the left cosets
is nonempty, it is a coset of the intersection
. [SHOW MORE]
- NEEDS LOT OF THOUGHT: Prove that for any nonempty subset
of a group
, there is a unique left coset of a subgroup containing
that is contained in every left coset of a subgroup containing
. 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