size_question

size_question

[Eduardo Dubuc]

This is a naive question on non naive foundations.

Consider the inclusion S_f C S  of finite sets in sets.

Is the category S_f closed under finite limits and at the same time small ?

For example, there are a proper class of singletons, all finite. Thus a
proper class of empty limits.

Question, which is the small category of finite sets ?, which are its
objects ?.

A small site with finite limits for a topos would not be closed under
finite limits ?

etc etc

But, more basic is the question above: How do you define the small
category of finite sets ?

Or only there are many small categories of finite sets ?

You can not define a finite limit as being any universal cone because
then you get a large category.

Then how do you determine a small category with finite limits without
choosing (vade retro !!) some of them. And if you choose, which ones ?

The esqueleton is small but a different question !!

e.d.


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

Re: size_question

[James Lipton]

Eduardo:
   For a small cat of finite sets: Why not use the Von Neumann hierarchy (up
to omega) for objects, and all set
functions as arrows. These are the "hereditarily finite sets"

    V(0) = empty set

   V(n+1) = P(V(n))

V(omega) = U{V(n): n in omega}

I would not call it "the" cat of finite sets, since there uncountably many
countable models of ZF. Obviously the choice of ZF, rather than say Zermelo
set theory or some other foundation is also pretty arbitrary.
Best,
   J. Lipton

On Tue, Jun 28, 2011 at 1:39 PM, Eduardo Dubuc <edubuc@dm.uba.ar> wrote:

> This is a naive question on non naive foundations.
>
> Consider the inclusion S_f C S  of finite sets in sets.
>
> Is the category S_f closed under finite limits and at the same time small ?
>
> For example, there are a proper class of singletons, all finite. Thus a
> proper class of empty limits.
>
> Question, which is the small category of finite sets ?, which are its
> objects ?.
>
> A small site with finite limits for a topos would not be closed under
> finite limits ?
>
> etc etc
>
> But, more basic is the question above: How do you define the small
> category of finite sets ?
>
> Or only there are many small categories of finite sets ?
>
> You can not define a finite limit as being any universal cone because
> then you get a large category.
>
> Then how do you determine a small category with finite limits without
> choosing (vade retro !!) some of them. And if you choose, which ones ?
>
> The esqueleton is small but a different question !!
>
> e.d.
>

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

Re: size_question

[Andrej Bauer]

On Wed, Jun 29, 2011 at 4:43 AM, James Lipton <jlipton@wesleyan.edu> wrote:
> These are the "hereditarily finite sets"
>
>    V(0) = empty set
>
>   V(n+1) = P(V(n))
>
> V(omega) = U{V(n): n in omega}
>
> I would not call it "the" cat of finite sets, since there uncountably many
> countable models of ZF. Obviously the choice of ZF, rather than say Zermelo
> set theory or some other foundation is also pretty arbitrary.

I should think that the hereditarily finite sets do not depend all
that much on the background setting. After all, there are not very
many of them and they are quite concrete. Can they really be hugely
different depending on whether we work in ZF, ZFC, IZF, CZF etc?

With kind regards,

Andrej


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

Re: size_question

[Thomas Streicher]

> I should think that the hereditarily finite sets do not depend all
> that much on the background setting. After all, there are not very
> many of them and they are quite concrete. Can they really be hugely
> different depending on whether we work in ZF, ZFC, IZF, CZF etc?

If we are not working classically subsets of finite sets need not be
finite but the sets in V_\omega are closed under subsets.

Thomas


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

Re: size_question

[F. William Lawvere]

In the absence of AC, we need to specify which notions of"finite" we are using. Certainly K-S (= locally quotient of standard numeral) while important is by no means the endof the story. We categorists do not seem to yet have a way of dealing  elegantly with the locally Noetherian, coherent,etcsheaves in terms of internal finiteness notions.
The SUBQUOTIENTS of standard numerals would surely be important. I recall the existence of intuitionist literature on this, but it seemed to assume that subquots of subquots etc would be an infinite sequence. Of course in a  category with reasonable pullbacks and pushouts this relation is already transitive (indeed an important subcategory of spans).
  But the original question actually had to do with the observation that for any qualitative definition of finite set, there are probably as many as there things in the ambient universe. We need an axiom of infinity to say that there is a category object that represents that metacategory UP TO EQUIVALENCE OF COURSE. 
The uniqueness is only relative to the ambient universe . The Incompleteness Theorem would seem to imply that there are an infinite number of non-elementarily-equivalent ambient universesand hence of these little metacategories in particular.
We really should overcome the ritual belief that such things must be defined by iteration (as opposed to being partially investigated via iteration). Already Peano misrepresented Grassmann's views on this.
Dedekind proposed that a set  A is finite if any idempotent whose fixed part is isomorphic to all of A is itself an automorphism. This seems difficultto relate to operations such as product. However note that it is an elementary axiom to require that all objects of a given topos satisfy it. It would see to propagate to any finite (in the sense of Artin) topos over such. Do basictheorems, such as the essentialness  of all geometric morphisms, extend to this axiomatic setting ?
A different elementary axiom on a topos is the requirement that every object A is fixed by the monad obtained by composing 3^( ) with its adjoint from the related topos of left actions of 3^3.
Are these two theories equivalent ? Such a finitely-axiomatized T defines "the" category of finite sets as any one that represents up to equivalence the submetacategory of the ambient universe consisting of all discrete categories that are finite in the stated sense.( But then of course there are many  models of T not equivalent to that)
I proposed the study of such an "Objective Number Theory" in Braga four years ago at a European computer science meeting without much response. It is known since Craig-Vaught that Peano's arithmetic can be embedded in a finitely axiomatizable theory,but it seems reasonable to try to find such an expansion with an objective content.If E is such a category, the Paris-Harrington theory seems to be about the topos E^Iwhere I is the arrow category; but don't the properties of that follow from those of E ?
Bill
PS Of course this ONT is not the same as (though related to) my ongoing  work with Schanuel and Menni.
> Date: Sat, 2 Jul 2011 22:05:05 +0200
> From: streicher@mathematik.tu-darmstadt.de
> To: andrej.bauer@andrej.com
> CC: jlipton@wesleyan.edu; categories@mta.ca
> Subject: categories: Re: size_question
> 
>> I should think that the hereditarily finite sets do not depend all
>> that much on the background setting. After all, there are not very
>> many of them and they are quite concrete. Can they really be hugely
>> different depending on whether we work in ZF, ZFC, IZF, CZF etc?
> 
> If we are not working classically subsets of finite sets need not be
> finite but the sets in V_\omega are closed under subsets.
> 
> Thomas

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

Re: size_question

[Gaucher Philippe]

Le mardi 28 juin 2011 19:39:10, vous avez écrit :
> This is a naive question on non naive foundations.
> 
> Consider the inclusion S_f C S  of finite sets in sets.
> 
> Is the category S_f closed under finite limits and at the same time small  ?
> 
> For example, there are a proper class of singletons, all finite. Thus a
> proper class of empty limits.

This is the definition of quasi-small, not small: a set of isomorphism classes 
? The category of finite sets is quasi-small, not small. And we need the axiom 
of choice for that, as for many things in category theory. 

pg.



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