Re: Testing for the equivalence relation

From: Dan <>
Date: 1 Jul 2005 10:57:08 -0700
Message-ID: <>

Thank you Jan.

Another counter example that now seems so obvious in hindsight.

So this leads me to my real objective. I now am wondering how we apply this to a relational model of data, or to what degree it is applicable without modification? I have quite a few question, but I'll try to focus on only one for now.

Suppose I define an alphabet A to be the the set of symbols {'a', 'b',
'c', 'd', 'e'}, and the set of strings S over A consisting of the set
of 1-tuples such that formal language is defined as {'a', 'b', 'c',

'd', 'e'}. We can also refer to S as a domain S in some universe of

Further suppose that a binary relation is defined over S, is given as R(u: S, v: S); and we claim that it is an equivalence relation, and it has the following extensional value:

u       v
--       --
a        a
b        b
c        c
d        d
a        b
b        a
c        d
d        c

Here there are 4 equivalence classes and two distinct equivalence classes.

I can look at this relation and interpret whether it meets the criteria for reflexivity in several ways. For me, this has implications concerning the distinction between domain and type that are not really explicit, referential integrity, and the application of functional dependencies in terms of whether they are well defined in relationship to mathematical functions:

  1. For all x,y that are elements of S, we can see that the relation meets the criteria for symmetry and transitivity. However, because for all x that are elements of S, x is not related to itself for one element of S, that being 'e', R is not an equivalence relation.

If we were to further define a unary relation T defined as T(w: S) and impose a referential integrity constraint on the attributes of R such that for all (x, y) that is an element of R, both x and y must also be an element of T and the value of T is,



..we would still lack reflexivity in R by the rationale of 1. above,
but an alternative interpretation of domain could lead one to justify
calling R an equivalence relation by redefining the domains of u and v
in R as the extensional set of values of attribute w of T.  Or can we?

If there exists an x in S that is not in T(u), if one wants to
determine whether the criterion for reflexivity is met in this
particular example, are the domains of u and v in T(u,v) all elements
of S? or are they defined as,  for all x in S such that T(u)?.

For me, one of the benfits of answering this question is that it goes a
long way ascertaining a distinction between type and domain.

Thanks again for the help.


- Dan
Received on Fri Jul 01 2005 - 19:57:08 CEST

Original text of this message