Revisions - MathOverflow

Return to Answer

z, not x

view source

edited May 13 2011 at 14:43

Goldstern
5,250●1●12●27

The answer to Q4 is yes. Let $X$ be any infinite set. Wlog $X= Z\times\mathbb N$, where there is a bijection $i:X\to Z\times \lbrace0\rbrace $. For $x=(z,n)$ write $x+1$ for $(x,n+1)$. (z,n+1)$. [Typo corrected.]

You are given countably many finitary functions $g_1, g_2, \ldots$. We may assume there is a pairing function $x*y$ among them, so we may as well assume that all of them are binary. (Due to Sierpinski, I think. E.g., $g(x,y,z) = h(x*(y*z)) $ for some unary $h$.)

Now there is a binary function $f$ satisfying the following for all $x,y\in X$:

$f(x,x) = x+1$.
$f(x, x+1) = i(x)$.
$f(i(x)+k,i(y)) = g_k(x,y)$ for $k=1,2,\ldots$.

Clearly $f$ generates the functions $x+1$, $i(x)$, and $g_k$ for all $k$.

fixed stupid error

view source

edited May 12 2011 at 17:08

Goldstern
5,250●1●12●27

The answer to Q4 is yes. Let $X$ be any infinite set. Wlog $X= Z\times\mathbb N$, where there is a bijection $i:X\to Z\times \lbrace0\rbrace $. For $x=(z,n)$ write $x+1$ for $(x,n+1)$.

Now there is a binary function $f$ satisfying the following for all $x,y\in X$:

$f(x,x) = x+1$.
$f(x, x+1) = i(x)$.
$f(i(x), y+k) f(i(x)+k,i(y)) = g_k(x,y)$ for $k=1,2,\ldots$.

Clearly $f$ generates the functions $x+1$, $i(x)$, and $g_k$ for all $k$.

view source

answered May 12 2011 at 17:02

Goldstern
5,250●1●12●27

The answer to Q4 is yes. Let $X$ be any infinite set. Wlog $X= Z\times\mathbb N$, where there is a bijection $i:X\to Z\times \lbrace0\rbrace $. For $x=(z,n)$ write $x+1$ for $(x,n+1)$.

Now there is a binary function $f$ satisfying the following for all $x,y\in X$:

$f(x,x) = x+1$.
$f(x, x+1) = i(x)$.
$f(i(x), y+k) = g_k(x,y)$ for $k=1,2,\ldots$.

Clearly $f$ generates the functions $x+1$, $i(x)$, and $g_k$ for all $k$.