I'm going to attempt to define the simplest possible irreducible ternary function.

"irreducible ternary function" is my own term, there might be another name for the idea that I don't know about.

I don't mean irreducible in the sense of polynomial irredicibility (at least I don't think so).

Irreducible ternary functions are functions that cannot be represented as a bounded number of binary functions.

To give an idea, a *reducible* binary function would be f(x,y)=x

It is reducible because it could be defined with a unary identity function.

Addition would be an irreducible binary function. I need a recursive axiom to define it:

add(x,y) = add(y,x)

add(x,0) = x

add(x,successor(y)) = successor(add(x,y))

It's easy to define a irreducible binary function because its value simply has to depend on both of it's arguments.

Irreducible ternary functions seem harder because binary functions can combine arguments in many ways.

Is this function irreducible?

tern(x,y,z) = tern(z,y,x)

tern(x,y,0) = tern(x,0,y) = add(x,y)

tern(add(x,y), y, z) = tern(x,add(x,y), z)

Is it even well defined?

I'm trying to in a way mimic addition, but I'm not sure about the last axiom.

## Irreducible ternary functions

**Moderators:** gmalivuk, Moderators General, Prelates

- dudiobugtron
**Posts:**1098**Joined:**Mon Jul 30, 2012 9:14 am UTC**Location:**The Outlier

### Re: Irreducible ternary functions

I'm not sure exactly what you're aiming for, or what problems you are trying to solve, but a definition of 'tern' you might be after is:

tern(x,y,z) = add(add(x,y),z)

You could show pretty easily the other properties it appears you're after, depending on how you define 'successor'.

Also it should be 'irreducible' according to your definition.

tern(x,y,z) = add(add(x,y),z)

You could show pretty easily the other properties it appears you're after, depending on how you define 'successor'.

Also it should be 'irreducible' according to your definition.

### Re: Irreducible ternary functions

Unfortunately that wouldn't fit my definition because you defined tern it in terms of binary functions.

For a function to be an irreducible n-ary function it must be impossible to definite with only (less than n)ary functions.

There's no problem I have in mind for this. I'm just trying to explore the concept.

For a function to be an irreducible n-ary function it must be impossible to definite with only (less than n)ary functions.

There's no problem I have in mind for this. I'm just trying to explore the concept.

### Re: Irreducible ternary functions

If your functions are allowed to have any domain and codomain, then any ternary function is reducible. Let h be a function that takes arguments in X, in Y, and in Z, and spits out an element of W. Take p to be the function that takes arguments in X and Y, and spits out an element of XxY, given by p(x,y) = (x,y). Take h' to be the function which takes an argument in XxY and an argument in Z, and spits out an element of W, given by h'((x,y),z) = h(x,y,z). Then h(x,y,z) = h'(p(x,y),z).

So to make it an interesting question, let's say every input and output has to belong to some fixed set X. If X is infinite, there's a bijection phi between XxX and X, so we can essentially do the same thing as before. This time p(x,y) = phi((x,y)), and h'(w,z) = h(x,y,z), where (x,y) = phi

So the question is only interesting if X is finite. Hint: given a ternary function h on a finite set X, consider the binary functions h

So to make it an interesting question, let's say every input and output has to belong to some fixed set X. If X is infinite, there's a bijection phi between XxX and X, so we can essentially do the same thing as before. This time p(x,y) = phi((x,y)), and h'(w,z) = h(x,y,z), where (x,y) = phi

^{-1}(w). Again, h(x,y,z) = h'(p(x,y),z).So the question is only interesting if X is finite. Hint: given a ternary function h on a finite set X, consider the binary functions h

_{x}(y,z) = h(x,y,z).Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: Irreducible ternary functions

Hi Anton, Maybe I'm just tired but I find something not quite satisfying about your answer.

I'll try to explain by appling your idea to the add function:

I could define a bijection that allows me to do this:

add(x,y) = add'(foo(z))

But what if I were to compute the value of add(1,1) in a formal way where each step is derived from an axiom.

E.g. add(1,1) = add(1, successor(0)) = successor(add(1, 0)) = successor(1)

It seems like the bijection adds an additional step, and I would need to map back to a binary function to compute the answer.

Is it possible to fully define addition from the ground up using only unary functions?

If not, perhaps I could modify my definition of irreducible n-ary functions to take that into account (i.e. irreducible n-ary functions require using (n or greater)-ary functions to evaluate.)

I'll try to explain by appling your idea to the add function:

I could define a bijection that allows me to do this:

add(x,y) = add'(foo(z))

But what if I were to compute the value of add(1,1) in a formal way where each step is derived from an axiom.

E.g. add(1,1) = add(1, successor(0)) = successor(add(1, 0)) = successor(1)

It seems like the bijection adds an additional step, and I would need to map back to a binary function to compute the answer.

Is it possible to fully define addition from the ground up using only unary functions?

If not, perhaps I could modify my definition of irreducible n-ary functions to take that into account (i.e. irreducible n-ary functions require using (n or greater)-ary functions to evaluate.)

### Re: Irreducible ternary functions

It would seem this definition isn't "interesting", as irreducible only applies to binary functions and means exactly those functions that aren't constant in one of their variables. The argument Anton gives works for any higher arity (and actually shows that any function can be written as the composition of binary functions.)

