Mixing
An $m$-ary function that represents all $n$-ary functions
up vote
5
down vote
favorite
Motivation
It is well-known that any binary operator $*$ on the boolean ring ${0,1}$ can be represented using only one of the $operatorname{NAND}$ and $operatorname{NOR}$ operators. For example,
$$xrightarrow y=big((xoperatorname{NOR}x)operatorname{NOR}ybig)operatorname{NOR}big((xoperatorname{NOR}x)operatorname{NOR}ybig)$$
and
begin{align}xoperatorname{XOR}y&= Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big)
\&hphantom{123}operatorname{NAND}Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big),end{align}
where $$p=big(xoperatorname{NAND}(yoperatorname{NAND}y)big)operatorname{NAND}big(xoperatorname{NAND}(yoperatorname{NAND}y)big)$$ and $$q=big((xoperatorname{NAND}x)operatorname{NAND}ybig)operatorname{NAND}big((xoperatorname{NAND}x)operatorname{NAND}ybig).$$
The notation $rightarrow$ is the implication connective, and $operatorname{XOR}$ is the exclusive-or operator.
Definitions
Let $S$ be a set and $f:S^mto S$ is an $m$-ary function (or $m$-ary operator). A valid expression in $f$ is an expression $E(x_1,x_2,ldots,x_n)$, where $x_1,x_2,ldots,x_nin S$ involving only finite iterations of $f$ and using only variables among $x_1,x_2,ldots,x_n$.
For example, if $m=n=2$ and $0in S$, $fbig(x_1,f(0,x_2)big)$ is not a valid expression because there is a constant $0$ that is not in the form of the variables $x_1,x_2$. If $m=2$, $n=1$, $S=mathbb{R}_{>0}$, and $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, then this is also not a valid expression because it involves infinite iterations of $f$:
$$fBiggl(x,fBig(x,fbig(x,f(ldots)big)Big)Biggr)=sqrt{xsqrt{xsqrt{xsqrt{ldots}}}} (=x).$$
(However, if you want to represent the identity function $xmapsto x$ on $S=mathbb{R}_{>0}$ with the function $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, this can be done without involving infinite iterations of $f$ like the previous example, i.e., $fbig(f(x,x),xbig)=sqrt{(xsqrt{x})sqrt{x}}=x$.)
For $m=n=3$, this is a valid expression of $f$:
$$fBiggl(fbig(x_1,x_2,f(x_1,x_3,x_2)big),fBig(fbig(x_1,f(x_2,x_3,x_1),x_3big),x_2,x_1Big)Biggr).$$
Also, not all variables need to be used. So, for $m=n=2$,
$$fbig(x_1,f(x_1,x_1)big)$$
is still a valid expression of $f$. In the previous example, one can say that this is a valid expression of $f$ with $m=2$ and $n=1$, as well. There can also be more variables than the number of arguments of $f$, that is, if $m=2$ and $n=3$,
$$fbig(f(x_1,x_2),f(x_2,x_3)big)$$
is a valid expression of $f$.
Let $g:S^nto S$. We say that $g$ is representable by $f$ if there exists a valid expression $E(x_1,x_2,ldots,x_n)$ of $f$ such that
$$g(x_1,x_2,ldots,x_n)=E(x_1,x_2,ldots,x_n)$$
for all $x_1,x_2,ldots,x_nin S$. For an $m$-ary function $f:S^mto S$, we say that $f$ is $n$-fulfilling if every $n$-ary function $g:S^nto S$ is representable by $f$.
Question
For a given non-empty set $S$ and positive integers $m,n$, when does there exist a $n$-fulfilling $m$-ary function $f:S^mto S$? Does there exist a set $S$ with $|S|geq 3$ along with a positive integer $m$ such that for some an $m$-ary function $f:S^mto S$ exists, and for any positive integer $n$, every $n$-ary function $g:S^nto S$ is representatble by $f$.
Has there been a study on this type of questions? Any reference is greatly appreciated.
Known Results
If $S$ is infinite, then there are only countably many valid expressions of $f$ in $n$ variables, but there are uncountably many $n$-ary functions $g:S^nto S$. Therefore, such a function $f$ does not exist. Hence, we can assume that $S$ is finite.
If $m=1$, then there exists an $n$-fulfilling function $f:Sto S$ if and only if $|S|=1$ or $big(n,|S|big)=(1,2)$. Clearly, the only valid expression of $f$ in any number of variables is of the form $f^k(x)$. Therefore, when $|S|>1$, there can only be one variable, so $n=1$. However, since the permutation group on $S$ is not abelian for $|S|>2$, we must have $|S|=2$ (provided that $|S|>1$).
Of course, if $|S|=1$, then any $m$-ary function $f:S^mto S$ and any $n$-ary function $g:S^mto S$ have the same image. So, this case is very trivial. If $|S|=2$, I think that we can identify $S$ as the boolean ring ${0,1}$ and use the $operatorname{NAND}$ or $operatorname{NOR}$ operators to represent any $n$-ary function $g:S^nto S$.
combinatorics functions reference-request binary-operations boolean-ring
asked Nov 8 at 12:59
Zvi
3,290223
This question has an open bounty worth +50
reputation from Zvi ending in 5 days.
This question has not received enough attention.
The case $S$ is finite and $|S|>2$ is still unsolved. I believe that the answer is positive already when $m=2$. That is, for any $n$ there exists a $2$-ary function $f:S^2to S$ such that $f$ is $n$-fulfilling. I wouldn't be surprised if there exists one $f$ for all $n$.
add a comment |
up vote
5
down vote
favorite
Motivation
It is well-known that any binary operator $*$ on the boolean ring ${0,1}$ can be represented using only one of the $operatorname{NAND}$ and $operatorname{NOR}$ operators. For example,
$$xrightarrow y=big((xoperatorname{NOR}x)operatorname{NOR}ybig)operatorname{NOR}big((xoperatorname{NOR}x)operatorname{NOR}ybig)$$
and
begin{align}xoperatorname{XOR}y&= Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big)
\&hphantom{123}operatorname{NAND}Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big),end{align}
where $$p=big(xoperatorname{NAND}(yoperatorname{NAND}y)big)operatorname{NAND}big(xoperatorname{NAND}(yoperatorname{NAND}y)big)$$ and $$q=big((xoperatorname{NAND}x)operatorname{NAND}ybig)operatorname{NAND}big((xoperatorname{NAND}x)operatorname{NAND}ybig).$$
The notation $rightarrow$ is the implication connective, and $operatorname{XOR}$ is the exclusive-or operator.
Definitions
Let $S$ be a set and $f:S^mto S$ is an $m$-ary function (or $m$-ary operator). A valid expression in $f$ is an expression $E(x_1,x_2,ldots,x_n)$, where $x_1,x_2,ldots,x_nin S$ involving only finite iterations of $f$ and using only variables among $x_1,x_2,ldots,x_n$.
For example, if $m=n=2$ and $0in S$, $fbig(x_1,f(0,x_2)big)$ is not a valid expression because there is a constant $0$ that is not in the form of the variables $x_1,x_2$. If $m=2$, $n=1$, $S=mathbb{R}_{>0}$, and $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, then this is also not a valid expression because it involves infinite iterations of $f$:
$$fBiggl(x,fBig(x,fbig(x,f(ldots)big)Big)Biggr)=sqrt{xsqrt{xsqrt{xsqrt{ldots}}}} (=x).$$
(However, if you want to represent the identity function $xmapsto x$ on $S=mathbb{R}_{>0}$ with the function $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, this can be done without involving infinite iterations of $f$ like the previous example, i.e., $fbig(f(x,x),xbig)=sqrt{(xsqrt{x})sqrt{x}}=x$.)
For $m=n=3$, this is a valid expression of $f$:
$$fBiggl(fbig(x_1,x_2,f(x_1,x_3,x_2)big),fBig(fbig(x_1,f(x_2,x_3,x_1),x_3big),x_2,x_1Big)Biggr).$$
Also, not all variables need to be used. So, for $m=n=2$,
$$fbig(x_1,f(x_1,x_1)big)$$
is still a valid expression of $f$. In the previous example, one can say that this is a valid expression of $f$ with $m=2$ and $n=1$, as well. There can also be more variables than the number of arguments of $f$, that is, if $m=2$ and $n=3$,
$$fbig(f(x_1,x_2),f(x_2,x_3)big)$$
is a valid expression of $f$.
Let $g:S^nto S$. We say that $g$ is representable by $f$ if there exists a valid expression $E(x_1,x_2,ldots,x_n)$ of $f$ such that
$$g(x_1,x_2,ldots,x_n)=E(x_1,x_2,ldots,x_n)$$
for all $x_1,x_2,ldots,x_nin S$. For an $m$-ary function $f:S^mto S$, we say that $f$ is $n$-fulfilling if every $n$-ary function $g:S^nto S$ is representable by $f$.
Question
For a given non-empty set $S$ and positive integers $m,n$, when does there exist a $n$-fulfilling $m$-ary function $f:S^mto S$? Does there exist a set $S$ with $|S|geq 3$ along with a positive integer $m$ such that for some an $m$-ary function $f:S^mto S$ exists, and for any positive integer $n$, every $n$-ary function $g:S^nto S$ is representatble by $f$.
Has there been a study on this type of questions? Any reference is greatly appreciated.
Known Results
If $S$ is infinite, then there are only countably many valid expressions of $f$ in $n$ variables, but there are uncountably many $n$-ary functions $g:S^nto S$. Therefore, such a function $f$ does not exist. Hence, we can assume that $S$ is finite.
If $m=1$, then there exists an $n$-fulfilling function $f:Sto S$ if and only if $|S|=1$ or $big(n,|S|big)=(1,2)$. Clearly, the only valid expression of $f$ in any number of variables is of the form $f^k(x)$. Therefore, when $|S|>1$, there can only be one variable, so $n=1$. However, since the permutation group on $S$ is not abelian for $|S|>2$, we must have $|S|=2$ (provided that $|S|>1$).
Of course, if $|S|=1$, then any $m$-ary function $f:S^mto S$ and any $n$-ary function $g:S^mto S$ have the same image. So, this case is very trivial. If $|S|=2$, I think that we can identify $S$ as the boolean ring ${0,1}$ and use the $operatorname{NAND}$ or $operatorname{NOR}$ operators to represent any $n$-ary function $g:S^nto S$.
combinatorics functions reference-request binary-operations boolean-ring
asked Nov 8 at 12:59
Zvi
3,290223
This question has an open bounty worth +50
reputation from Zvi ending in 5 days.
This question has not received enough attention.
The case $S$ is finite and $|S|>2$ is still unsolved. I believe that the answer is positive already when $m=2$. That is, for any $n$ there exists a $2$-ary function $f:S^2to S$ such that $f$ is $n$-fulfilling. I wouldn't be surprised if there exists one $f$ for all $n$.
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday
add a comment |
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Motivation
It is well-known that any binary operator $*$ on the boolean ring ${0,1}$ can be represented using only one of the $operatorname{NAND}$ and $operatorname{NOR}$ operators. For example,
$$xrightarrow y=big((xoperatorname{NOR}x)operatorname{NOR}ybig)operatorname{NOR}big((xoperatorname{NOR}x)operatorname{NOR}ybig)$$
and
begin{align}xoperatorname{XOR}y&= Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big)
\&hphantom{123}operatorname{NAND}Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big),end{align}
where $$p=big(xoperatorname{NAND}(yoperatorname{NAND}y)big)operatorname{NAND}big(xoperatorname{NAND}(yoperatorname{NAND}y)big)$$ and $$q=big((xoperatorname{NAND}x)operatorname{NAND}ybig)operatorname{NAND}big((xoperatorname{NAND}x)operatorname{NAND}ybig).$$
The notation $rightarrow$ is the implication connective, and $operatorname{XOR}$ is the exclusive-or operator.
Definitions
Let $S$ be a set and $f:S^mto S$ is an $m$-ary function (or $m$-ary operator). A valid expression in $f$ is an expression $E(x_1,x_2,ldots,x_n)$, where $x_1,x_2,ldots,x_nin S$ involving only finite iterations of $f$ and using only variables among $x_1,x_2,ldots,x_n$.
For example, if $m=n=2$ and $0in S$, $fbig(x_1,f(0,x_2)big)$ is not a valid expression because there is a constant $0$ that is not in the form of the variables $x_1,x_2$. If $m=2$, $n=1$, $S=mathbb{R}_{>0}$, and $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, then this is also not a valid expression because it involves infinite iterations of $f$:
$$fBiggl(x,fBig(x,fbig(x,f(ldots)big)Big)Biggr)=sqrt{xsqrt{xsqrt{xsqrt{ldots}}}} (=x).$$
(However, if you want to represent the identity function $xmapsto x$ on $S=mathbb{R}_{>0}$ with the function $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, this can be done without involving infinite iterations of $f$ like the previous example, i.e., $fbig(f(x,x),xbig)=sqrt{(xsqrt{x})sqrt{x}}=x$.)
For $m=n=3$, this is a valid expression of $f$:
$$fBiggl(fbig(x_1,x_2,f(x_1,x_3,x_2)big),fBig(fbig(x_1,f(x_2,x_3,x_1),x_3big),x_2,x_1Big)Biggr).$$
Also, not all variables need to be used. So, for $m=n=2$,
$$fbig(x_1,f(x_1,x_1)big)$$
is still a valid expression of $f$. In the previous example, one can say that this is a valid expression of $f$ with $m=2$ and $n=1$, as well. There can also be more variables than the number of arguments of $f$, that is, if $m=2$ and $n=3$,
$$fbig(f(x_1,x_2),f(x_2,x_3)big)$$
is a valid expression of $f$.
Let $g:S^nto S$. We say that $g$ is representable by $f$ if there exists a valid expression $E(x_1,x_2,ldots,x_n)$ of $f$ such that
$$g(x_1,x_2,ldots,x_n)=E(x_1,x_2,ldots,x_n)$$
for all $x_1,x_2,ldots,x_nin S$. For an $m$-ary function $f:S^mto S$, we say that $f$ is $n$-fulfilling if every $n$-ary function $g:S^nto S$ is representable by $f$.
Question
For a given non-empty set $S$ and positive integers $m,n$, when does there exist a $n$-fulfilling $m$-ary function $f:S^mto S$? Does there exist a set $S$ with $|S|geq 3$ along with a positive integer $m$ such that for some an $m$-ary function $f:S^mto S$ exists, and for any positive integer $n$, every $n$-ary function $g:S^nto S$ is representatble by $f$.
Has there been a study on this type of questions? Any reference is greatly appreciated.
Known Results
If $S$ is infinite, then there are only countably many valid expressions of $f$ in $n$ variables, but there are uncountably many $n$-ary functions $g:S^nto S$. Therefore, such a function $f$ does not exist. Hence, we can assume that $S$ is finite.
If $m=1$, then there exists an $n$-fulfilling function $f:Sto S$ if and only if $|S|=1$ or $big(n,|S|big)=(1,2)$. Clearly, the only valid expression of $f$ in any number of variables is of the form $f^k(x)$. Therefore, when $|S|>1$, there can only be one variable, so $n=1$. However, since the permutation group on $S$ is not abelian for $|S|>2$, we must have $|S|=2$ (provided that $|S|>1$).
Of course, if $|S|=1$, then any $m$-ary function $f:S^mto S$ and any $n$-ary function $g:S^mto S$ have the same image. So, this case is very trivial. If $|S|=2$, I think that we can identify $S$ as the boolean ring ${0,1}$ and use the $operatorname{NAND}$ or $operatorname{NOR}$ operators to represent any $n$-ary function $g:S^nto S$.
combinatorics functions reference-request binary-operations boolean-ring
asked Nov 8 at 12:59
Zvi
3,290223
Motivation
It is well-known that any binary operator $*$ on the boolean ring ${0,1}$ can be represented using only one of the $operatorname{NAND}$ and $operatorname{NOR}$ operators. For example,
$$xrightarrow y=big((xoperatorname{NOR}x)operatorname{NOR}ybig)operatorname{NOR}big((xoperatorname{NOR}x)operatorname{NOR}ybig)$$
and
begin{align}xoperatorname{XOR}y&= Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big)
\&hphantom{123}operatorname{NAND}Big(big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)operatorname{NAND}big((poperatorname{NAND}p)operatorname{NAND}(qoperatorname{NAND}q)big)Big),end{align}
where $$p=big(xoperatorname{NAND}(yoperatorname{NAND}y)big)operatorname{NAND}big(xoperatorname{NAND}(yoperatorname{NAND}y)big)$$ and $$q=big((xoperatorname{NAND}x)operatorname{NAND}ybig)operatorname{NAND}big((xoperatorname{NAND}x)operatorname{NAND}ybig).$$
The notation $rightarrow$ is the implication connective, and $operatorname{XOR}$ is the exclusive-or operator.
Definitions
Let $S$ be a set and $f:S^mto S$ is an $m$-ary function (or $m$-ary operator). A valid expression in $f$ is an expression $E(x_1,x_2,ldots,x_n)$, where $x_1,x_2,ldots,x_nin S$ involving only finite iterations of $f$ and using only variables among $x_1,x_2,ldots,x_n$.
For example, if $m=n=2$ and $0in S$, $fbig(x_1,f(0,x_2)big)$ is not a valid expression because there is a constant $0$ that is not in the form of the variables $x_1,x_2$. If $m=2$, $n=1$, $S=mathbb{R}_{>0}$, and $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, then this is also not a valid expression because it involves infinite iterations of $f$:
$$fBiggl(x,fBig(x,fbig(x,f(ldots)big)Big)Biggr)=sqrt{xsqrt{xsqrt{xsqrt{ldots}}}} (=x).$$
(However, if you want to represent the identity function $xmapsto x$ on $S=mathbb{R}_{>0}$ with the function $f(x_1,x_2)=sqrt{x_1sqrt{x_2}}$, this can be done without involving infinite iterations of $f$ like the previous example, i.e., $fbig(f(x,x),xbig)=sqrt{(xsqrt{x})sqrt{x}}=x$.)
For $m=n=3$, this is a valid expression of $f$:
$$fBiggl(fbig(x_1,x_2,f(x_1,x_3,x_2)big),fBig(fbig(x_1,f(x_2,x_3,x_1),x_3big),x_2,x_1Big)Biggr).$$
Also, not all variables need to be used. So, for $m=n=2$,
$$fbig(x_1,f(x_1,x_1)big)$$
is still a valid expression of $f$. In the previous example, one can say that this is a valid expression of $f$ with $m=2$ and $n=1$, as well. There can also be more variables than the number of arguments of $f$, that is, if $m=2$ and $n=3$,
$$fbig(f(x_1,x_2),f(x_2,x_3)big)$$
is a valid expression of $f$.
Let $g:S^nto S$. We say that $g$ is representable by $f$ if there exists a valid expression $E(x_1,x_2,ldots,x_n)$ of $f$ such that
$$g(x_1,x_2,ldots,x_n)=E(x_1,x_2,ldots,x_n)$$
for all $x_1,x_2,ldots,x_nin S$. For an $m$-ary function $f:S^mto S$, we say that $f$ is $n$-fulfilling if every $n$-ary function $g:S^nto S$ is representable by $f$.
Question
For a given non-empty set $S$ and positive integers $m,n$, when does there exist a $n$-fulfilling $m$-ary function $f:S^mto S$? Does there exist a set $S$ with $|S|geq 3$ along with a positive integer $m$ such that for some an $m$-ary function $f:S^mto S$ exists, and for any positive integer $n$, every $n$-ary function $g:S^nto S$ is representatble by $f$.
Has there been a study on this type of questions? Any reference is greatly appreciated.
Known Results
If $S$ is infinite, then there are only countably many valid expressions of $f$ in $n$ variables, but there are uncountably many $n$-ary functions $g:S^nto S$. Therefore, such a function $f$ does not exist. Hence, we can assume that $S$ is finite.
If $m=1$, then there exists an $n$-fulfilling function $f:Sto S$ if and only if $|S|=1$ or $big(n,|S|big)=(1,2)$. Clearly, the only valid expression of $f$ in any number of variables is of the form $f^k(x)$. Therefore, when $|S|>1$, there can only be one variable, so $n=1$. However, since the permutation group on $S$ is not abelian for $|S|>2$, we must have $|S|=2$ (provided that $|S|>1$).
Of course, if $|S|=1$, then any $m$-ary function $f:S^mto S$ and any $n$-ary function $g:S^mto S$ have the same image. So, this case is very trivial. If $|S|=2$, I think that we can identify $S$ as the boolean ring ${0,1}$ and use the $operatorname{NAND}$ or $operatorname{NOR}$ operators to represent any $n$-ary function $g:S^nto S$.
combinatorics functions reference-request binary-operations boolean-ring
combinatorics functions reference-request binary-operations boolean-ring
asked Nov 8 at 12:59
Zvi
3,290223
asked Nov 8 at 12:59
Zvi
3,290223
edited Nov 8 at 14:40
asked Nov 8 at 12:59
Zvi
3,290223
asked Nov 8 at 12:59
Zvi
3,290223
asked Nov 8 at 12:59
Zvi
3,290223
3,290223
This question has an open bounty worth +50
reputation from Zvi ending in 5 days.
This question has not received enough attention.
The case $S$ is finite and $|S|>2$ is still unsolved. I believe that the answer is positive already when $m=2$. That is, for any $n$ there exists a $2$-ary function $f:S^2to S$ such that $f$ is $n$-fulfilling. I wouldn't be surprised if there exists one $f$ for all $n$.
This question has an open bounty worth +50
reputation from Zvi ending in 5 days.
This question has not received enough attention.
The case $S$ is finite and $|S|>2$ is still unsolved. I believe that the answer is positive already when $m=2$. That is, for any $n$ there exists a $2$-ary function $f:S^2to S$ such that $f$ is $n$-fulfilling. I wouldn't be surprised if there exists one $f$ for all $n$.
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday
add a comment |
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2989947%2fan-m-ary-function-that-represents-all-n-ary-functions%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
I've been thinking about this question on & off for 1+ week, and have made no progress whatsoever. In fact the more I think about it, the more it seems this is a very non-trivial result for $|S|=2$ i.e. the boolean case. For $|S| > 2$ if we are allowed to have TWO functions $f_1, f_2$ to compose with, then we can perhaps calculate any $g$ bit by bit and combine the results at the very end...?
– antkam
2 days ago
Can you clarify your bounty-comment? "I believe that the answer is positive already when $m=2$" $leftarrow$ do you mean the $|S|>2$ case? If so, what intuition makes you think so? Whereas if you mean the $|S| =2$ case, then I agree with your OP that it's equivalent to Boolean and NAND (or NOR) is a 2-ary $f$ that works for all $n$.
– antkam
yesterday
@antkam Let $f$ be an $m$-ary opertor with $mgeq 2$. My guess is due to the fact that there are infinitely many valid expressions of $f$ for any fixed number $n$ of variables, and there are only finitely many $n$-ary functions $g$. But frankly, this is a wild guess.
– Zvi
yesterday
hahaha, ok that is a pretty wild guess... in particular this line of logic would suggest that ANY $f$ would work (with obvious exceptions like functions whose range does not entirely cover $S$, and functions whose output always match at least 1 input). but i like your guess -- it is OPTIMISTIC. :)
– antkam
yesterday
@antkam The world is not too gloomy when you are optimistic :D.
– Zvi
yesterday