Re: Relational symmetric difference is well defined

From: Jan Hidders <hidders_at_gmail.com>
Date: Wed, 20 Jun 2007 11:21:00 -0000

On 20 jun, 02:09, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
> Jan Hidders <hidd..._at_gmail.com> wrote innews:1182294540.670096.220200_at_n60g2000hse.googlegroups.com:
>
>
>
> > On 19 jun, 22:37, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
> >> Jan Hidders <hidd..._at_gmail.com> wrote
>
> >> >> {(x,z)| (Forall y : A(x,y) <-> B(y,z) }
>
> >> > Ok.
>
> >> >> which is a different query altogether since forall y: A(x,y) <->
> >> >> B(y,z) evaluates to true only in trivial cases and does not give a
> >> >> set valued join which was specified originally with set builder
> >> >> notation ! E.g. if you have
>
> >> >> A:
>
> >> >> 1 2
> >> >> 1 3
> >> >> 2 5
> >> >> 2 6
>
> >> >> B:
>
> >> >> 2 a
> >> >> 3 a
> >> >> 5 b
> >> >> 6 b
>
> >> >> then your formula will produce an empty set instead of {(1 a), (2
> >> >> b)} !
>
> >> > Really? For x="1", z="a" the formula says "forall y : A(1,y) <->
> >> > B(y,a)". For y=2 and y=3 the propositions A(1,y) and B(y,a) are
> >> > both true. For all other values for y both are false. So I would
> >> > think the formula holds for x=1, z=a.
>
> >> I was wrong by being pessimistic about the formula, but you are not
> >> right either. You formula is overly optimistic. Assuming
> >> quantification domains X = 1..100 and Z = 'a'..'z' and according to
> >> your predicate, the following pairs would be legit:
>
> >> (3, c), (4, d), (3, d),... etc., i.e. every pair such that A(x,y) and
> >> B (y,z) evaluate to false for each y.
>
> > They should. My claim was that it is equivalent with the set equality
> > join as defined by Vadim:
>
> > A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}={y|B(y,z)} }
>
> > and this also has these pairs in its result.
>
> That is true although it's trivial to specify that at least one relation
> is not empty. It's not so easy with the first-order formula, see below.
>
> >Of course this is not a
> > completely correct definition of the set equality join but, as already
> > indicated by Vadim, it's very easy to see how this can be fixed in the
> > definition and in the formula while staying in first-order logic (just
> > add "and (exists y : A(x,y)) and (exists y : B(y, z))").
>
> Are you saying that now you are using different 'y's to check the
> existence:
>
> (forall y: A(x,y) <-> B(y,z) ) and (exists y1: A(x, y1) and (exists y2: B
> (y2, z)
>
> ?

• Jan Hidders
Received on Wed Jun 20 2007 - 13:21:00 CEST

Original text of this message