Mixing
How many associative binary operations are there on a 2 element set?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
We can easily find commutative binary operations on a 2 element set from the truth table (if ab=ba then the operation is commutative, thus there are 8 commutative binary operations in a 2 element set).
Is there a similar method or algorithm to find how many and what are the associative binary operations in a 2 element set?
If there isn't a way to quickly check, we would need to test all 8 possible inputs independently (if not commutative) and only 4 (if commutative) - which is still a lot for a 2 element set - 96 total (16 operations, 8 are commutative, so 8*4+8*8=96).
A generalization to an n-element set be very helpful.
abstract-algebra binary-operations associativity
asked Aug 3 at 13:50
JohnShn
62
add a comment |Â
up vote
1
down vote
favorite
We can easily find commutative binary operations on a 2 element set from the truth table (if ab=ba then the operation is commutative, thus there are 8 commutative binary operations in a 2 element set).
Is there a similar method or algorithm to find how many and what are the associative binary operations in a 2 element set?
If there isn't a way to quickly check, we would need to test all 8 possible inputs independently (if not commutative) and only 4 (if commutative) - which is still a lot for a 2 element set - 96 total (16 operations, 8 are commutative, so 8*4+8*8=96).
A generalization to an n-element set be very helpful.
abstract-algebra binary-operations associativity
asked Aug 3 at 13:50
JohnShn
62
2
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
2
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
We can easily find commutative binary operations on a 2 element set from the truth table (if ab=ba then the operation is commutative, thus there are 8 commutative binary operations in a 2 element set).
Is there a similar method or algorithm to find how many and what are the associative binary operations in a 2 element set?
If there isn't a way to quickly check, we would need to test all 8 possible inputs independently (if not commutative) and only 4 (if commutative) - which is still a lot for a 2 element set - 96 total (16 operations, 8 are commutative, so 8*4+8*8=96).
A generalization to an n-element set be very helpful.
abstract-algebra binary-operations associativity
asked Aug 3 at 13:50
JohnShn
62
We can easily find commutative binary operations on a 2 element set from the truth table (if ab=ba then the operation is commutative, thus there are 8 commutative binary operations in a 2 element set).
Is there a similar method or algorithm to find how many and what are the associative binary operations in a 2 element set?
If there isn't a way to quickly check, we would need to test all 8 possible inputs independently (if not commutative) and only 4 (if commutative) - which is still a lot for a 2 element set - 96 total (16 operations, 8 are commutative, so 8*4+8*8=96).
A generalization to an n-element set be very helpful.
abstract-algebra binary-operations associativity
asked Aug 3 at 13:50
JohnShn
62
asked Aug 3 at 13:50
JohnShn
62
asked Aug 3 at 13:50
JohnShn
62
asked Aug 3 at 13:50
JohnShn
62
62
2
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
2
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02
add a comment |Â
2
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
2
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02
2
2
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
2
2
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
You do not need to check every single possibility. For your set use $+1, -1$.
Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,bin pm1$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_pm1,y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields
$$
beginaligned
B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\
B(x_-y,y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y
endaligned
$$
The possible solutions are (1) $x_y=-x_-y=y$, (2) $x_y=x_-y=y$, (3) $x_y=x_-y=-y$. And these are the only possibilities.
So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_+1, x_-1, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_-y$.Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives
$$
B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a)
$$
meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.
Before we continue, note that the equalities
$$
beginaligned
y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\
1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y)
endaligned
$$
are tautologically true no matter what $y$ is. Writting the most general associativity equality
$$
B(B(a,b),c)=B(a, B(b,c))
$$
assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation
$$
beginaligned
&(mathrmsgn: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(mathrmsgn: a)y)\
&B((mathrmsgn: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(mathrmsgn: a)y)\
&B(-(mathrmsgn: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(mathrmsgn: a)y
endaligned
$$
all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.
Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.
answered Aug 3 at 15:43
Hamed
4,333421
add a comment |Â
up vote
0
down vote
The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $astar b = f(a,b),$ where $star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $T, F,$ so that we can pull in expressions from boolean logic. So we create the following tables:
$$
beginarrayhline
a &b &1 &2 &3 &4 &5 &6 &7 &8 \ hline
T &T &F &F &F &F &F &F &F &F\ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &F &lnot(alor b) & &lnot,a & &lnot,b &aotimes b &lnot (aland b) \ hline
textAssoc.? & &T &F &F &F &F &F &T &F\ hline
endarray
$$
$$
beginarrayhline
a &b &9 &10 &11 &12 &13 &14 &15 &16 \ hline
T &T &T &T &T &T &T &T &T &T \ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &aland b &a iff b &b &aimplies b &a &bimplies a &alor b &T \ hline
textAssoc.? & &T &T &T &F &T &F &T &T \ hline
endarray
$$
Here is some Python code used to test each option:
def f(a: bool, b: bool) -> bool:
return a or b
def test_assoc() -> bool:
values = [True, False]
associative = True
for a in values:
for b in values:
for c in values:
test = (f(f(a, b), c) == f(a, f(b, c)))
associative = associative and test
return associative
You just change the definition of f to match which function you're testing, and run the test_assoc function again.
There are definitely some surprises in these results.
answered Aug 3 at 16:49
Adrian Keister
3,49321433
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
You do not need to check every single possibility. For your set use $+1, -1$.
Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,bin pm1$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_pm1,y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields
$$
beginaligned
B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\
B(x_-y,y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y
endaligned
$$
The possible solutions are (1) $x_y=-x_-y=y$, (2) $x_y=x_-y=y$, (3) $x_y=x_-y=-y$. And these are the only possibilities.
So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_+1, x_-1, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_-y$.Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives
$$
B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a)
$$
meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.
Before we continue, note that the equalities
$$
beginaligned
y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\
1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y)
endaligned
$$
are tautologically true no matter what $y$ is. Writting the most general associativity equality
$$
B(B(a,b),c)=B(a, B(b,c))
$$
assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation
$$
beginaligned
&(mathrmsgn: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(mathrmsgn: a)y)\
&B((mathrmsgn: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(mathrmsgn: a)y)\
&B(-(mathrmsgn: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(mathrmsgn: a)y
endaligned
$$
all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.
Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.
answered Aug 3 at 15:43
Hamed
4,333421
add a comment |Â
up vote
1
down vote
You do not need to check every single possibility. For your set use $+1, -1$.
Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,bin pm1$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_pm1,y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields
$$
beginaligned
B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\
B(x_-y,y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y
endaligned
$$
The possible solutions are (1) $x_y=-x_-y=y$, (2) $x_y=x_-y=y$, (3) $x_y=x_-y=-y$. And these are the only possibilities.
So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_+1, x_-1, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_-y$.Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives
$$
B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a)
$$
meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.
Before we continue, note that the equalities
$$
beginaligned
y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\
1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y)
endaligned
$$
are tautologically true no matter what $y$ is. Writting the most general associativity equality
$$
B(B(a,b),c)=B(a, B(b,c))
$$
assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation
$$
beginaligned
&(mathrmsgn: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(mathrmsgn: a)y)\
&B((mathrmsgn: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(mathrmsgn: a)y)\
&B(-(mathrmsgn: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(mathrmsgn: a)y
endaligned
$$
all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.
Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.
answered Aug 3 at 15:43
Hamed
4,333421
add a comment |Â
up vote
1
down vote
up vote
1
down vote
You do not need to check every single possibility. For your set use $+1, -1$.
Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,bin pm1$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_pm1,y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields
$$
beginaligned
B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\
B(x_-y,y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y
endaligned
$$
The possible solutions are (1) $x_y=-x_-y=y$, (2) $x_y=x_-y=y$, (3) $x_y=x_-y=-y$. And these are the only possibilities.
So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_+1, x_-1, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_-y$.Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives
$$
B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a)
$$
meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.
Before we continue, note that the equalities
$$
beginaligned
y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\
1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y)
endaligned
$$
are tautologically true no matter what $y$ is. Writting the most general associativity equality
$$
B(B(a,b),c)=B(a, B(b,c))
$$
assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation
$$
beginaligned
&(mathrmsgn: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(mathrmsgn: a)y)\
&B((mathrmsgn: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(mathrmsgn: a)y)\
&B(-(mathrmsgn: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(mathrmsgn: a)y
endaligned
$$
all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.
Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.
answered Aug 3 at 15:43
Hamed
4,333421
You do not need to check every single possibility. For your set use $+1, -1$.
Suppose $B$ is commutative, i.e. $B(a,b)=B(b,a)$ for all $a,bin pm1$, and associative . Then if we put $B(a,a)=x_a$ and $B(a,-a)=B(-a,a)=y$ (note the latter is independent of $a$). The triple $x_pm1,y$ is enough to completely determine $B$. The only non-trivial associativity equation in this case yields
$$
beginaligned
B(x_y,-y)&=B(B(y,y), -y)=B(y,B(y,-y))=B(y,y)=x_y\
B(x_-y,y)&=B(B(-y,-y), y)=B(-y,B(-y,y))=B(-y,y)=y
endaligned
$$
The possible solutions are (1) $x_y=-x_-y=y$, (2) $x_y=x_-y=y$, (3) $x_y=x_-y=-y$. And these are the only possibilities.
So programatically, if $B(1,-1)=B(-1,1)$, simply calculate $x_+1, x_-1, y$ and check if $x_y=y$ (case 1 and 2 together), or else if $x_y=x_-y$.Suppose $B$ is NOT commutative but associative. Then $B(a,-a)=-B(-a,a)$. Define $x_a=B(a,a)$ and $y=B(1,-1)$. Now associativity gives
$$
B(x_a,a)=B(B(a,a),a)=B(a,B(a,a))=B(a,x_a)
$$
meaning $a,x_a$ commute. This in turn means, $x_a=a$ necessarily.
Before we continue, note that the equalities
$$
beginaligned
y&=B(1,y)=-B(-1,-y)=B(y,-1)=-B(-y,1)\
1&=B(y,1)=B(1,-y)=-B(-y,-1)=-B(-1,y)
endaligned
$$
are tautologically true no matter what $y$ is. Writting the most general associativity equality
$$
B(B(a,b),c)=B(a, B(b,c))
$$
assuming not all $a,b,c$ are the same, we have the following possibilities, $a=b=-c$, $a=-b=c$ and $-a=b=c$. This leads to three associativity relation
$$
beginaligned
&(mathrmsgn: a)y=B(a,-a)=B(B(a,a),-a)=B(a, B(a,-a))=B(a,(mathrmsgn: a)y)\
&B((mathrmsgn: a)y,a)=B(B(a,-a),a)=B(a, B(-a,a))=B(a, -(mathrmsgn: a)y)\
&B(-(mathrmsgn: a)y,a)=B(B(-a,a),a)=B(-a,B(a,a))=B(-a,a)=-(mathrmsgn: a)y
endaligned
$$
all of which are tautologically true. This means we are completely free to choose $y$ as we please. So programatically, if $y=B(1,-1)neq B(-1,1)$, then simply check if $B(1,1)=1$ and $B(-1,-1)$, because that's the only possibility.
Assuming I have not done any stupid mistakes (which I'm quite afraid might have happened), you should be able to rule whether a binary relation $B$ is associative or not with like four if-clauses. I'm too lazy to actually count how many binary relations I just created, but it's quite straightforward to do that now.
answered Aug 3 at 15:43
Hamed
4,333421
edited Aug 3 at 15:51
answered Aug 3 at 15:43
Hamed
4,333421
answered Aug 3 at 15:43
Hamed
4,333421
answered Aug 3 at 15:43
Hamed
4,333421
4,333421
add a comment |Â
add a comment |Â
up vote
0
down vote
The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $astar b = f(a,b),$ where $star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $T, F,$ so that we can pull in expressions from boolean logic. So we create the following tables:
$$
beginarrayhline
a &b &1 &2 &3 &4 &5 &6 &7 &8 \ hline
T &T &F &F &F &F &F &F &F &F\ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &F &lnot(alor b) & &lnot,a & &lnot,b &aotimes b &lnot (aland b) \ hline
textAssoc.? & &T &F &F &F &F &F &T &F\ hline
endarray
$$
$$
beginarrayhline
a &b &9 &10 &11 &12 &13 &14 &15 &16 \ hline
T &T &T &T &T &T &T &T &T &T \ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &aland b &a iff b &b &aimplies b &a &bimplies a &alor b &T \ hline
textAssoc.? & &T &T &T &F &T &F &T &T \ hline
endarray
$$
Here is some Python code used to test each option:
def f(a: bool, b: bool) -> bool:
return a or b
def test_assoc() -> bool:
values = [True, False]
associative = True
for a in values:
for b in values:
for c in values:
test = (f(f(a, b), c) == f(a, f(b, c)))
associative = associative and test
return associative
You just change the definition of f to match which function you're testing, and run the test_assoc function again.
There are definitely some surprises in these results.
answered Aug 3 at 16:49
Adrian Keister
3,49321433
add a comment |Â
up vote
0
down vote
The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $astar b = f(a,b),$ where $star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $T, F,$ so that we can pull in expressions from boolean logic. So we create the following tables:
$$
beginarrayhline
a &b &1 &2 &3 &4 &5 &6 &7 &8 \ hline
T &T &F &F &F &F &F &F &F &F\ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &F &lnot(alor b) & &lnot,a & &lnot,b &aotimes b &lnot (aland b) \ hline
textAssoc.? & &T &F &F &F &F &F &T &F\ hline
endarray
$$
$$
beginarrayhline
a &b &9 &10 &11 &12 &13 &14 &15 &16 \ hline
T &T &T &T &T &T &T &T &T &T \ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &aland b &a iff b &b &aimplies b &a &bimplies a &alor b &T \ hline
textAssoc.? & &T &T &T &F &T &F &T &T \ hline
endarray
$$
Here is some Python code used to test each option:
def f(a: bool, b: bool) -> bool:
return a or b
def test_assoc() -> bool:
values = [True, False]
associative = True
for a in values:
for b in values:
for c in values:
test = (f(f(a, b), c) == f(a, f(b, c)))
associative = associative and test
return associative
You just change the definition of f to match which function you're testing, and run the test_assoc function again.
There are definitely some surprises in these results.
answered Aug 3 at 16:49
Adrian Keister
3,49321433
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $astar b = f(a,b),$ where $star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $T, F,$ so that we can pull in expressions from boolean logic. So we create the following tables:
$$
beginarrayhline
a &b &1 &2 &3 &4 &5 &6 &7 &8 \ hline
T &T &F &F &F &F &F &F &F &F\ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &F &lnot(alor b) & &lnot,a & &lnot,b &aotimes b &lnot (aland b) \ hline
textAssoc.? & &T &F &F &F &F &F &T &F\ hline
endarray
$$
$$
beginarrayhline
a &b &9 &10 &11 &12 &13 &14 &15 &16 \ hline
T &T &T &T &T &T &T &T &T &T \ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &aland b &a iff b &b &aimplies b &a &bimplies a &alor b &T \ hline
textAssoc.? & &T &T &T &F &T &F &T &T \ hline
endarray
$$
Here is some Python code used to test each option:
def f(a: bool, b: bool) -> bool:
return a or b
def test_assoc() -> bool:
values = [True, False]
associative = True
for a in values:
for b in values:
for c in values:
test = (f(f(a, b), c) == f(a, f(b, c)))
associative = associative and test
return associative
You just change the definition of f to match which function you're testing, and run the test_assoc function again.
There are definitely some surprises in these results.
answered Aug 3 at 16:49
Adrian Keister
3,49321433
The comments show what there might be for the $n$-element set. As for the $2$-element set, we can enumerate all possible binary operations (realizing that Hamed's answer shows we don't necessarily have to do this), and then check which ones are associative. Assume we are writing $astar b = f(a,b),$ where $star$ is the binary operation and $f$ we will designate as a number from $1$ to $16,$ and we're going to use the $2$-element set $T, F,$ so that we can pull in expressions from boolean logic. So we create the following tables:
$$
beginarrayhline
a &b &1 &2 &3 &4 &5 &6 &7 &8 \ hline
T &T &F &F &F &F &F &F &F &F\ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &F &lnot(alor b) & &lnot,a & &lnot,b &aotimes b &lnot (aland b) \ hline
textAssoc.? & &T &F &F &F &F &F &T &F\ hline
endarray
$$
$$
beginarrayhline
a &b &9 &10 &11 &12 &13 &14 &15 &16 \ hline
T &T &T &T &T &T &T &T &T &T \ hline
T &F &F &F &F &F &T &T &T &T \ hline
F &T &F &F &T &T &F &F &T &T \ hline
F &F &F &T &F &T &F &T &F &T \ hline
textExpr: & &aland b &a iff b &b &aimplies b &a &bimplies a &alor b &T \ hline
textAssoc.? & &T &T &T &F &T &F &T &T \ hline
endarray
$$
Here is some Python code used to test each option:
def f(a: bool, b: bool) -> bool:
return a or b
def test_assoc() -> bool:
values = [True, False]
associative = True
for a in values:
for b in values:
for c in values:
test = (f(f(a, b), c) == f(a, f(b, c)))
associative = associative and test
return associative
You just change the definition of f to match which function you're testing, and run the test_assoc function again.
There are definitely some surprises in these results.
answered Aug 3 at 16:49
Adrian Keister
3,49321433
edited Aug 3 at 17:02
answered Aug 3 at 16:49
Adrian Keister
3,49321433
answered Aug 3 at 16:49
Adrian Keister
3,49321433
answered Aug 3 at 16:49
Adrian Keister
3,49321433
3,49321433
add a comment |Â
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%2f2871087%2fhow-many-associative-binary-operations-are-there-on-a-2-element-set%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
2
Considering that this 7-page paper (the first google result I got) is needed for the number of associative binary operators on a $5$-element set, I don't think there is a nice and simple general way (at least not a known one). Although since they clearly haven't checked all possible 3-element multiplications for all the 298,023,223,876,953,125 possible operations (at least I don't think they have, I haven't actually read the thing) you might be able to find some nice shortcuts.
– Arthur
Aug 3 at 13:54
2
The result in that paper leads to OEIS sequence A023814, which contains the counts up to $9$-element set and a few links but no results. (Note that the counts up to $9$-element sets where shortly before that paper was published, so apparently that wasn't state of the art.)
– joriki
Aug 3 at 14:02