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.

  • $\begingroup$ Your definition seems to be a bit off. I think it should be that " $T$ is pure iff there are no $f$ and $g$ such that either: $\forall x,y,z: f(g(x,y),z) = T(x,y,z)$ or $\forall x,y,z: f(x,(x,g(y,z)) = T(x,y,z)$ or ... " and that is equivalent to: " $T$ is pure iff for every $f$ and $g$ we have that $\not \forall x,y,z: f(g(x,y),z) = T(x,y,z)$ and $\not \forall x,y,z: f(x,(x,g(y,z)) = T(x,y,z)$ and ... " and that is equivalent to: "$T$ is pure iff for every $f$ and $g$ we have that $\exists x,y,z: f(g(x,y),z) \not = T(x,y,z)$ and $\exists x,y,z: f(x,(x,g(y,z)) \not = T(x,y,z)$ ... $\endgroup$
    – Bram28
    Jun 26, 2017 at 19:28
  • $\begingroup$ I just realized my example is incorrect. I will try to correct it, but how do I put the question on hold or something, till I make my example correct? And that might be were the confusion about definition comes from. $\endgroup$
    – TStancek
    Jun 26, 2017 at 19:54
  • 1
    $\begingroup$ Hmmm, not sure how to put it on hold ....I would just make the corrections as needed and hope it doesn't trip anyone trying to answer the question ... maybe do a quick edit where you write at the top or bottom "EDITING ...." $\endgroup$
    – Bram28
    Jun 26, 2017 at 19:57
  • $\begingroup$ Is it intentional that the definition of purity permits a composition of the form $T(x, y, z) = f(g(x, z), y)$? $\endgroup$ Jun 27, 2017 at 9:54
  • $\begingroup$ Yes, it allows. It might be reasonable to extend it for this argument permutation, but I want the order of arguments preserved, I find it more "natural" this way. $\endgroup$
    – TStancek
    Jun 27, 2017 at 10:26

1 Answer 1



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),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)$


$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']

  • $\begingroup$ Nice summary, but I think the equivalence of "pure is if and only if..." is implication with "only if". Because it still might not be pure if the other grouping works. It would be equivalence in case you used something like "pure from left" definition instead. $\endgroup$
    – TStancek
    Jun 27, 2017 at 13:37
  • $\begingroup$ @TStancek Hmm, I am not sure I follow what you're saying here ... but I do note that you updated your definition to reflect exactly what I was saying :) $\endgroup$
    – Bram28
    Jun 27, 2017 at 14:54
  • $\begingroup$ $T$ is not pure if and only if for all $x,y,x′,y′x,y,x′,y′: T(x,y,1)=T(x′,y′,1)$ iff $T(x,y,0)=T(x′,y′,0)$ . The if and only if statement is incorrect. It is not pure if for all..., without the "only if", because when the condition is not met, there still might be the possibility it is not pure when apllying the inner function on the two operands on the right, And I was aware of that simplification, but the first definition I wrote was not the one I was working with, but once you wrote the first comment, I realized that. $\endgroup$
    – TStancek
    Jun 27, 2017 at 15:06
  • $\begingroup$ @TStancek Ah! OK, well, you could be right about that ... I did not check the other way around ,,, the post shows how far I got with this yesterday, and my intuition said that we had an iff here, but you're telling I was wrong! And yes, I see what you're saying about applying the inner function first, so I can totally believe that. Well ... I'll have to look at it some more. And this obviously does relate to the 'double-counting' point. So ... maybe there is a better way to figure this out ... $\endgroup$
    – Bram28
    Jun 27, 2017 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.