Mixing
Is there a name for an associative algebraic structure in which everything is irreducible?
$begingroup$
Let $A$ be a set and $ast$ a binary operator on that set. Let us suppose that $(A,ast)$ satisfies the following axioms:
- For all $x,y,z in A$, $x ast (y ast z) = (x ast y) ast z$
- For all $x,y,z in A$, if $z = x ast y$, then $z = x$ or $z = y$
The first property says that the structure is a semigroup and the second says that all elements are irreducible. Moreover, this semigroup is a idempotent.
We can induce a weak order on $A$ by saying $x < y$ if $x ast y = x$ and $y ast x = x$. To prove transitivity, just note that $x ast (y ast z) = (x ast y) ast z$ implies $x ast z = z$ if $x < y$ and $y < z$. Do the operations in reverse to show $z ast x = z$.
We can also do the reverse by defining $x ast y$ as $x$ unless $y < x$. This is not an isomorphism though.
Does this algebraic structure have a name?
abstract-algebra order-theory semigroups idempotents associativity
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
$endgroup$
|
show 1 more comment
$begingroup$
Let $A$ be a set and $ast$ a binary operator on that set. Let us suppose that $(A,ast)$ satisfies the following axioms:
- For all $x,y,z in A$, $x ast (y ast z) = (x ast y) ast z$
- For all $x,y,z in A$, if $z = x ast y$, then $z = x$ or $z = y$
The first property says that the structure is a semigroup and the second says that all elements are irreducible. Moreover, this semigroup is a idempotent.
We can induce a weak order on $A$ by saying $x < y$ if $x ast y = x$ and $y ast x = x$. To prove transitivity, just note that $x ast (y ast z) = (x ast y) ast z$ implies $x ast z = z$ if $x < y$ and $y < z$. Do the operations in reverse to show $z ast x = z$.
We can also do the reverse by defining $x ast y$ as $x$ unless $y < x$. This is not an isomorphism though.
Does this algebraic structure have a name?
abstract-algebra order-theory semigroups idempotents associativity
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
$endgroup$
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05
|
show 1 more comment
$begingroup$
Let $A$ be a set and $ast$ a binary operator on that set. Let us suppose that $(A,ast)$ satisfies the following axioms:
- For all $x,y,z in A$, $x ast (y ast z) = (x ast y) ast z$
- For all $x,y,z in A$, if $z = x ast y$, then $z = x$ or $z = y$
The first property says that the structure is a semigroup and the second says that all elements are irreducible. Moreover, this semigroup is a idempotent.
We can induce a weak order on $A$ by saying $x < y$ if $x ast y = x$ and $y ast x = x$. To prove transitivity, just note that $x ast (y ast z) = (x ast y) ast z$ implies $x ast z = z$ if $x < y$ and $y < z$. Do the operations in reverse to show $z ast x = z$.
We can also do the reverse by defining $x ast y$ as $x$ unless $y < x$. This is not an isomorphism though.
Does this algebraic structure have a name?
abstract-algebra order-theory semigroups idempotents associativity
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
$endgroup$
Let $A$ be a set and $ast$ a binary operator on that set. Let us suppose that $(A,ast)$ satisfies the following axioms:
- For all $x,y,z in A$, $x ast (y ast z) = (x ast y) ast z$
- For all $x,y,z in A$, if $z = x ast y$, then $z = x$ or $z = y$
The first property says that the structure is a semigroup and the second says that all elements are irreducible. Moreover, this semigroup is a idempotent.
We can induce a weak order on $A$ by saying $x < y$ if $x ast y = x$ and $y ast x = x$. To prove transitivity, just note that $x ast (y ast z) = (x ast y) ast z$ implies $x ast z = z$ if $x < y$ and $y < z$. Do the operations in reverse to show $z ast x = z$.
We can also do the reverse by defining $x ast y$ as $x$ unless $y < x$. This is not an isomorphism though.
Does this algebraic structure have a name?
abstract-algebra order-theory semigroups idempotents associativity
abstract-algebra order-theory semigroups idempotents associativity
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
edited Jan 18 at 19:02
PyRulez
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
asked Jan 18 at 17:48
PyRulezPyRulez
4,94622470
4,94622470
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05
|
show 1 more comment
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
I don't know what these are called, but it's worth noting that (unsurprisingly) they have an order-theoretic description as well. Specifically, there is a tight connection between these semigroups and pairs of (partial) preorders satisfying a kind of "antiduality" condition.
Suppose $(A,*)$ is a semigroup of this type. Consider the relation $trianglelefteq_{right}$ on $A$ defined by $$xtrianglelefteq_{right} yiff x*y=y$$ (this is a weakening of the relation you define). I claim that this is in fact a partial preorder on $A$ (= reflexive and transitive, but elements don't need to be comparable and perhaps $xtrianglelefteq_{right} y,ytrianglelefteq_{right} xnotrightarrow x=y$).
For efficiency, I'll refer to partial preorders as just "preorders" for the rest of this answer.
Reflexivity is clear, so we just have to show transitivity.
To see this, let $x*y=y$ and $y*z=z$. Since $x*zin{x,z}$, the only two possibilities are $x*z=z$ - in which case we're done - or $x*z=x$. So suppose $x*z=x$; I'll show that $x=z$ (and so $x*z=z$ as desired). But this is easy: we have $x*(y*z)=x*z=x$ and $(x*y)*z=y*z=z$.
The "dual" relation $$xtrianglelefteq_{left}yiff y*x=y$$ is similarly a preorder on $A$. However, we also have $$xtrianglelefteq_{left} yiff (x=ymbox{ or }ynottrianglelefteq_{right}x)quadmbox{and}quad xtrianglelefteq_{right} yiff (x=ymbox{ or }ynottrianglelefteq_{left}x).$$ We can now make the following observation:
There is a natural correspondence between "double-preorders" satisfying the above conditions and semigroups satisfying your conditions.
The only piece of this observation left to prove is that from such a double-preorder we can recover the desired type of semigroup. Given $(A,preccurlyeq_1,preccurlyeq_2)$ appropriate, let $$x*y=yiff xpreccurlyeq_1y, quad x*y=xiff ypreccurlyeq_2x.$$ This is clearly well-defined, and it's a bit tedious but not hard to check that it is associative as well. Here's part of the proof:
Suppose that $xpreccurlyeq_1y$ and $ypreccurlyeq_2z$. Then we have $$(x*y)*z=y*z=zquadmbox{and}quad x*(y*z)=x*z.$$ For associativity to fail, we would need to have $x*z=x$ and $xnot=z$, but this would mean $zpreccurlyeq_2x$. Transitivity of $preccurlyeq_2$ then gives $ypreccurlyeq_2x$, so since $xpreccurlyeq_1y$ we have $x=y$. But then $x*z=y*z=z$, so $x=z$, a contradiction.
Moreover, it's not hard to show that this correspondence is in fact 1-1. So we have our order-theoretic description.
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
$endgroup$
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078563%2fis-there-a-name-for-an-associative-algebraic-structure-in-which-everything-is-ir%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I don't know what these are called, but it's worth noting that (unsurprisingly) they have an order-theoretic description as well. Specifically, there is a tight connection between these semigroups and pairs of (partial) preorders satisfying a kind of "antiduality" condition.
Suppose $(A,*)$ is a semigroup of this type. Consider the relation $trianglelefteq_{right}$ on $A$ defined by $$xtrianglelefteq_{right} yiff x*y=y$$ (this is a weakening of the relation you define). I claim that this is in fact a partial preorder on $A$ (= reflexive and transitive, but elements don't need to be comparable and perhaps $xtrianglelefteq_{right} y,ytrianglelefteq_{right} xnotrightarrow x=y$).
For efficiency, I'll refer to partial preorders as just "preorders" for the rest of this answer.
Reflexivity is clear, so we just have to show transitivity.
To see this, let $x*y=y$ and $y*z=z$. Since $x*zin{x,z}$, the only two possibilities are $x*z=z$ - in which case we're done - or $x*z=x$. So suppose $x*z=x$; I'll show that $x=z$ (and so $x*z=z$ as desired). But this is easy: we have $x*(y*z)=x*z=x$ and $(x*y)*z=y*z=z$.
The "dual" relation $$xtrianglelefteq_{left}yiff y*x=y$$ is similarly a preorder on $A$. However, we also have $$xtrianglelefteq_{left} yiff (x=ymbox{ or }ynottrianglelefteq_{right}x)quadmbox{and}quad xtrianglelefteq_{right} yiff (x=ymbox{ or }ynottrianglelefteq_{left}x).$$ We can now make the following observation:
There is a natural correspondence between "double-preorders" satisfying the above conditions and semigroups satisfying your conditions.
The only piece of this observation left to prove is that from such a double-preorder we can recover the desired type of semigroup. Given $(A,preccurlyeq_1,preccurlyeq_2)$ appropriate, let $$x*y=yiff xpreccurlyeq_1y, quad x*y=xiff ypreccurlyeq_2x.$$ This is clearly well-defined, and it's a bit tedious but not hard to check that it is associative as well. Here's part of the proof:
Suppose that $xpreccurlyeq_1y$ and $ypreccurlyeq_2z$. Then we have $$(x*y)*z=y*z=zquadmbox{and}quad x*(y*z)=x*z.$$ For associativity to fail, we would need to have $x*z=x$ and $xnot=z$, but this would mean $zpreccurlyeq_2x$. Transitivity of $preccurlyeq_2$ then gives $ypreccurlyeq_2x$, so since $xpreccurlyeq_1y$ we have $x=y$. But then $x*z=y*z=z$, so $x=z$, a contradiction.
Moreover, it's not hard to show that this correspondence is in fact 1-1. So we have our order-theoretic description.
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
$endgroup$
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
add a comment |
$begingroup$
I don't know what these are called, but it's worth noting that (unsurprisingly) they have an order-theoretic description as well. Specifically, there is a tight connection between these semigroups and pairs of (partial) preorders satisfying a kind of "antiduality" condition.
Suppose $(A,*)$ is a semigroup of this type. Consider the relation $trianglelefteq_{right}$ on $A$ defined by $$xtrianglelefteq_{right} yiff x*y=y$$ (this is a weakening of the relation you define). I claim that this is in fact a partial preorder on $A$ (= reflexive and transitive, but elements don't need to be comparable and perhaps $xtrianglelefteq_{right} y,ytrianglelefteq_{right} xnotrightarrow x=y$).
For efficiency, I'll refer to partial preorders as just "preorders" for the rest of this answer.
Reflexivity is clear, so we just have to show transitivity.
To see this, let $x*y=y$ and $y*z=z$. Since $x*zin{x,z}$, the only two possibilities are $x*z=z$ - in which case we're done - or $x*z=x$. So suppose $x*z=x$; I'll show that $x=z$ (and so $x*z=z$ as desired). But this is easy: we have $x*(y*z)=x*z=x$ and $(x*y)*z=y*z=z$.
The "dual" relation $$xtrianglelefteq_{left}yiff y*x=y$$ is similarly a preorder on $A$. However, we also have $$xtrianglelefteq_{left} yiff (x=ymbox{ or }ynottrianglelefteq_{right}x)quadmbox{and}quad xtrianglelefteq_{right} yiff (x=ymbox{ or }ynottrianglelefteq_{left}x).$$ We can now make the following observation:
There is a natural correspondence between "double-preorders" satisfying the above conditions and semigroups satisfying your conditions.
The only piece of this observation left to prove is that from such a double-preorder we can recover the desired type of semigroup. Given $(A,preccurlyeq_1,preccurlyeq_2)$ appropriate, let $$x*y=yiff xpreccurlyeq_1y, quad x*y=xiff ypreccurlyeq_2x.$$ This is clearly well-defined, and it's a bit tedious but not hard to check that it is associative as well. Here's part of the proof:
Suppose that $xpreccurlyeq_1y$ and $ypreccurlyeq_2z$. Then we have $$(x*y)*z=y*z=zquadmbox{and}quad x*(y*z)=x*z.$$ For associativity to fail, we would need to have $x*z=x$ and $xnot=z$, but this would mean $zpreccurlyeq_2x$. Transitivity of $preccurlyeq_2$ then gives $ypreccurlyeq_2x$, so since $xpreccurlyeq_1y$ we have $x=y$. But then $x*z=y*z=z$, so $x=z$, a contradiction.
Moreover, it's not hard to show that this correspondence is in fact 1-1. So we have our order-theoretic description.
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
$endgroup$
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
add a comment |
$begingroup$
I don't know what these are called, but it's worth noting that (unsurprisingly) they have an order-theoretic description as well. Specifically, there is a tight connection between these semigroups and pairs of (partial) preorders satisfying a kind of "antiduality" condition.
Suppose $(A,*)$ is a semigroup of this type. Consider the relation $trianglelefteq_{right}$ on $A$ defined by $$xtrianglelefteq_{right} yiff x*y=y$$ (this is a weakening of the relation you define). I claim that this is in fact a partial preorder on $A$ (= reflexive and transitive, but elements don't need to be comparable and perhaps $xtrianglelefteq_{right} y,ytrianglelefteq_{right} xnotrightarrow x=y$).
For efficiency, I'll refer to partial preorders as just "preorders" for the rest of this answer.
Reflexivity is clear, so we just have to show transitivity.
To see this, let $x*y=y$ and $y*z=z$. Since $x*zin{x,z}$, the only two possibilities are $x*z=z$ - in which case we're done - or $x*z=x$. So suppose $x*z=x$; I'll show that $x=z$ (and so $x*z=z$ as desired). But this is easy: we have $x*(y*z)=x*z=x$ and $(x*y)*z=y*z=z$.
The "dual" relation $$xtrianglelefteq_{left}yiff y*x=y$$ is similarly a preorder on $A$. However, we also have $$xtrianglelefteq_{left} yiff (x=ymbox{ or }ynottrianglelefteq_{right}x)quadmbox{and}quad xtrianglelefteq_{right} yiff (x=ymbox{ or }ynottrianglelefteq_{left}x).$$ We can now make the following observation:
There is a natural correspondence between "double-preorders" satisfying the above conditions and semigroups satisfying your conditions.
The only piece of this observation left to prove is that from such a double-preorder we can recover the desired type of semigroup. Given $(A,preccurlyeq_1,preccurlyeq_2)$ appropriate, let $$x*y=yiff xpreccurlyeq_1y, quad x*y=xiff ypreccurlyeq_2x.$$ This is clearly well-defined, and it's a bit tedious but not hard to check that it is associative as well. Here's part of the proof:
Suppose that $xpreccurlyeq_1y$ and $ypreccurlyeq_2z$. Then we have $$(x*y)*z=y*z=zquadmbox{and}quad x*(y*z)=x*z.$$ For associativity to fail, we would need to have $x*z=x$ and $xnot=z$, but this would mean $zpreccurlyeq_2x$. Transitivity of $preccurlyeq_2$ then gives $ypreccurlyeq_2x$, so since $xpreccurlyeq_1y$ we have $x=y$. But then $x*z=y*z=z$, so $x=z$, a contradiction.
Moreover, it's not hard to show that this correspondence is in fact 1-1. So we have our order-theoretic description.
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
$endgroup$
I don't know what these are called, but it's worth noting that (unsurprisingly) they have an order-theoretic description as well. Specifically, there is a tight connection between these semigroups and pairs of (partial) preorders satisfying a kind of "antiduality" condition.
Suppose $(A,*)$ is a semigroup of this type. Consider the relation $trianglelefteq_{right}$ on $A$ defined by $$xtrianglelefteq_{right} yiff x*y=y$$ (this is a weakening of the relation you define). I claim that this is in fact a partial preorder on $A$ (= reflexive and transitive, but elements don't need to be comparable and perhaps $xtrianglelefteq_{right} y,ytrianglelefteq_{right} xnotrightarrow x=y$).
For efficiency, I'll refer to partial preorders as just "preorders" for the rest of this answer.
Reflexivity is clear, so we just have to show transitivity.
To see this, let $x*y=y$ and $y*z=z$. Since $x*zin{x,z}$, the only two possibilities are $x*z=z$ - in which case we're done - or $x*z=x$. So suppose $x*z=x$; I'll show that $x=z$ (and so $x*z=z$ as desired). But this is easy: we have $x*(y*z)=x*z=x$ and $(x*y)*z=y*z=z$.
The "dual" relation $$xtrianglelefteq_{left}yiff y*x=y$$ is similarly a preorder on $A$. However, we also have $$xtrianglelefteq_{left} yiff (x=ymbox{ or }ynottrianglelefteq_{right}x)quadmbox{and}quad xtrianglelefteq_{right} yiff (x=ymbox{ or }ynottrianglelefteq_{left}x).$$ We can now make the following observation:
There is a natural correspondence between "double-preorders" satisfying the above conditions and semigroups satisfying your conditions.
The only piece of this observation left to prove is that from such a double-preorder we can recover the desired type of semigroup. Given $(A,preccurlyeq_1,preccurlyeq_2)$ appropriate, let $$x*y=yiff xpreccurlyeq_1y, quad x*y=xiff ypreccurlyeq_2x.$$ This is clearly well-defined, and it's a bit tedious but not hard to check that it is associative as well. Here's part of the proof:
Suppose that $xpreccurlyeq_1y$ and $ypreccurlyeq_2z$. Then we have $$(x*y)*z=y*z=zquadmbox{and}quad x*(y*z)=x*z.$$ For associativity to fail, we would need to have $x*z=x$ and $xnot=z$, but this would mean $zpreccurlyeq_2x$. Transitivity of $preccurlyeq_2$ then gives $ypreccurlyeq_2x$, so since $xpreccurlyeq_1y$ we have $x=y$. But then $x*z=y*z=z$, so $x=z$, a contradiction.
Moreover, it's not hard to show that this correspondence is in fact 1-1. So we have our order-theoretic description.
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
edited Jan 19 at 4:29
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
answered Jan 18 at 19:35
Noah SchweberNoah Schweber
126k10150288
126k10150288
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
add a comment |
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
Cool, interesting construction. I do have a question though. What do you mean by "combinatorial version"? The only difference I see is that your construction has two binary relations and mine has one binary function.
$endgroup$
– PyRulez
Jan 19 at 0:19
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
@PyRulez I was just referring at the relations vs. functions issue. Intuitively - to me at least - relational structures (especially when the relation is a preorder or similar) are combinatorial and functional structures are algebraic (certainly that second part is reflected by terminology in universal algebra). But it's just flavor text, ignore it.
$endgroup$
– Noah Schweber
Jan 19 at 1:15
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
okay, just wondering what you meant by it. I figured it wasn't super important since it was in scare quotes.
$endgroup$
– PyRulez
Jan 19 at 3:50
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
$begingroup$
@PyRulez I've edited it to be more on point.
$endgroup$
– Noah Schweber
Jan 19 at 4:22
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078563%2fis-there-a-name-for-an-associative-algebraic-structure-in-which-everything-is-ir%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Atom is a synonym for irreducible. Rings with no atoms are called atomless by some authors. Domains in which nonzero nonunits have some factorization into atoms are called atomic domains.. The terminology is usually credited to Paul M. Cohn (but it may well be older).
$endgroup$
– Bill Dubuque
Jan 18 at 18:02
$begingroup$
Unless I'm missing something, your claim "$x$ and $y$ commute iff $x=y$" is false: given a linear order $(A,trianglelefteq)$ let $a*b=max_{trianglelefteq}{a,b}$. Then $(A,*)$ is a commutative semiring satisfying $forall x,y(x*yin{x,y})$, hence a structure of the type you describe, but $A$ could have more than one element.
$endgroup$
– Noah Schweber
Jan 18 at 18:58
$begingroup$
@NoahSchweber brain derp, that was definitely false. It has been removed.
$endgroup$
– PyRulez
Jan 18 at 19:03
$begingroup$
@BillDubuque in this, not only does everything factor as a atoms, everything is an atom. Also, it can't be a ring since it only has one operator.
$endgroup$
– PyRulez
Jan 18 at 19:06
$begingroup$
@PyRulez The point was simply to give you more keywords which may help you in searching (the terminology is also used for monoids and semigroups).
$endgroup$
– Bill Dubuque
Jan 18 at 21:05