Having said that, we might get something interesting if we require computable functions, as I don't believe ther is a computable injection from RxR to R

D-503, Anton's argument fails for binary functions as the map f(x,y)=z is itself a binary function, so using it doesn't "reduce" a binary function, but it does reduce an n-ary function for any larger n

On N we can do this concretely. Given a ternary function t(x,y,z), define f(x,y)=2^x3^y, and define g(x,y) = t(p,q,y) where 2^p is the largest power of 2 dividing x and 3^q is the largest power of 3 dividing x. Then t(x,y,z) = g(f(x,y),z).

We may do the same for a binary function (now g is unary), but we end up with b(x,y) = g(f(x,y)), which still has a binary function. As I said, a binary function is "irreducible" if and only if it is not constant in both variables (this is also true on a finite domain)

Having said that, we might get something interesting if we require computable functions, as I don't believe ther is a computable injection from RxR to R

D-503, Anton's argument fails for binary functions as the map f(x,y)=z is itself a binary function, so using it doesn't "reduce" a binary function, but it does reduce an n-ary function for any larger n

On N we can do this concretely. Given a ternary function t(x,y,z), define f(x,y)=2^x3^y, and define g(x,y) = t(p,q,y) where 2^p is the largest power of 2 dividing x and 3^q is the largest power of 3 dividing x. Then t(x,y,z) = g(f(x,y),z).

We may do the same for a binary function (now g is unary), but we end up with b(x,y) = g(f(x,y)), which still has a binary function. As I said, a binary function is "irreducible" if and only if it is not constant in both variables (this is also true on a finite domain)

addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

- dudiobugtron
**Posts:**1098**Joined:**Mon Jul 30, 2012 9:14 am UTC**Location:**The Outlier

### Re: Irreducible ternary functions

For each element y of X, you can define a unary function y(x) gives the same answer as add(x,y)

Then define add(x,y) = y(x)

But that's probably cheating!

What does 'computable' mean in this sense? Eg, you could define a function on [0,1)x[0,1) which takes (x,y) to the real number which has the digits of x in the odd decimal places, and the values of y in the even decimal places.

Then define add(x,y) = y(x)

But that's probably cheating!

mike-l wrote:Having said that, we might get something interesting if we require computable functions, as I don't believe there is a computable injection from RxR to R

What does 'computable' mean in this sense? Eg, you could define a function on [0,1)x[0,1) which takes (x,y) to the real number which has the digits of x in the odd decimal places, and the values of y in the even decimal places.

### Re: Irreducible ternary functions

I was going with Anton's restrictions that the domain and range are constant, so in your example you are mapping y to a function, which doesn't meet this criteria

You're right about a computable function from RxR to R though. You should modify it slightly to take care of numbers with 2 representations. But yeah, I was mistaken about that

You're right about a computable function from RxR to R though. You should modify it slightly to take care of numbers with 2 representations. But yeah, I was mistaken about that

addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

### Re: Irreducible ternary functions

Here are some interesting variants:

1. Are there any partially ordered sets X and order preserving maps from X

2. Are there any topological spaces X and continuous maps from X

Of course we can generalize to other categories as well...

For problem 1: if X is a finite Boolean lattice then the universality of the And and Or gates for monotone circuits and a little thought show there are no irreducible ternary functions. If X is an infinite Boolean lattice, then X

1. Are there any partially ordered sets X and order preserving maps from X

^{3}to X that can't be built out of order preserving maps from X^{2}to X?2. Are there any topological spaces X and continuous maps from X

^{3}to X that can't be built out of continuous maps from X^{2}to X?Of course we can generalize to other categories as well...

For problem 1: if X is a finite Boolean lattice then the universality of the And and Or gates for monotone circuits and a little thought show there are no irreducible ternary functions. If X is an infinite Boolean lattice, then X

^{2}has an order preserving bijection to X, so again you can build any ternary functions up out of binary functions. I haven't thought about more general posets...Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ

### Re: Irreducible ternary functions

Upon further thought, I think the bijection to binary functions idea may not show irreducibly according to my original definition.

Take this function for example:

sqrt(multi(x,x)) = x

The same input for sqrt can have multiple values. It is conceivable that there is a function where some inputs map to an unbounded number of values, in which case I don't think the bijection is possible.

Can anyone show that my definition of tern does not have this property?

Edit:

Never-mind about that idea, I don't think it bears any consequence on whether a bijection is possible any more. However, I still think there may be an interesting problem here if irreducible n-ary function is defined in terms of the functions needed to evaluate it.

Take this function for example:

sqrt(multi(x,x)) = x

The same input for sqrt can have multiple values. It is conceivable that there is a function where some inputs map to an unbounded number of values, in which case I don't think the bijection is possible.

Can anyone show that my definition of tern does not have this property?

tern(x,y,z) = tern(z,y,x)

tern(x,y,0) = tern(x,0,y) = add(x,y)

tern(add(x,y), y, z) = tern(x,add(x,y), z)

Edit:

Never-mind about that idea, I don't think it bears any consequence on whether a bijection is possible any more. However, I still think there may be an interesting problem here if irreducible n-ary function is defined in terms of the functions needed to evaluate it.

### Who is online

Users browsing this forum: No registered users and 11 guests