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