Ternary relation

Here is an interesting discussion I had with a friend of mine. Rather i must say, it is one amongst the many interesting discussions I have had someone who more than just a friend.

He said: “We can study the limitation of human thought by computers” … he meant … “Computers do kind of reflect the limitation of human thought process”.

Umm … Philosophical, I thought.

One of the things he said elaborating his idea was as follows: “A ternary relation (or any n-ary relation) is always expressible as some interaction of binary relations”.

One (counter?)example which we are not able to still decide about whether the map from a set of three points not all on a line to their orthrocentre defines one.

I approached it as follows. Let * be a ternary relation, closed in set S. By this I mean,

\forall \, x,y,z \in S,\quad *(x,y,z)=w\in S

Do there exist two binary relations \phi and \varphi, both closed in S, so that

\forall \, x,y,z \in S,\quad*(x,y,z)=\phi(x,\varphi (y,z))\qquad \qquad \dots (1)

For a certain x\in S, if there exist two ordered pairs (y,z) and (y_1,z_1) such that (y,z)\ne (y_1,z_1),

(x,y,z)=(x,y_1,z_1)\qquad \qquad \dots (2)

Then we have a possibility that, \varphi(y,z)=\varphi(y_1,z_1). This is just a a possibility, it need not hold. This makes the cardinality of S significant.

If S is finite, for \varphi to be closed in S, the co-domain of \varphi should not have more elements than in S. We need to pack 2{|S|\choose 2} elements in n boxes, bringing (2) into play. This partitions the set of ordered pairs. Different maps n^{2{|S|\choose 2}} count the number of ordered pairs of binary relations (\phi,\varphi) satisfying (1).

If S is infinite, the do not encounter some of the problems as S\times S has same cardinality as S. Further, every complete order of S (every partial order is extendable to a complete order) gives rise to an natural ordering of S\times S, thus giving rise to a canonical bijection.

Some simple restrictions on * shall drastically affect the validality of (1). Like suppose, * is permutative, that is *(x,y,z)=*(\delta (x), \delta (y), \delta (z)) for some permutation \delta. Further finding such relations makes me clueless.

Challenges we have:

1. What is the general solution (in terms of mappings or solutions) when * is n-ary for some finite n? That is, when do we have \phi_1,\phi_2,\dots, \phi_{n-1} satisfying

*(x_1,x_2,\dots, x_n)=\phi_1(x_1,\phi_2(x_2\dots \phi_{n-1}(x_{n-1},x_{n}\underbrace{)\dots)}_{n-1}

2. Can we have restrictions on * which render the impossibility of (1)? For smaller finite n, this is computer doable.

3. The composition construct may be a goof up, there could be better ways of achieving a ternary relation in terms of binary relations.

Far in the horizons … ?

Advertisements

ನಿಮ್ಮದೊಂದು ಉತ್ತರ

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s