In a Cayley table, which Group axioms fail when an entry appears twice in a row or a column?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
In a Cayley table, which Group axioms fail when an entry appears twice in a row or a column?
It's obviously not the Closure axiom, and after some inspection, I believe the Inverses axiom does fail.
However, I'm not so sure how to show whether or not the two other axioms fail (Identity and Associativity).
group-theory axioms semigroups monoid cayley-table
add a comment |Â
up vote
5
down vote
favorite
In a Cayley table, which Group axioms fail when an entry appears twice in a row or a column?
It's obviously not the Closure axiom, and after some inspection, I believe the Inverses axiom does fail.
However, I'm not so sure how to show whether or not the two other axioms fail (Identity and Associativity).
group-theory axioms semigroups monoid cayley-table
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
In a Cayley table, which Group axioms fail when an entry appears twice in a row or a column?
It's obviously not the Closure axiom, and after some inspection, I believe the Inverses axiom does fail.
However, I'm not so sure how to show whether or not the two other axioms fail (Identity and Associativity).
group-theory axioms semigroups monoid cayley-table
In a Cayley table, which Group axioms fail when an entry appears twice in a row or a column?
It's obviously not the Closure axiom, and after some inspection, I believe the Inverses axiom does fail.
However, I'm not so sure how to show whether or not the two other axioms fail (Identity and Associativity).
group-theory axioms semigroups monoid cayley-table
edited Aug 25 at 23:57
Shaun
7,43692972
7,43692972
asked Aug 25 at 22:42
Stephen
1,2771819
1,2771819
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
9
down vote
accepted
None of the properties fail automatically
For any group property, you can always find a Cayley table where there's a duplicate entry and yet that property still holds. Here are examples for each:
Associativity can still hold. $$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$
Identity can still hold. (Same example.)
$$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$Inverses can still hold. (Here, $a$ and $b$ are inverses of each other.)$$beginarrayccc & e & a & b \hline e & e & a & b\a & a & a & e \b & b & e & aendarray$$
However, either associativity fails or inverses fail.
If there's a duplicate row, then $ab=ac$ for some $bneq c$. Suppose the operator has inverses and associativity. Then we get $a^-1ab = a^-1ac$ so that $b=c$â contradicting our assumption that $bneq c$.
So if there's a duplicate row, the operator can either be associative (as shown above), or have inverses (as shown above), but never both.
For confirmation, note that in the example tables above, #1 is associative but not invertible because of 0, and #3 is invertible but not associative because $(bb)a = aa = a$ but $b(ba) = be = b$.)
Diagram
Groups can't have repeat entries. Therefore, if a table has repeat entries, it's not a group. If it's not a group, then it's not in the green region of this diagram. Visually, you can see that such a table can't be both associative and have inverses at the same time. And you can show that there exist tables with duplicate rows that belong to any other non-green region of this diagram.
add a comment |Â
up vote
3
down vote
If you have a monoid, an entry can appear twice in a row or a column. However, the axioms "Identity" and "Associativity" are satisfied. Suppose now that $xa = xb$ with $a not= b$. Then $x$ cannot have an inverse, since otherwise $xa = xb$ implies $x^-1xa = x^-1xb$, that is, $a = b$.
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
add a comment |Â
up vote
1
down vote
Update: The proof I gave that you can't have inverses at all assumed associativity. Out of the three properties in question (identity, inverses, associativity), you can have any combination whatsoever as long as it does not have both inverses and associativity.
This change can be made without affecting the identity, though it doesn't have to. As an example, consider the additive group $mathbbZ_2$ with $1+1=1$ instead of $1+1=0$. By inspection of the 3 relevant cases, there is still an identity in this set and operation even though rows and columns have duplicated information.
That isn't mandatory. The offending definition could just as well have been $0+1=0$, with nothing else changed. One could easily verify that the resulting set and operation do not have an identity.
If there is not an identity, inverses don't exist. At least, the definitions of inverse that I'm familiar with explicitly define such a thing in terms of an identity.
If there IS an identity, inverses still don't exist. Consider (with multiplicative notation and an identity of $e$) the equation $ax=bx$ corresponding to a row with duplicates if $aneq b$. Note that if inverses existed we would have $ae=be$, but since $e$ is the identity we have $a=b$, violating $aneq b$.
Associativity can go either way. The object $mathbbZ_2$ with $1+1=1$ is associative and even has an identity. As far as modifications to $mathbbZ_2$ are concerned, there are non-associative options as well (like all additions being $0$ except $0+1=1$), but none of them have a proper identity.
With slightly more elements, we can lose associativity and retain the identity. Consider the set $0,1,2$ with $0$ as an identity, $1+1=0$, and $2+1=0$. Note that $$beginaligned2+(1+1)&=2+0\&=2neq1\&=0+1\&=(2+1)+1.endaligned$$ The remaining operations can be defined however you want, and this Cayley table still corresponds to a set with an identity and without associativity.
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
accepted
None of the properties fail automatically
For any group property, you can always find a Cayley table where there's a duplicate entry and yet that property still holds. Here are examples for each:
Associativity can still hold. $$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$
Identity can still hold. (Same example.)
$$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$Inverses can still hold. (Here, $a$ and $b$ are inverses of each other.)$$beginarrayccc & e & a & b \hline e & e & a & b\a & a & a & e \b & b & e & aendarray$$
However, either associativity fails or inverses fail.
If there's a duplicate row, then $ab=ac$ for some $bneq c$. Suppose the operator has inverses and associativity. Then we get $a^-1ab = a^-1ac$ so that $b=c$â contradicting our assumption that $bneq c$.
So if there's a duplicate row, the operator can either be associative (as shown above), or have inverses (as shown above), but never both.
For confirmation, note that in the example tables above, #1 is associative but not invertible because of 0, and #3 is invertible but not associative because $(bb)a = aa = a$ but $b(ba) = be = b$.)
Diagram
Groups can't have repeat entries. Therefore, if a table has repeat entries, it's not a group. If it's not a group, then it's not in the green region of this diagram. Visually, you can see that such a table can't be both associative and have inverses at the same time. And you can show that there exist tables with duplicate rows that belong to any other non-green region of this diagram.
add a comment |Â
up vote
9
down vote
accepted
None of the properties fail automatically
For any group property, you can always find a Cayley table where there's a duplicate entry and yet that property still holds. Here are examples for each:
Associativity can still hold. $$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$
Identity can still hold. (Same example.)
$$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$Inverses can still hold. (Here, $a$ and $b$ are inverses of each other.)$$beginarrayccc & e & a & b \hline e & e & a & b\a & a & a & e \b & b & e & aendarray$$
However, either associativity fails or inverses fail.
If there's a duplicate row, then $ab=ac$ for some $bneq c$. Suppose the operator has inverses and associativity. Then we get $a^-1ab = a^-1ac$ so that $b=c$â contradicting our assumption that $bneq c$.
So if there's a duplicate row, the operator can either be associative (as shown above), or have inverses (as shown above), but never both.
For confirmation, note that in the example tables above, #1 is associative but not invertible because of 0, and #3 is invertible but not associative because $(bb)a = aa = a$ but $b(ba) = be = b$.)
Diagram
Groups can't have repeat entries. Therefore, if a table has repeat entries, it's not a group. If it's not a group, then it's not in the green region of this diagram. Visually, you can see that such a table can't be both associative and have inverses at the same time. And you can show that there exist tables with duplicate rows that belong to any other non-green region of this diagram.
add a comment |Â
up vote
9
down vote
accepted
up vote
9
down vote
accepted
None of the properties fail automatically
For any group property, you can always find a Cayley table where there's a duplicate entry and yet that property still holds. Here are examples for each:
Associativity can still hold. $$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$
Identity can still hold. (Same example.)
$$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$Inverses can still hold. (Here, $a$ and $b$ are inverses of each other.)$$beginarrayccc & e & a & b \hline e & e & a & b\a & a & a & e \b & b & e & aendarray$$
However, either associativity fails or inverses fail.
If there's a duplicate row, then $ab=ac$ for some $bneq c$. Suppose the operator has inverses and associativity. Then we get $a^-1ab = a^-1ac$ so that $b=c$â contradicting our assumption that $bneq c$.
So if there's a duplicate row, the operator can either be associative (as shown above), or have inverses (as shown above), but never both.
For confirmation, note that in the example tables above, #1 is associative but not invertible because of 0, and #3 is invertible but not associative because $(bb)a = aa = a$ but $b(ba) = be = b$.)
Diagram
Groups can't have repeat entries. Therefore, if a table has repeat entries, it's not a group. If it's not a group, then it's not in the green region of this diagram. Visually, you can see that such a table can't be both associative and have inverses at the same time. And you can show that there exist tables with duplicate rows that belong to any other non-green region of this diagram.
None of the properties fail automatically
For any group property, you can always find a Cayley table where there's a duplicate entry and yet that property still holds. Here are examples for each:
Associativity can still hold. $$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$
Identity can still hold. (Same example.)
$$beginarrayc times& 0 & 1 \hline 0 & 0 & 0\1 & 0 & 1endarray$$Inverses can still hold. (Here, $a$ and $b$ are inverses of each other.)$$beginarrayccc & e & a & b \hline e & e & a & b\a & a & a & e \b & b & e & aendarray$$
However, either associativity fails or inverses fail.
If there's a duplicate row, then $ab=ac$ for some $bneq c$. Suppose the operator has inverses and associativity. Then we get $a^-1ab = a^-1ac$ so that $b=c$â contradicting our assumption that $bneq c$.
So if there's a duplicate row, the operator can either be associative (as shown above), or have inverses (as shown above), but never both.
For confirmation, note that in the example tables above, #1 is associative but not invertible because of 0, and #3 is invertible but not associative because $(bb)a = aa = a$ but $b(ba) = be = b$.)
Diagram
Groups can't have repeat entries. Therefore, if a table has repeat entries, it's not a group. If it's not a group, then it's not in the green region of this diagram. Visually, you can see that such a table can't be both associative and have inverses at the same time. And you can show that there exist tables with duplicate rows that belong to any other non-green region of this diagram.
edited Aug 27 at 20:35
answered Aug 26 at 1:55
user326210
8,722625
8,722625
add a comment |Â
add a comment |Â
up vote
3
down vote
If you have a monoid, an entry can appear twice in a row or a column. However, the axioms "Identity" and "Associativity" are satisfied. Suppose now that $xa = xb$ with $a not= b$. Then $x$ cannot have an inverse, since otherwise $xa = xb$ implies $x^-1xa = x^-1xb$, that is, $a = b$.
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
add a comment |Â
up vote
3
down vote
If you have a monoid, an entry can appear twice in a row or a column. However, the axioms "Identity" and "Associativity" are satisfied. Suppose now that $xa = xb$ with $a not= b$. Then $x$ cannot have an inverse, since otherwise $xa = xb$ implies $x^-1xa = x^-1xb$, that is, $a = b$.
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
add a comment |Â
up vote
3
down vote
up vote
3
down vote
If you have a monoid, an entry can appear twice in a row or a column. However, the axioms "Identity" and "Associativity" are satisfied. Suppose now that $xa = xb$ with $a not= b$. Then $x$ cannot have an inverse, since otherwise $xa = xb$ implies $x^-1xa = x^-1xb$, that is, $a = b$.
If you have a monoid, an entry can appear twice in a row or a column. However, the axioms "Identity" and "Associativity" are satisfied. Suppose now that $xa = xb$ with $a not= b$. Then $x$ cannot have an inverse, since otherwise $xa = xb$ implies $x^-1xa = x^-1xb$, that is, $a = b$.
edited Aug 26 at 0:16
Shaun
7,43692972
7,43692972
answered Aug 25 at 23:17
J.-E. Pin
17.4k21753
17.4k21753
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
add a comment |Â
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
3
3
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
In your last line you are assuming associativity.
â Josh B.
Aug 25 at 23:52
add a comment |Â
up vote
1
down vote
Update: The proof I gave that you can't have inverses at all assumed associativity. Out of the three properties in question (identity, inverses, associativity), you can have any combination whatsoever as long as it does not have both inverses and associativity.
This change can be made without affecting the identity, though it doesn't have to. As an example, consider the additive group $mathbbZ_2$ with $1+1=1$ instead of $1+1=0$. By inspection of the 3 relevant cases, there is still an identity in this set and operation even though rows and columns have duplicated information.
That isn't mandatory. The offending definition could just as well have been $0+1=0$, with nothing else changed. One could easily verify that the resulting set and operation do not have an identity.
If there is not an identity, inverses don't exist. At least, the definitions of inverse that I'm familiar with explicitly define such a thing in terms of an identity.
If there IS an identity, inverses still don't exist. Consider (with multiplicative notation and an identity of $e$) the equation $ax=bx$ corresponding to a row with duplicates if $aneq b$. Note that if inverses existed we would have $ae=be$, but since $e$ is the identity we have $a=b$, violating $aneq b$.
Associativity can go either way. The object $mathbbZ_2$ with $1+1=1$ is associative and even has an identity. As far as modifications to $mathbbZ_2$ are concerned, there are non-associative options as well (like all additions being $0$ except $0+1=1$), but none of them have a proper identity.
With slightly more elements, we can lose associativity and retain the identity. Consider the set $0,1,2$ with $0$ as an identity, $1+1=0$, and $2+1=0$. Note that $$beginaligned2+(1+1)&=2+0\&=2neq1\&=0+1\&=(2+1)+1.endaligned$$ The remaining operations can be defined however you want, and this Cayley table still corresponds to a set with an identity and without associativity.
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
add a comment |Â
up vote
1
down vote
Update: The proof I gave that you can't have inverses at all assumed associativity. Out of the three properties in question (identity, inverses, associativity), you can have any combination whatsoever as long as it does not have both inverses and associativity.
This change can be made without affecting the identity, though it doesn't have to. As an example, consider the additive group $mathbbZ_2$ with $1+1=1$ instead of $1+1=0$. By inspection of the 3 relevant cases, there is still an identity in this set and operation even though rows and columns have duplicated information.
That isn't mandatory. The offending definition could just as well have been $0+1=0$, with nothing else changed. One could easily verify that the resulting set and operation do not have an identity.
If there is not an identity, inverses don't exist. At least, the definitions of inverse that I'm familiar with explicitly define such a thing in terms of an identity.
If there IS an identity, inverses still don't exist. Consider (with multiplicative notation and an identity of $e$) the equation $ax=bx$ corresponding to a row with duplicates if $aneq b$. Note that if inverses existed we would have $ae=be$, but since $e$ is the identity we have $a=b$, violating $aneq b$.
Associativity can go either way. The object $mathbbZ_2$ with $1+1=1$ is associative and even has an identity. As far as modifications to $mathbbZ_2$ are concerned, there are non-associative options as well (like all additions being $0$ except $0+1=1$), but none of them have a proper identity.
With slightly more elements, we can lose associativity and retain the identity. Consider the set $0,1,2$ with $0$ as an identity, $1+1=0$, and $2+1=0$. Note that $$beginaligned2+(1+1)&=2+0\&=2neq1\&=0+1\&=(2+1)+1.endaligned$$ The remaining operations can be defined however you want, and this Cayley table still corresponds to a set with an identity and without associativity.
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Update: The proof I gave that you can't have inverses at all assumed associativity. Out of the three properties in question (identity, inverses, associativity), you can have any combination whatsoever as long as it does not have both inverses and associativity.
This change can be made without affecting the identity, though it doesn't have to. As an example, consider the additive group $mathbbZ_2$ with $1+1=1$ instead of $1+1=0$. By inspection of the 3 relevant cases, there is still an identity in this set and operation even though rows and columns have duplicated information.
That isn't mandatory. The offending definition could just as well have been $0+1=0$, with nothing else changed. One could easily verify that the resulting set and operation do not have an identity.
If there is not an identity, inverses don't exist. At least, the definitions of inverse that I'm familiar with explicitly define such a thing in terms of an identity.
If there IS an identity, inverses still don't exist. Consider (with multiplicative notation and an identity of $e$) the equation $ax=bx$ corresponding to a row with duplicates if $aneq b$. Note that if inverses existed we would have $ae=be$, but since $e$ is the identity we have $a=b$, violating $aneq b$.
Associativity can go either way. The object $mathbbZ_2$ with $1+1=1$ is associative and even has an identity. As far as modifications to $mathbbZ_2$ are concerned, there are non-associative options as well (like all additions being $0$ except $0+1=1$), but none of them have a proper identity.
With slightly more elements, we can lose associativity and retain the identity. Consider the set $0,1,2$ with $0$ as an identity, $1+1=0$, and $2+1=0$. Note that $$beginaligned2+(1+1)&=2+0\&=2neq1\&=0+1\&=(2+1)+1.endaligned$$ The remaining operations can be defined however you want, and this Cayley table still corresponds to a set with an identity and without associativity.
Update: The proof I gave that you can't have inverses at all assumed associativity. Out of the three properties in question (identity, inverses, associativity), you can have any combination whatsoever as long as it does not have both inverses and associativity.
This change can be made without affecting the identity, though it doesn't have to. As an example, consider the additive group $mathbbZ_2$ with $1+1=1$ instead of $1+1=0$. By inspection of the 3 relevant cases, there is still an identity in this set and operation even though rows and columns have duplicated information.
That isn't mandatory. The offending definition could just as well have been $0+1=0$, with nothing else changed. One could easily verify that the resulting set and operation do not have an identity.
If there is not an identity, inverses don't exist. At least, the definitions of inverse that I'm familiar with explicitly define such a thing in terms of an identity.
If there IS an identity, inverses still don't exist. Consider (with multiplicative notation and an identity of $e$) the equation $ax=bx$ corresponding to a row with duplicates if $aneq b$. Note that if inverses existed we would have $ae=be$, but since $e$ is the identity we have $a=b$, violating $aneq b$.
Associativity can go either way. The object $mathbbZ_2$ with $1+1=1$ is associative and even has an identity. As far as modifications to $mathbbZ_2$ are concerned, there are non-associative options as well (like all additions being $0$ except $0+1=1$), but none of them have a proper identity.
With slightly more elements, we can lose associativity and retain the identity. Consider the set $0,1,2$ with $0$ as an identity, $1+1=0$, and $2+1=0$. Note that $$beginaligned2+(1+1)&=2+0\&=2neq1\&=0+1\&=(2+1)+1.endaligned$$ The remaining operations can be defined however you want, and this Cayley table still corresponds to a set with an identity and without associativity.
edited Aug 26 at 2:12
answered Aug 25 at 23:15
Hans Musgrave
1,504111
1,504111
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
add a comment |Â
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
1
1
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
Associativity definitely could fail. Take your time.
â Frenzy Li
Aug 25 at 23:16
1
1
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
Inverse semigroups might interest you. There, one can have inverses without an identity. We say $b$ is an inverse of $a$ if both $a=aba$ and $b=bab$.
â Shaun
Aug 26 at 0:13
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2894561%2fin-a-cayley-table-which-group-axioms-fail-when-an-entry-appears-twice-in-a-row%23new-answer', 'question_page');
);
Post as a guest
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
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
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