Re: Can relational alegbra perform bulk operations?

On Oct 1, 11:25 am, Marshall <marshall.spi..._at_gmail.com> wrote:
> On Sep 30, 7:37 pm, David BL <davi..._at_iinet.net.au> wrote:
>
>
>
> > I would have thought that set theory itself cannot be regarded as an
> > algebraic structure - because it is not possible to form the set of
> > all sets (by Russell).
>
> No, that's not why. I don't actually see any reason to exclude
> sets from the study of algebraic structures. Perhaps the
> one reason would be that sets are generally at or near the
> foundational bottom of the mathematical hierarchy, and
> we risk circularity if we treat them as algebraic structures.
> Normally the "is-an-element-of" predicate is the only operator
> and it is left undefined.
>
> Russel's paradox is actually not difficult to deal with and only
> comes in to play if the system admits unrestricted set
> comprehension. That is, if you allow the construction of
> sets via a description of their members. A low-cost alternative
> to unrestricted comprehension is separation: start with a set,
> and construct a new set that contains those members of the
> original set that satisfy some predicate. (Instead of constructing
> a set that contains all sets that satisfy some criteria.)

Yes, an axiomatic system like ZFC is believed to be free from contradiction because it doesn't allow unrestricted comprehension.

However assuming an algebraic structure by definition involves a *set* of abstract elements, then I can't see how ZFC can itself be regarded as an algebraic structure.

> > Operators like 'union', 'intersection' and
> > 'element-of' don't have a domain and therefore are not functions.
>
> But they do have a domain: sets. In set theories such as
> ZFC, there aren't any members of the domain of discourse
> that aren't sets.

I'll try and show my reasoning as explicitly as possible...

Claim: Under ZFC there is no set which is defined as the

       set of all sets.

Proof: Suppose there exists U such that for all x, x is an

       element of U.  By the axiom of separation one can take
       the subset R of U

           R = { x in U :  not (x in x) }

       It then follows that if R is an element of R then it
       can't be an element of R, and if R is not an element of
       R then it must be an element of R.  Either way this is
       a contradiction which proves there is no such U.

Claim: The intersection operator is not a binary function

Proof: Every function has a domain which is by definition a

       set. If the intersection operator is a binary function
       then its domain is UxU where U is the set of all sets,
       but U is not a set under ZFC.  It follows that the
       intersection operator is not a binary function.

> > Wouldn't the RM suffer from the same limitation (well at least an
> > untyped version of the RM)?
>
> I don't think so. It is entirely possible to have a relational theory
> that only admits the existence of relations.
>
> I don't generally like the approach of having a set theory that
> only admits sets, but it's actually the more popular approach.

I suspect there is no such thing as the set of all relations. Received on Thu Oct 01 2009 - 06:17:21 CEST