Re: Relational symmetric difference is well defined

From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Wed, 20 Jun 2007 02:09:54 +0200 (CEST)
Message-ID: <Xns9954CD22DEB6Dvdghher@194.177.96.26>

Jan Hidders <hidders_at_gmail.com> wrote in news: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
>> innews:1182264646.065242.294970_at_e9g2000prf.googlegroups.com: 
>>
>>
>>
>>
>>
>> >> {(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)

?

Or you are doing this:
forall y: ( ( A(x,y) <-> B(y,z) ) and (exists y: A(x, y1) and (exists y: B(y, z) )

(note bracket placement)

?

If yes, then new 'y's do not help you any because 'forall' will still allow the 'bad' pairs.

>In fact, the

> biggest problem seems to be to get the brackets right. (Sorry
> Vadim! ;-))
>
> -- Jan Hidders
>
>
Received on Tue Jun 19 2007 - 19:09:54 CDT