Reducibility

Reducibility

[Russ Abbott]

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/ ]

Re: Reducibility

[Vaughan Pratt]

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/ ]