Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Free magma"

(blah)
 
m (Added Categories)
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
 
*The set <math>M_1(X)</math> is the set <math>X \times \{0\}</math>.
 
*The set <math>M_1(X)</math> is the set <math>X \times \{0\}</math>.
 
*For <math>n>1</math>, the set <math>M_n(X)</math> is defined as
 
*For <math>n>1</math>, the set <math>M_n(X)</math> is defined as
−
<cmath> M_n = \bigcup_{i=1}^n M_i \times M_{n-i} \times \{i\} . </cmath>
+
<cmath> M_n = \bigcup_{i=1}^{n-1} M_i \times M_{n-i} \times \{i\} . </cmath>
 
*The set <math>M(X)</math> is the union of the sets <math>M_n(X)</math>.
 
*The set <math>M(X)</math> is the union of the sets <math>M_n(X)</math>.
  
Line 46: Line 46:
  
 
[[Category:Abstract algebra]]
 
[[Category:Abstract algebra]]
 +
[[Category:Mathematics]]

Latest revision as of 17:34, 28 September 2024

A free magma is magma structure that is as general as possible—a magma generated from an initial set with no constraints or relations.

Construction

The free magma generated from a set $X$ is constructed as follows.

  • The set $M_1(X)$ is the set $X \times \{0\}$.
  • For $n>1$, the set $M_n(X)$ is defined as

\[M_n = \bigcup_{i=1}^{n-1} M_i \times M_{n-i} \times \{i\} .\]

  • The set $M(X)$ is the union of the sets $M_n(X)$.

It can be seen from induction on the sets $M_n(X)$ that for any $w\in M(X)$, the integer $n$ such that $x \in M_n(X)$ is unique. This is called the length of $x$; it is sometimes denoted $l(x)$.

Let $x$ and $y$ be elements of $M(X)$. The element $(x,y,l(x))$ is called the composition of $x$ and $y$; it is denoted multiplicatively.

The set $M(X)$ under the law of composition $(x,y) \mapsto xy$ is called the free magma generated by $X$.

The rest of this article details properties useful by extension to free groups and free monoids.

Constructive properties

Proposition 1. Let $X$ be a set, let $S$ be a magma, and let $f : X \to S$ be a function. Then $f$ may be extended uniquely to $M(X)$ in such a way that the extended mapping is a magma homomorphism.

Proof. We prove by induction on $n$ that for all integers $n$, there is a unique extension $f_n$ of $f$ to $\bigcup_{i=1}^n M_n(X)$ such that, for all $x,y$ in $M$ satisfying $l(x) + l(y) \le n$, $f(xy) = f(x)f(y)$. For $n=1$, this is vacuously true. Now, supposing that this statement holds for integers less than or equal to $n$, we note that every element $w$ of $M_n(X)$ is uniquely defined as the composition of two elements $x,y$ of $M(X)$ such that $l(x) + l(y) \le n$; in particular, $l(x),l(y) <n$; thus we can and must define $f(w)$ as $f(x)f(y)$; for elements $w$ of length less than $n$, $f(w)$ must be defined as for $\bigcup_{i=1}^{n-1} M_i(X)$, by inductive hypothesis.

Now, for any $x\in M(X)$, we define $g(x)$ to be $f_{l(x)}(x)$. This is then a homomorphism from $M(X)$ into $S$, since $f_{l(x)}(x) = f_n(x)$, for all $n\ge l(x)$, and it is the only possible one. $\blacksquare$

Let $X$ and $Y$ be sets, $f : X \to Y$ a function; this is also a function $f : X \to M(Y)$. The unique homomorphic extension of $f$ to $M(X)$ is denoted $M(f)$.

Proposition 2. If $f : X \to Y$ is injective (or surjective), then so is $M(f)$.

The proof is analogous to the proof of the first proposition.

Relations on a free magma; Universal property

Let $I$ be an index set, and $(u_i,v_i)_{i\in I}$ a set of ordered pairs of elements of a free magma $M(X)$. The quotient magma under the equivalence relation compatible with $M(X)$ generated by the pairs $(u_i,v_i)_{i\in I}$ is called the magma generated by $X$ and the relators $(u_i,v_i)$. Let $R$ denote this equivalence relation, and let $h$ be the canonical homomorphism from $M(X)$ to $M(X)/R$. Then $h(X)$ generates $M(X)/R$.

Proposition 3. Every magma is isomorphic to a magma generated by a magma generated by a set under a set of relators.

Proof. Let $S$ be a magma, and $X$ a generating subset of $S$. Let $f$ be the unique homomorphic extension of the identity mapping on $X$ to $M(X)$, and let $(u_{i},v_i)_{i\in I}$ be a generating set of the equivalence relation $R(x,y)$ defined as $f(x) = f(y)$. Then $S$ is isomorphic to the magma generated by $X$ with the relators $(u_{i},v_i)_{i\in I}$. $\blacksquare$

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Free_magma&oldid=228527"