提一个问题

[TheMatrix]

举几个二元函数的例子 f:Z×Z --> Z，使得可以定义出具有结合律的二元运算 x#y = f(x,y)，也就是(x#y)#z=x#(y#z)。

以下两个是显然的：
f(x,y)=x+y
f(x,y)=x*y

举几个其他的例子。

[TheMatrix]

举几个二元函数的例子 f:Z×Z --> Z，使得可以定义出具有结合律的二元运算 x#y = f(x,y)，也就是(x#y)#z=x#(y#z)。

以下两个是显然的：
f(x,y)=x+y
f(x,y)=x*y

举几个其他的例子。

限定一下范围，假如f(x,y)是二元polynomial，这样会简单一些吧。

[YWY]

f(x,y) = nx+ny, where n is an integer.
f(x,y) = xⁿyⁿ, where n is a non-negative integer.

[TheMatrix]

f(x,y) = nx+ny, where n is an integer.
f(x,y) = xⁿyⁿ, where n is a non-negative integer.

还能找到其他的吗？也许没有其他的了。结合律是一个很强的限制。

[randomatrices]

这俩个都不行吧？
n(nx+ny)+nz != nx+n(ny+nz) when n != 1

AND, OR， bitwise AND, bitwise OR 可以

还能找到其他的吗？也许没有其他的了。结合律是一个很强的限制。

[TheMatrix]

这俩个都不行吧？
n(nx+ny)+nz != nx+n(ny+nz) when n != 1

AND, OR， bitwise AND, bitwise OR 可以

确实。nx+ny, xⁿyⁿ都不行。

bitwise AND OR可以。

整数怎么AND OR? 0=false, otherwise true?

[randomatrices]

最简单的就是0=false, otherwise true吧， 或者复杂一点 AND(isPrime(x), isPrime(y))

确实。nx+ny, xⁿyⁿ都不行。

bitwise AND OR可以。

整数怎么AND OR? 0=false, otherwise true?

[randomatrices]

只考虑结合律的话：
f(x,y)=x
f(x,y)=y
都可以，但不满足交换律。
有没有更复杂的呢？

举几个二元函数的例子 f:Z×Z --> Z，使得可以定义出具有结合律的二元运算 x#y = f(x,y)，也就是(x#y)#z=x#(y#z)。

以下两个是显然的：
f(x,y)=x+y
f(x,y)=x*y

举几个其他的例子。

[YWY]

这俩个都不行吧？
n(nx+ny)+nz != nx+n(ny+nz) when n != 1

AND, OR， bitwise AND, bitwise OR 可以

哈哈，我一觉醒来，冲澡时也发现了自己的错误，刚想上来纠正，却早已经被班上大牛们的火眼金睛发现了。

我冲澡时还发现了另一个（trivial的）结合律例子，就是f(x,y) = n where n is a constant。

[TheMatrix]

最简单的就是0=false, otherwise true吧， 或者复杂一点 AND(isPrime(x), isPrime(y))

嗯。一个indicator function on Z，然后再logic function。特例通常可以泛化。。。

[YWY]

只考虑结合律的话：
f(x,y)=x
f(x,y)=y
都可以，但不满足交换律。
有没有更复杂的呢？

还有就是
f(x,y) = min{x,y}
f(x,y) = max{x,y}
f(x,y) = gcd(x,y), where we agree gcd(0,0) = 0
这几个都满足交换律，但不是多项式。

[TheMatrix]

只考虑结合律的话：
f(x,y)=x
f(x,y)=y
都可以，但不满足交换律。
有没有更复杂的呢？

对。这是polynomial。

[TheMatrix]

还有就是
f(x,y) = min{x,y}
f(x,y) = max{x,y}
f(x,y) = gcd(x,y), where we agree gcd(0,0) = 0
这几个都满足交换律，但不是多项式。

嗯。对。我们很可能快要穷尽构造结合律的方法了！

[randomatrices]

哈哈， 大牛一时失察， 我等只是稍微起得早了点。

哈哈，我一觉醒来，冲澡时也发现了自己的错误，刚想上来纠正，却早已经被班上大牛们的火眼金睛发现了。

我冲澡时还发现了另一个（trivial的）结合律例子，就是f(x,y) = n where n is a constant。

[FoxMe]

wikipedia上给了一些例子。要提醒的是，乘法不一定满足结合律，比如octonion：

https://en.wikipedia.org/wiki/Associati ... _operation

[YWY]

哈哈， 大牛一时失察， 我等只是稍微起得早了点。

只考虑结合律的话：
f(x,y)=x
f(x,y)=y
都可以，但不满足交换律。
有没有更复杂的呢？

在你上面例子的基础上，可以取绝对值，依然满足结合律
f(x,y) = |x|
f(x,y) = |y|

[TheMatrix]

wikipedia上给了一些例子。要提醒的是，乘法不一定满足结合律，比如octonion：

https://en.wikipedia.org/wiki/Associati ... _operation

这里列的跟wiki上的差不多了。

[TheMatrix]

再出一个题：构造一个3个元素的monoid，而且非group。

[YWY]

再出一个题：构造一个3个元素的monoid，而且非group。

Let A = {1, 2, ..., n} and let x # y = max{x, y} for x, y in A. Then A is a monoid (with n elements), but A is not a group for n > 1.

[TheMatrix]

Let A = {1, 2, ..., n} and let x # y = max{x, y} for x, y in A. Then A is a monoid (with n elements), but A is not a group for n > 1.

对。

这个问题我没想出来。我问了Bing，Bing给了这个答案。

monoid的这种结构和自然数很不同啊。看来要撑起自然数的结构，加法和乘法都是必不可少的。