Distinguishing things by relations

[Stephen Tashi]

What math is useful for distinguishing and classifying things based only on relations they satisfy?

For example the relation $R_1 = \{(a,b), (b,a)\}$ isn't useful for distinguishing "a" from "b" while the relation $R_2 = \{(a,b), (c,b) \}$ let's us distinguish "b" by the description "The thing that has two other things $R_2$ related to it".

In a more general case, we could have sets of symbols that satisfy more than one relation - or even infinite sets of symbols.

 

[andrewkirk]

I wonder if the following is as general as one can be for a single relation R.

For any set U be a set let $U^*=\bigcup_{k=1}^\infty U^k$.
Let $S$ be the set of elements we are interested in distinguishing.
Let $D'=\mathbb \{0,1\}^*\times S\times S\times S^*$ and let $D$ be the subset of elements $(\vec b,u,v,\vec w)$ of $D'$ such that $\vec b$ and $\vec w$ have the same length.

Define $f: D \to S^*$ such that $f(\vec b,u,v,\vec w)$ is what we get by starting with $\vec w$ and, for each $k\in \{1,...,\mathrm{length}( \vec w)\}$ replacing the $k$th element by $v$ iff that element is $u$ and $b_k=1$.

$f$ is the most general form of substitution function and gives all the possible ways of substituting one or more instance of one element for another in a tuple $\vec w$.

Then we can say that $k$-ary relation $R$ on $S$ distinguishes elements $u,v\in S$ iff there exists some $\vec b\in \{0,1\}^k$ and $\vec w\in S^k$ such that
$$\vec w\in R \wedge ( f(\vec b,u,v,\vec w)\notin R \vee f(\vec b,v,u,\vec w)\notin R)$$

In words, the relation distinguishes u and v if there is some tuple $\vec w$ in the relation such that when we replace one or more of the occurrences of u (or v) by the other, the modified tuple is no longer in the relation.

To generalise further, given a set H of relations on R, we can say that H distinguishes elements u, v if there is some relation R in H that distinguishes u and v.

EDIT: I realized we can simplify the criterion for a relation R distinguishing two elements - so that it only requires a single element switch. Let $K'=\mathbb N\times S\times S^*$ and let $K$ be the subset of elements $(n,u,v,\vec w)\in K'$ such that $n\leq \mathrm{length}(\vec w)$. Then define function $g:K\to S^*$ such that $g(n,v,\vec w)$ is $\vec w$ with the $n$th element replaced by $v$. Then it is reasonably straightforward to prove that relation R distinguishes $u,v\in S$ under the definition above iff there exists $\vec w\in S^*$ and $n\leq \mathrm{length}(\vec w)$ such that the $n$th component of $\vec w$ is $u$ or $v$ and

$$\vec w\in R \wedge ( g(n,v,\vec w)\notin R \vee g(n,u,\vec w)\notin R)$$

In words, $\vec w$ is in the relation but if we replace the $n$th element of it by whichever of u,v it is not, it is no longer in the relation.

 

[Stephen Tashi]

I'm not sure about the notation "$\wedge$" , "$\vee$" in that definition. Do they mean "and" and "or" ?

If a ternary relation contains (a,b,b), does the definition consider replacing only one occurrence of the "b" by "c". i.e. Do we consider the possibility (a,b,c) as well as (a,c,c) ?

Can we get a good definition by applying group theory? The path would be:
1) Define what it means for two relations to be homomorphic
2) Use that definition to define what it means for two relations to be isomorphic
3) Those definitions imply a definition of an automorphism of relation
4) Define a set of S things that appear as members of a relation R to be "of the same R-class" iff each permutation of an ordered set of those things induces an automorphism on R.

The general idea is that if $R_1$ is a relation on $S_1$ things and $R_2$ is a relation on $S_2$ things then any function $g: S_1 \rightarrow S_2$ can be applied to the tuples of $R_1$ "term by term" to define a
new relation. Denote that new relation by $g(R_1)$. Define "R_2 is homomorphic to R_1" to mean that there exists a function $g:S_1 \rightarrow S_2$ such that $g(R_1) = R_2$.

That definition is general enough to make $R_x = \{(c,c)\}$ homomorphic to $R_1 = \{(a,b),(b,a)\}$ via the mapping $g(a) = c, \ g(b) = c$. That definition wouldn't allow any 1-ary or ternary relation to be homomorphic to $R_1$.

 

[andrewkirk]

I'm not sure about the notation "$\wedge$" , "$\vee$" in that definition. Do they mean "and" and "or" ?

Yes that's right.

If a ternary relation contains (a,b,b), does the definition consider replacing only one occurrence of the "b" by "c". i.e. Do we consider the possibility (a,b,c) as well as (a,c,c) ?

Yes.
$(a,b,c)=f(\ (0,0,1),\ b,\ c,\ (a,b,b)\ )$ (replace b by c if it occurs in the third component)
$(a,c,c)=f(\ (0,1,1),\ b,\ c,\ (a,b,b)\ )$ (replace b by c wherever it occurs in either of the second or third components)

Using the simpler function $g$ defined in the 'EDIT', we can write these as:
$(a,b,c) = g(\ 3,\ c,\ (a,b,b)\ )$ (replace 3rd element by c)
$(a,c,c) = g(\ 3,\ c,\ g(\ 2,\ c,\ (a,b,b)\ )\ )$ (replace 2nd element by c, then replace 3rd element by c)