how many “pure ternary” operators are there?

Question

Pure ternary operator is a function $T:A\times A\times A \to A$ such that for every pair of binary operators $f,g:A\times A \to A$ and for each of the following inequalities

• $f(g(x,y),z) \ne T(x,y,z)$
• $f(x,g(y,z)) \ne T(x,y,z)$

there is a triplet $x,y,z\in A$ for which the inequality holds

Basically I cannot replace T with two binary operators in a simple composition. Such ternary functions exist (for the set of size two): $$T(1,0,0)=1 \quad T(0,0,0)=0 \quad T(0,1,0)=1 \quad T(1,0,1)=1 \quad T(0,1,1)=0 \\ T(1,1,1)=0\;or\; 1 \quad T(1,1,0) = 0 \quad T(0,0,1)=1 \quad $$

Lets rule out the possibility the inner binary function is applied on the left two elements. Then the outer function has for the zero as its right argument two possible outcomes, so the inner function has to map the left(1,0) and (0,1) to the same element. But if that is true, than (1,0,1) and (0,1,1) needs to be mapped on the same element, but they are not.

The possibility of the inner function being applied on the right two elements can't happen neither. (0,1,0) and (0,1,1) have different images, but (0,1,0) and (0,0,1) have the same image, so the right (1,0) and (0,1) has to be mapped identically. That would imply (1,1,0) and (1,0,1) have the same image, but they do not. So no matter what operators I choose, I cannot use them in "simple" composition to obtain this ternary operator. Hope my proof is correct.

And such a way of constructing the "pure ternary" function could be (I think) applied for larger sets as well. I tried to google more information about it, but I was unsuccessful. Mostly I ended it up on topic related to Are all n-ary operators simply compositions of binary operators? . But I am interested only in this kind of composition.

So my question: Is there a way to calculate (without going through all possibilities) the number of "pure ternary" operators on a set of size $n$?

I really do not know how to approach this.

EDIT: Example of such a operator is incorrect, it works for a different definition. Please I will try to make correction, but I need some time, I was playing with for too long and lost it.

EDIT2: Based on Bram28 comment I changed the definition. I have been actually working with this definition anyway. This more strict version should be feasible at least on constructing the examples.

Answer 1

HINTS

First notice that if there aren't any $f$ and $g$ such that:

$$\forall x,y,z \ f(g(x,y),z) = T(x,y,z)$$

then there also won't be any $f$ and $g$ such that any of the following holds:

$$\forall x,y,z \ g(f(x,y),z) = T(x,y,z)$$ $$\forall x,y,z \ f(f(x,y),z) = T(x,y,z)$$ $$\forall x,y,z \ g(g(x,y),z) = T(x,y,z)$$

Likewise, if there aren't any $f$ and $g$ such that:

$$\forall x,y,z \ f(x,g(y,z)) = T(x,y,z)$$

then there also won't be any $f$ and $g$ such that any of the following holds:

$$\forall x,y,z \ g(x,f(y,z)) = T(x,y,z)$$

$$\forall x,y,z \ f(x,f(y,z)) = T(x,y,z)$$

$$\forall x,y,z \ g(x,g(y,z)) = T(x,y,z)$$

In other words: a ternary operator $T$ is 'pure' if and only if there aren't any $f$ and $g$ such that any of the following holds:

$$\forall x,y,z \ f(g(x,y),z) = T(x,y,z)$$

$$\forall x,y,z \ f(x,g(y,z)) = T(x,y,z)$$

Second, it may be easier to consider the ternary operators that are not pure. That is, what do the $T$'s look like for which we do have $f$ and $g$ that 'capture' $T$ in one of these ways?

To find such $T$, we can first consider those that can be captured by $f$ and $g$ such that

$$\forall x,y,z \ f(g(x,y),z) = T(x,y,z)$$

What kind of $T$ would allow for this? Well, suppose $T(x,y,1)=1$ for any $x$ and $y$. Then we can capture $T$ as follows: Set $g(x,y)=T(x,y,0)$, set $f(w,1)=1$, and set $f(w,0)=w$. Similarly, if $T(x,y,1)=0$ for any $x$ and $y$, we can capture $T$. And likewise, if $T(x,y,0)$ has the same value for all $x$ and $y$, $T$ is not pure.

OK, so now consider any $T$ for which $T(x,y,1)=0$ for some pairs of $x$ and $y$ and $T(x,y,1)=1$ for other pairs. In that case, $T$ is not pure if and only if for all $x,y,x',y'$: $T(x,y,1)=T(x',y',1)$ iff $T(x,y,0)=T(x',y',0)$. This is because if for all $x,y,x',y'$: $T(x,y,1)=T(x',y',1)$ iff $T(x,y,0)=T(x',y',0)$, then set $g(x,y)=T(x,y,1)$, $f(w,1)=w$, and $f(w,0)=w$ if for all $x,y$: $T(x,y,1)=T(x,y,0)$ and $f(w,0)=1-w$ if for all $x,y$: $T(x,y,1)\not =T(x,y,0)$, for then:

$f(g(x,y),1)=g(x,y)=T(x,y,1)$

and

$f(g(x,y),0)=g(x,y)= T(x,y,1)= T(x,y,0)$ if for all $x,y$: $T(x,y,1)=T(x,y,0)$

and

$f(g(x,y),0)=1-g(x,y)= 1-T(x,y,1) = T(x,y,0)$ if for all $x,y$: $T(x,y,1)\not =T(x,y,0)$

[now prove that if not if for all $x,y,x',y'$: $T(x,y,1)=T(x',y',1)$ iff $T(x,y,0)=T(x',y',0)$, then $T$ is pure]

[now we can fairly easily calculate how many such non-pure $T$'s there are]

[now consider the second case]

[finally, consider the 'double-counts']