1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Distinguishing things by relations
  1. Root thing (Replies: 2)

  2. How are things proven? (Replies: 4)

Loading...