Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Distinguishing things by relations

Tags:
  1. Oct 5, 2017 #1

    Stephen Tashi

    User Avatar
    Science Advisor

    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) \}## lets 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.
     
  2. jcsd
  3. Oct 5, 2017 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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 realised 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.
     
    Last edited: Oct 5, 2017
  4. Oct 8, 2017 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    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##.
     
  5. Oct 8, 2017 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes that's right.
    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)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted