Re: Reducibility

[Vaughan Pratt <pratt@cs.stanford.edu>]

The question as posed makes no sense.

To begin with, there are too many groups to form a set, so you need to
pose this as a question about classes rather than sets, and f needs to
map classes instead of sets.

Second, you must first specify a larger class of which the class of all
groups is a proper subclass.  Otherwise what does it mean for x not to
be a member of A?  In this case, what does it mean not to be a group?

If you make the larger class "everything" then f has an unmanageably
large domain.  What if you apply f to an anteater, for example?

Vaughan Pratt

On 7/19/2010 9:46 AM, Russ Abbott wrote:
> Hi,
>
> I apologize if this is off topic. I'm not sure where to direct this
> question.
>
> I'm interested in when one can say that one theory is reducible to another.
> Reducibility is defined: a set A is T-reducible to a set B if there is a
> function f of type T such that x is a member of A if and only if f(x) is a
> member of B. Mathematical groups are defined in terms of a 0 element, other
> elements, and an operation with certain properties. Let A be the set
> of mathematical
> groups (set of models of groups?).  Is there an interesting set B and
> function type T so that A is T-reducible to B?
>
> First of all, is that an interesting question to ask?  If so, how would one
> go about thinking about it?
>
> Thanks for any help or pointers you can give me.
>
> -- Russ Abbott
> ______________________________________
>
>     Professor, Computer Science
>     California State University, Los Angeles
>
>     cell:  310-621-3805
>     Google voice: 424-2Blue4
>     blog: http://russabbott.blogspot.com/
>     vita:  http://sites.google.com/site/russabbott/
> ______________________________________
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]