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.
Contents
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 with two-sided identity element
, we can define, for
and
a natural number,
where
occurs
times. The parenthesization is irrelevant by generalized associativity. We further define
.
- Prove that
for
natural numbers and
.
- Prove that
for
natural numbers.
For a group and an element
, we define:
-
is the
-fold product of
for
a positive integer.
-
is the identity element of
.
-
is defined as
for
a positive integer.
- NEEDS SOME THOUGHT: Prove that for a group
,
for
integers and
.
- NEEDS SOME THOUGHT: Prove that for a group
,
for
integers and
.
Inverses
- Suppose
is a magma with a two-sided neutral element
, 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.)
- Prove that in a monoid, any left inverse to an element must equal any right inverse. (already seen in the tour)
- 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]
- 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.
- NEEDS SOME THOUGHT: Prove that if every element in a monoid has a left inverse, then the monoid is a group. [SHOW MORE]
- Define: Using the preceding exercise, give an alternative, more minimal definition of group.
- NEEDS LOT OF THOUGHT: Suppose
is a semigroup with a left neutral element
(i.e.,
) and such that for every
, there exists
such that
. Prove that
is a group under
with identity element
.[SHOW MORE]
The two videos below cover some of the questions above. The first video discusses Question (1) and (3).
The second video discusses Question (5).
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 with binary operation
, where for any
, there exist unique
such that
.
- Prove that in a quasigroup, every element is both left and right cancellative. [SHOW MORE]
- Prove that any group is a quasigroup. [SHOW MORE]
- 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.
- 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]
- 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).
- 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 is a magma. For
, let
be the map given by left multiplication by
, and
be the map given by right multiplication by
. In other words:
- Prove that
is a semigroup if and only if
for all
. Here,
denotes function composition.
- Prove that
is a semigroup if and only if
for all
.
- Prove that
is a semigroup if and only if
for all
.
- Prove that
is left-cancellative if and only if
is injective, and right-cancellative if and only if
is injective.
- Prove that
is a quasigroup if and only if
are bijective for all
. In particular, prove that
are bijections if
is a group.
- Prove that if
is a nonempty submagma of
, and
, then
sends
to
.
- Prove that if
is a subgroup of a group
, and
, then
restricts to a bijection from
to itself.
- Prove that if
is a magma that has at least one right-cancellative element, then for
such that
,
. Formulate an analogous statement with left-cancellative elements and right multiplication maps.
- NEEDS LOT OF THOUGHT: Prove that if
is a monoid, and
is such that
for all
, then
for some
. (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.
- 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
under multiplication to prove that these two definitions are not equivalent.
- Prove that for a cancellative monoid (a monoid where every element is both left and right cancellative) the two definitions of submonoid are equivalent.
- 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.
- An algebra loop is a quasigroup with a two-sided neutral element (identity element) that we call
. 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.
- 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:
- Prove that associativity inherits to subsets: thus, any subset of a semigroup, closed under the multiplication, is a subsemigroup.
- Prove that cancellation inherits to subsets; thus, any subset of a cancellative magma, closed under the binary operation, is cancellative.
- Prove that commutativity inherits to subsets; thus, any subset of a commutative magma, closed under the binary operation, is commutative.
- 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
- An element
in a magma
is termed left-associative (or left nuclear) if
. Prove that the left-associative elements of a magma form a submagma.[SHOW MORE]
- 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]
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