Irreducible ternary functions

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

D-503
Posts: 84
Joined: Sun Apr 15, 2012 11:35 pm UTC

Irreducible ternary functions

Postby D-503 » Sun Feb 03, 2013 4:02 am UTC

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.

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

Re: Irreducible ternary functions

Postby dudiobugtron » Sun Feb 03, 2013 5:26 am UTC

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.
Image

D-503
Posts: 84
Joined: Sun Apr 15, 2012 11:35 pm UTC

Re: Irreducible ternary functions

Postby D-503 » Sun Feb 03, 2013 5:35 am UTC

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.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Irreducible ternary functions

Postby antonfire » Sun Feb 03, 2013 7:33 am UTC

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-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 hx(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?

D-503
Posts: 84
Joined: Sun Apr 15, 2012 11:35 pm UTC

Re: Irreducible ternary functions

Postby D-503 » Sun Feb 03, 2013 9:04 am UTC

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.)

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Irreducible ternary functions

Postby mike-l » Sun Feb 03, 2013 9:15 am UTC

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)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Irreducible ternary functions

Postby dudiobugtron » Sun Feb 03, 2013 9:28 am UTC

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!

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.
Image

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Irreducible ternary functions

Postby mike-l » Sun Feb 03, 2013 9:48 am UTC

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
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Irreducible ternary functions

Postby notzeb » Sun Feb 03, 2013 11:01 am UTC

Here are some interesting variants:

1. Are there any partially ordered sets X and order preserving maps from X3 to X that can't be built out of order preserving maps from X2 to X?

2. Are there any topological spaces X and continuous maps from X3 to X that can't be built out of continuous maps from X2 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 X2 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µ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

D-503
Posts: 84
Joined: Sun Apr 15, 2012 11:35 pm UTC

Re: Irreducible ternary functions

Postby D-503 » Sun Feb 03, 2013 7:55 pm UTC

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?

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests