Difference between revisions of "Tour:Examples peek two (beginners)"
(→Modular arithmetic) |
(→Metric spaces and maps between them) |
||
(10 intermediate revisions by the same user not shown) | |||
Line 15: | Line 15: | ||
# '''Prove that''' the positive integers, under multiplication, form a cancellative monoid. | # '''Prove that''' the positive integers, under multiplication, form a cancellative monoid. | ||
# For any positive integer <math>n</math>, '''prove that''' the set of positive integers <math>a</math> such that <math>n | a - 1</math> is a submonoid of the monoid of all positive integers. | # For any positive integer <math>n</math>, '''prove that''' the set of positive integers <math>a</math> such that <math>n | a - 1</math> is a submonoid of the monoid of all positive integers. | ||
− | # Using the identity <math>(a^2 + b^2)(c^2 + d^2) = (ad + bc)^2 + (ac - bd)^2</math>, '''prove that''' the set of all integers that can be written as a sum of two squares forms a monoid under multiplication. | + | # Using the identity <math>(a^2 + b^2)(c^2 + d^2) = (ad + bc)^2 + (ac - bd)^2</math>, '''prove that''' the set of all integers that can be written as a sum of two squares of integers forms a monoid under multiplication. |
==Integers under addition== | ==Integers under addition== | ||
Line 32: | Line 32: | ||
# '''Prove that''' this monoid is not a group for <math>n > 1</math>. | # '''Prove that''' this monoid is not a group for <math>n > 1</math>. | ||
# '''Find''' all the idempotent elements in this monoid. In other words, find all the elements <math>a</math> satisfying <math>a^2 = a</math>. The solution depends, of course, on <math>n</math>. | # '''Find''' all the idempotent elements in this monoid. In other words, find all the elements <math>a</math> satisfying <math>a^2 = a</math>. The solution depends, of course, on <math>n</math>. | ||
− | # '''Prove that''' the number of <math>x</math> such that <math>x^2 = 1</math> in this monoid is 1 for <math>n = 1</math> and <math>n = 2</math>, 2 for <math>n = 4</math>, <math>n = 2p^k</math> and <math>n = p^k</math> where <math> | + | # '''NEEDS LOT OF THOUGHT''': '''Prove that''' the number of <math>x</math> such that <math>x^2 = 1</math> in this monoid is 1 for <math>n = 1</math> and <math>n = 2</math>, 2 for <math>n = 4</math>, <math>n = 2p^k</math> and <math>n = p^k</math> where <math>p</math> is an odd prime, and strictly greater than 2 otherwise. |
− | # '''Prove that''' the cancellative elements of this monoid form a subgroup, and these are the same as the elements <math>a</math> that are relatively prime to <math>n</math>. | + | # '''Prove that''' the cancellative elements of this monoid form a subgroup, and these are the same as the elements <math>a \in \{ 0,1,2, \dots, n - 1 \}</math> that are relatively prime to <math>n</math>. |
===Addition mod a real number=== | ===Addition mod a real number=== | ||
Line 39: | Line 39: | ||
Let <math>r</math> be a positive real number. Consider the set of all real numbers <math>x</math> such that <math>0 \le x < r</math>, and give this set an addition as follows: for <math>a,b</math> the sum is defined as the usual sum if <math>a + b < r</math>, and <math>a + b - r</math> otherwise. | Let <math>r</math> be a positive real number. Consider the set of all real numbers <math>x</math> such that <math>0 \le x < r</math>, and give this set an addition as follows: for <math>a,b</math> the sum is defined as the usual sum if <math>a + b < r</math>, and <math>a + b - r</math> otherwise. | ||
− | # '''Prove that''' with this addition, the set of numbers <math>\{ x \mid 0 \le x < r \}</math> forms an | + | # '''Prove that''' with this addition, the set of numbers <math>\{ x \mid 0 \le x < r \}</math> forms an abelian group. |
# '''Prove that''', when <math>r</math> is a positive integers, the group of integers mod <math>r</math> is a subgroup of this group. | # '''Prove that''', when <math>r</math> is a positive integers, the group of integers mod <math>r</math> is a subgroup of this group. | ||
Line 46: | Line 46: | ||
Let <math>r</math> be a positive real number. Consider the set of all real numbers <math>x</math> such that <math>0 \le x < r</math>, and give this set a multiplication as follows: for <math>a,b</math> the product is defined as the unique <math>s \in [0,r)</math> such that <math>ab = rn + s</math> for some integer <math>n</math>. In other words, the multiplication is defined by first doing the multiplication as real numbers and then reducing mod <math>r</math>. | Let <math>r</math> be a positive real number. Consider the set of all real numbers <math>x</math> such that <math>0 \le x < r</math>, and give this set a multiplication as follows: for <math>a,b</math> the product is defined as the unique <math>s \in [0,r)</math> such that <math>ab = rn + s</math> for some integer <math>n</math>. In other words, the multiplication is defined by first doing the multiplication as real numbers and then reducing mod <math>r</math>. | ||
− | # '''Prove that''' this multiplication gives a commutative magma. | + | # '''Prove that''' this multiplication gives a commutative magma. |
− | # '''Prove that''' this multiplication gives a cancellative semigroup if <math>r \le 1</math>. | + | # '''NEEDS SOME THOUGHT''': '''prove that''' this magma has a two-sided neutral element if and only if <math>r \ge 1</math>. |
− | # '''Prove that''' this multiplication does ''not'' give a monoid if <math>r > 1</math>: in particular, that it is ''not'' associative. Further, '''prove that''' the only associative element (an element such that every expression involving it associates) is 1. | + | # '''NEEDS SOME THOUGHT''': '''Prove that''' this multiplication gives a cancellative semigroup if <math>r \le 1</math>. |
+ | # '''NEEDS LOT OF THOUGHT''': '''Prove that''' this multiplication does ''not'' give a monoid if <math>r > 1</math>: in particular, that it is ''not'' associative. Further, '''prove that''' the only associative element (an element such that every expression involving it associates) is 1. | ||
# '''Prove that''' when <math>r</math> is a positive integer, the integers mod <math>r</math> form a submonoid of this magma. | # '''Prove that''' when <math>r</math> is a positive integer, the integers mod <math>r</math> form a submonoid of this magma. | ||
Line 54: | Line 55: | ||
# Let <math>S</math> be an infinite set. '''Prove that''' the set of all functions from <math>S</math> to <math>S</math> form a monoid under composition. Here, the product of two functions <math>f</math> and <math>g</math> is the function <math>f \circ g = x \mapsto f(g(x))</math>. We'll call this monoid <math>M</math>. | # Let <math>S</math> be an infinite set. '''Prove that''' the set of all functions from <math>S</math> to <math>S</math> form a monoid under composition. Here, the product of two functions <math>f</math> and <math>g</math> is the function <math>f \circ g = x \mapsto f(g(x))</math>. We'll call this monoid <math>M</math>. | ||
− | # '''Prove that''' the set of injective maps from <math>S</math> to <math>S</math> is a submonoid, the set of surjective maps from <math>S</math> to <math>S</math> is a submonoid, and the set of bijective maps from <math>S</math> to <math>S</math> is a subgroup (it is the group of all permutations on <math>S</math>, denoted <math>\operatorname{Sym}(S)</math>. | + | # '''Prove that''' the set of injective maps from <math>S</math> to <math>S</math> is a submonoid, the set of surjective maps from <math>S</math> to <math>S</math> is a submonoid, and the set of bijective maps from <math>S</math> to <math>S</math> is a subgroup (it is the group of all permutations on <math>S</math>, denoted <math>\operatorname{Sym}(S)</math>). |
# '''Prove that''' if <math>f:S \to S</math> is injective, then <math>f</math> is a left-cancellative element of the monoid of all functions under composition. | # '''Prove that''' if <math>f:S \to S</math> is injective, then <math>f</math> is a left-cancellative element of the monoid of all functions under composition. | ||
# '''NEEDS SOME THOUGHT''': '''Prove the converse''' statement: if <math>f:S \to S</math> is left-cancellative, then <math>f</math> is injective. | # '''NEEDS SOME THOUGHT''': '''Prove the converse''' statement: if <math>f:S \to S</math> is left-cancellative, then <math>f</math> is injective. | ||
Line 62: | Line 63: | ||
==Metric spaces and maps between them== | ==Metric spaces and maps between them== | ||
− | # Let <math>M</math> be the set of all functions <math>f:\R^2 \to \R^2</math> with the property that for any <math>x,y \in \R^2</math>, the distance between <math>f(x)</math> and <math>f(y)</math> is not greater than the distance between <math>x</math> and <math>y</math>. '''Prove that''' <math>M</math> is a monoid under function composition. | + | # Let <math>M</math> be the set of all functions <math>f:\R^2 \to \R^2</math> with the property that for any <math>x,y \in \R^2</math>, the distance between <math>f(x)</math> and <math>f(y)</math> is not greater than the distance between <math>x</math> and <math>y</math>. '''Prove that''' <math>M</math> is a monoid under function composition. (Such maps are termed [[topospaces:short map|short maps]]). |
# '''NEEDS SOME THOUGHT''': '''Find''' an element of <math>M</math> that gives a surjective map that is ''not'' injective. | # '''NEEDS SOME THOUGHT''': '''Find''' an element of <math>M</math> that gives a surjective map that is ''not'' injective. | ||
− | # '''Prove that''' the group of | + | # '''Prove that''' the group of isometries of <math>\R^2</math> is a subgroup of <math>M</math>. |
+ | # '''Prove that''' the group of isometries of <math>\R^2</math> is the unique largest subgroup of <math>M</math>. ''Note: You need to be careful here. There do exist short maps that are bijective, and hence, invertible, but are not isometries. The question here asks you to prove that for a short map to be invertible and for its inverse to also be a short map, the map must be an isometry.'' | ||
+ | # '''Find''' the condition on a similarity <math>\R^2 \to \R^2</math> for it to be a short map. | ||
==Weird examples of groups and quasigroups== | ==Weird examples of groups and quasigroups== | ||
Line 70: | Line 73: | ||
===Groups coming from groups=== | ===Groups coming from groups=== | ||
− | # Let <math>G</math> be an | + | # Let <math>G</math> be an abelian group with binary operation <math>+</math>. Pick an element <math>a \in G</math>, and define a new binary operation on <math>G</math> by: <math>x * y := x + y + a</math>. '''Prove that''' <math>G</math> is an abelian group under <math>*</math>, and '''find''' the identity element and inverse map. |
− | # Let <math>n</math> be an odd positive integer. Define the following binary operation <math>+_n</math> on <math>\R</math>: <math>x +_n y := (x^n + y^n)^{1/n}</math>. '''Prove that''' <math>\R</math> is an | + | # Let <math>n</math> be an odd positive integer. Define the following binary operation <math>+_n</math> on <math>\R</math>: <math>x +_n y := (x^n + y^n)^{1/n}</math>. '''Prove that''' <math>\R</math> is an abelian group under <math>+_n</math>. |
===Quasigroups coming from groups=== | ===Quasigroups coming from groups=== | ||
Line 77: | Line 80: | ||
# The ''arithmetic mean'' quasigroup: Define the following binary operation <math>*</math> on <math>\R</math>: <math>x * y = (x + y)/2</math>. '''Prove that''' <math>\R</math> has the structure of a commutative quasigroup where every element is idempotent: <math>x * x = x</math> for every <math>x \in \R</math>. | # The ''arithmetic mean'' quasigroup: Define the following binary operation <math>*</math> on <math>\R</math>: <math>x * y = (x + y)/2</math>. '''Prove that''' <math>\R</math> has the structure of a commutative quasigroup where every element is idempotent: <math>x * x = x</math> for every <math>x \in \R</math>. | ||
# The ''ratio'' quasigroup: Let <math>G</math> be any group. Define a binary operation <math>*</math> on <math>G</math> given by <math>x * y = xy^{-1}</math>. '''Prove that''' <math>G</math> is an algebra loop under <math>*</math>. '''Find''' all the right-associative elements for this operation. Further, '''prove that''' the subloops of <math>G</math> with this binary operation, are the same as its subgroups. | # The ''ratio'' quasigroup: Let <math>G</math> be any group. Define a binary operation <math>*</math> on <math>G</math> given by <math>x * y = xy^{-1}</math>. '''Prove that''' <math>G</math> is an algebra loop under <math>*</math>. '''Find''' all the right-associative elements for this operation. Further, '''prove that''' the subloops of <math>G</math> with this binary operation, are the same as its subgroups. | ||
− | # A quasigroup <math>(S,*)</math> is termed a [[medial quasigroup]] if <math>(x * y) * (z * w) = (x * z) * (y * w)</math> for all <math>x,y,z,w \in S</math>. '''Prove that''' the arithmetic mean quasigroup is a medial quasigroup. Further, '''prove that''' the ratio quasigroup of an | + | # A quasigroup <math>(S,*)</math> is termed a [[medial quasigroup]] if <math>(x * y) * (z * w) = (x * z) * (y * w)</math> for all <math>x,y,z,w \in S</math>. '''Prove that''' the arithmetic mean quasigroup is a medial quasigroup. Further, '''prove that''' the ratio quasigroup of an abelian group is a medial quasigroup. |
{{tour-special| | {{tour-special| |
Latest revision as of 00:19, 21 February 2010
This page is a Examples peek page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Mind's eye test two (beginners)| UP: Introduction two | NEXT: Interdisciplinary problems two (beginners)
PREVIOUS SECTION Examples peek: Examples peek one|NEXT SECTION Examples peek: Examples peek three
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part
The page develops some examples of groups, monoids and other related structures in different contexts. The page can be skipped without any loss and content in this page will not be referred to except in future Examples peek pages. This page develops examples originally looked at in Examples peek one.
Contents
Integers under multiplication
- Prove that the rational numbers, under multiplication, form a monoid. Further, prove that the nonzero rational numbers form a subgroup of this monoid.
- Prove that the positive integers, under multiplication, form a cancellative monoid.
- For any positive integer , prove that the set of positive integers such that is a submonoid of the monoid of all positive integers.
- Using the identity , prove that the set of all integers that can be written as a sum of two squares of integers forms a monoid under multiplication.
Integers under addition
- Prove that the nonnegative integers form a monoid under addition.
- Prove that for any positive integer , the set of integers , along with 0, form a submonoid of this monoid.
- NEEDS LOT OF THOUGHT: Let be positive integers whose greatest common divisor is 1. Prove that the set of elements of the form , where are nonnegative integers, is a submonoid of the monoid of nonnegative integers. Further, prove that this submonoid is cofinite: there are only finitely many nonnegative integers not in this submonoid.
Modular arithmetic
Multiplication mod an integer
In examples peek one, we defined the additive group of integers mod , for any positive integer . Now, we define the multiplicative monoid of integers mod , for any positive integer .
- For a positive integer , consider the set . Define a multiplication on the set by the following rule: multiply them as integers, and then take the remainder of the product mod . Prove that with this multiplication, we get a monoid.
- Prove that this monoid is not a group for .
- Find all the idempotent elements in this monoid. In other words, find all the elements satisfying . The solution depends, of course, on .
- NEEDS LOT OF THOUGHT: Prove that the number of such that in this monoid is 1 for and , 2 for , and where is an odd prime, and strictly greater than 2 otherwise.
- Prove that the cancellative elements of this monoid form a subgroup, and these are the same as the elements that are relatively prime to .
Addition mod a real number
Let be a positive real number. Consider the set of all real numbers such that , and give this set an addition as follows: for the sum is defined as the usual sum if , and otherwise.
- Prove that with this addition, the set of numbers forms an abelian group.
- Prove that, when is a positive integers, the group of integers mod is a subgroup of this group.
Multiplication mod a real number
Let be a positive real number. Consider the set of all real numbers such that , and give this set a multiplication as follows: for the product is defined as the unique such that for some integer . In other words, the multiplication is defined by first doing the multiplication as real numbers and then reducing mod .
- Prove that this multiplication gives a commutative magma.
- NEEDS SOME THOUGHT: prove that this magma has a two-sided neutral element if and only if .
- NEEDS SOME THOUGHT: Prove that this multiplication gives a cancellative semigroup if .
- NEEDS LOT OF THOUGHT: Prove that this multiplication does not give a monoid if : in particular, that it is not associative. Further, prove that the only associative element (an element such that every expression involving it associates) is 1.
- Prove that when is a positive integer, the integers mod form a submonoid of this magma.
Permutations and functions
- Let be an infinite set. Prove that the set of all functions from to form a monoid under composition. Here, the product of two functions and is the function . We'll call this monoid .
- Prove that the set of injective maps from to is a submonoid, the set of surjective maps from to is a submonoid, and the set of bijective maps from to is a subgroup (it is the group of all permutations on , denoted ).
- Prove that if is injective, then is a left-cancellative element of the monoid of all functions under composition.
- NEEDS SOME THOUGHT: Prove the converse statement: if is left-cancellative, then is injective.
- (For those who know the Cantor-Bernstein-Schroeder theorem) Prove that the left-invertible elements in are precisely the injective maps.
- Formulate and prove analogous statements related surjective maps, right-cancellative elements and right-invertible elements.
Metric spaces and maps between them
- Let be the set of all functions with the property that for any , the distance between and is not greater than the distance between and . Prove that is a monoid under function composition. (Such maps are termed short maps).
- NEEDS SOME THOUGHT: Find an element of that gives a surjective map that is not injective.
- Prove that the group of isometries of is a subgroup of .
- Prove that the group of isometries of is the unique largest subgroup of . Note: You need to be careful here. There do exist short maps that are bijective, and hence, invertible, but are not isometries. The question here asks you to prove that for a short map to be invertible and for its inverse to also be a short map, the map must be an isometry.
- Find the condition on a similarity for it to be a short map.
Weird examples of groups and quasigroups
Groups coming from groups
- Let be an abelian group with binary operation . Pick an element , and define a new binary operation on by: . Prove that is an abelian group under , and find the identity element and inverse map.
- Let be an odd positive integer. Define the following binary operation on : . Prove that is an abelian group under .
Quasigroups coming from groups
- The arithmetic mean quasigroup: Define the following binary operation on : . Prove that has the structure of a commutative quasigroup where every element is idempotent: for every .
- The ratio quasigroup: Let be any group. Define a binary operation on given by . Prove that is an algebra loop under . Find all the right-associative elements for this operation. Further, prove that the subloops of with this binary operation, are the same as its subgroups.
- A quasigroup is termed a medial quasigroup if for all . Prove that the arithmetic mean quasigroup is a medial quasigroup. Further, prove that the ratio quasigroup of an abelian group is a medial quasigroup.
This page is a Examples peek page, part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Mind's eye test two (beginners)| UP: Introduction two | NEXT: Interdisciplinary problems two (beginners)
PREVIOUS SECTION Examples peek: Examples peek one|NEXT SECTION Examples peek: Examples peek three
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part