User doctor gibarian - MathOverflow

Cotensor vs exponential objects.

2012-06-20T09:06:01Z

Under which conditions can we say that the cotensor objects in a (closed) V-category are the exponential objects? It is just when V=Set?

Codomain fibration.

2011-12-31T10:48:12Z

It is known that the codomain fibration is given by a functor in the form $\mathcal{C}^{\rightarrow}\longrightarrow\mathcal{C}$ where $\mathcal{C}$ is a category having pullbacks and $\mathcal{C}^{\rightarrow}$ is the arrow category. It is also known (see B. Jacobs, Categorical Logic and Type Theory, Studies in Logic and the Foundations of Mathematics 141, North Holland, Elsevier, 1999. ISBN 0-444-50170-3) that the condition of $\mathcal{C}$ having pullbacks is necessary and sufficient.

In the same book can also be found the definition of a chain of fibrations in the form $\mathcal{C}^{\rightarrow\rightarrow}\longrightarrow\mathcal{C}^{\rightarrow}\longrightarrow\mathcal{C}$ etc and that it depends again on the condition of $\mathcal{C}$ having pullbacks.

My question is: could this sequence be defined as a fibration when $\mathcal{C}$ is just a cartesian category? Would the fibers be the same (that is: the slices over an object in $\mathcal{C}$)?

Category of graphs.

2010-01-17T18:52:05Z

Hello, I'm writting something about Malcev categories and monadicity. The fact is that I need to know if Graph is or not complete (have all finite limits). It seems easy but I would like a real answer (not my feelings saying that it is) and I don't find that information anywhere.

Thank you for your answers.

Parametrized natural numbers object.

2010-01-18T10:44:26Z

Lambek and Scott demonstrate in Introduction to higher order categorical logic the existence of a parametrized nno when we are in a cartesian closed category (CCC) with a "simple nno" and suggest the possibility of define a parametrized nno in the context of a cartesian category (CC) with a simple nno. In which cases can it be done in the context of a CC? Could it be done only with numerals or (in the more general case of a) strong nno?

Ximo.

Answer by Doctor Gibarian for Parametrized natural numbers object.

2010-01-19T10:51:57Z

So, here are some definitions about Natural Numbers Object (nno), that is a key concept in category theory related to Computer Science. They are given in Lambek and Scott (LS) in the following form:

A (simple) nno is a group of three (N,z,s) where N is an object and z (as zero) and s (as successor) morphisms in a category and the diagram $1\overset{z}{\longrightarrow}N\overset{s}{\longrightarrow}N$ is initial among all the diagrams in the form $1\overset{f}{\longrightarrow}Y\overset{g}{\longrightarrow}Y$
A parametrized nno is a group of three as the one above where the diagram $X\overset{(z,1_X)}{\longrightarrow}N \times X\overset{s \times 1_X}{\longrightarrow}N \times X$ is initial among all the diagrams in the form $X\overset{f}{\longrightarrow}Y\overset{g}{\longrightarrow}Y$

Barr and Wells propose to say the latter simply a nno because is the only of our interest. It is closely related to a descrption of the primitive recursive functions. A nno makes an object of a category behave as the natural numbers.

With all of these my questions are: while LS demonstrate the existence of a parametrized nno when we are in a cartesian closed category (CCC) with a (simple) nno...in which cases can it be done in the context of a CC (not closed)? Could it be done only with numerals in the sense of arrows $1\longrightarrow N^{k}$ standard (built up in terms of z and s morphisms)?

To ask about weak and strong nno's I would need more definitions, so I let it here for the moment. Thank you in advance and sorry for my english.

Ximo.

Freyd cover of a category.

2010-01-17T19:40:20Z

I’ve couldn’t find any information about the free category built up from that Freyd cover. Where can I find more about the Freyd cover of a category (not a topos!)?

Edit: The definition has been given in Lambek and Scott's "Higher order categorical logic". I think (according to L. Román) it is initial among all categories endowed with products and a weak nno.

Edit: (Added by Tom Leinster) Here's the definition of Freyd cover, taken from Lambek and Scott (22.1). Let $\mathcal{T}$ be a category with terminal object. Its Freyd cover $\hat{\mathcal{T}}$ is the comma category whose objects are the triples $(X, \xi, U)$ where:

$X$ is a set
$U$ is an object of $\mathcal{T}$
$\xi: X \to \mathcal{T}(1, U)$ is a function.

Lambek and Scott emphasize that $\hat{\mathcal{T}}$ has a terminal object and that it comes equipped with a terminal-object-preserving functor $G: \hat{\mathcal{T}} \to \mathcal{T}$. Strictly speaking, the Freyd cover is the pair $(\hat{\mathcal{T}}, G)$, not just the category $\hat{\mathcal{T}}$ itself.

Equalizer completion

2010-10-07T09:56:41Z

Can anybody give a definition of the equalizer completion of a cartesian category?

Is the method to get more or less as the regular and exact completions in the way that are given in: http://ncatlab.org/nlab/show/regular+and+exact+completions?

How is in that case the behaviour of the forgetful functor FL-->FP (where FL are categories with finite limits and FP categories with finite products)?

The difference between the Recursive and the Effective topos.

2010-04-18T14:11:04Z

I would like to know which is the real difference between the Recursive topos (in the sense of Mulry) and the Effective topos (in the sense of Hyland). Especially what is related to recursive functions. Do they have the same semantic power? I will be gratefull with some hints about texts related to this.

Thanks in advance.

PS: I don't give definitions because of their big extension, but I could give them if anybody wants.

Answer by Doctor Gibarian for The difference between the Recursive and the Effective topos.

2010-04-19T09:56:45Z

As far as I now (correct me if I'm wrong, please):

1 The recursive topos was introduced in "The topos of recursive sets", Thesis, Buffalo, 1980. It is $Rec=Sh_{J}(Set^{M^{op}})$ where:

-M is the monoid of total recursive functions in $\mathbb{N}$

-Sh relates to sheaves

-J is the canonical Grothendieck topology

One has to take some concrete ideals and pullbacks to have a representation of partial recursive functions through Rec.

2 For the Effective topos (introduced by Hyland in "The Effective Topos", Cambridge, 1982) I could suggest "An introduction to fibrations, the effective topos and modest sets" by W. Phoa and a shorter explanation in: http://xorshammer.com/2008/10/13/what-would-the-world-look-like-if-everything-was-computable-an-introduction-to-hylands-effective-topos/

Pullbacks for primitive recursive functions.

2010-02-25T15:15:49Z

Since a pullback of two functions f and g with common codomain into Set category is just a subset of cartesian product like this: {(x,y)/f(x)=g(y)} (with two more functions not important here) could this pullback set be the empty set in some cases (for exemple in the case of constant functions)?

My question is related to find pullbacks for primitive recursive functions, where the functions are all of them total and the domain and codomain are powers of natural numbers set. Which could be the aspect of those supposed pullbacks for constant functions since the empty set is not there available? Do they exist?

Equalizer objects in Set.

2010-01-31T10:49:01Z

An equalizer in a category $\mathcal{C}$ is a couple $(E,eq)$ consisting in an object $E$ and a morphism $eq:E\longrightarrow X$ so that $f\circ eq=g\circ eq$ for every pair of parallel morphisms $f,g:X\longrightarrow Y$ and if for every other object $O$ and morphism $m:O→X$ there exists a unique morphism $u:O→E$ so that $eq\circ u=m$ .

In the category $Set$ , by taking sets and functions between them, an equalizer is the set of elements of the common domain where the functions are equal, that is: $Eq(f,g)=\{x\in X/f(x)=g(x)\}$ with $X$ a set and $(f,g)$ a couple of parallel morphism in Set.

My question is: can we say that the equalizer set is minimal among all the equalizer sets (like $O$ in the definition)?

Thanks for participate.

Coequalizer in the category of primitive recursive functions

2010-01-22T19:17:35Z

What does a coequalizer in the category of primitive recursive functions look like? I know that in Set, a coequalizer is a minimum congruence but...what is it in particular in the category of primitive recursive functions (which is a subcategory of Set)?

Comment by Doctor Gibarian

2012-06-21T11:00:49Z

Thanks. Did you mean perhaps Hom(A,X) iso DAtensorX?

Comment by Doctor Gibarian

2012-01-16T16:13:51Z

Mh...that is not the simple fibration but a particular case of it (according to Jacobs). It is interesting for me anyway, it gives me some suggestions to work with. I was looking, however, for a fibration like this without pullbacks and it seems to be no possible. $C^{pr}$ has pullbacks as you say. Thank you anyway.

Comment by Doctor Gibarian

2012-01-10T10:28:43Z

Related to this discussion:I've found the concept of "standard model of a Lawvere Theory".What is it commonly referred to?Is it just the product preserving functor from a Lawvere Theory to Set in the original definition of a Lawvere Theory?

Comment by Doctor Gibarian

2010-12-30T07:52:00Z

Well, I have it. Cartesian categories with parametrized natural numbers object are called Skolem categories in "Joyal's arithmetic universes via type theory" of Maria Emilia Maietti, Electronic Notes in Theoretical Computer Science. Volume 69, February 2003, Pages 272-286. This concept is used there to build up Joyal Arithmetic universes and finally the category of primitive recursive predicates using type theory.

Comment by Doctor Gibarian

2010-12-29T20:53:53Z

You are right about the definition using slice categories. About the other I would love to know how to import diagrams from Lyx to show the explanation given in "On recursive principles in cartesian categories" L.Román.The definition I gave for parameterized was certainly incorrect:I tried to mimic non parameterized case since I didn't know how to add diagrams and I failed in my formulation.In that paper there are several equivalent formulations for cartesian and cartesian closed.I'll try to bring them here.Thanks,Andrej,do you know everything? ;-)

Comment by Doctor Gibarian

2010-12-29T14:05:49Z

Mh...no, otherwise you had an extra variable with no sense. Am I correct?

Comment by Doctor Gibarian

2010-12-29T13:21:46Z

So you mean: is it another way to pass from syntactic (what you call crude semantics) to semantic in every case?

Comment by Doctor Gibarian

2010-05-11T16:11:58Z

Yes, that's my doubt. What should one interpret by that expression as it appear? The reference: Cockett, J.R.B. "List-arithmetic distributive categories: Locoi" J. Pure Appl. Algebra 66, 1-29 (1990) page 6.

Comment by Doctor Gibarian

2010-05-11T09:24:17Z

It appears in "List-Arithmetic distributive categories" by Cockett with no other indication. Shall I supose that + means coproduct in every case? Is it just a constant coproduct followed by a product?

Comment by Doctor Gibarian

2010-04-20T14:45:58Z

What I know is that in both topos recursive functions can be represented. The problem for me is: though in Eff is quite easy to see how is it done (because recursive realizability is a quite easy concept) in Rec everything is harder. One reason is that Mulry's papers are more difficult to find than Hyland's. This is why I ask for (open, free) references. At the same time I would like to join Krishnaswami question here:mathoverflow.net/questions/21947/… made after mine. Thank you, A. Bauer, and...have you Mulry's key papers?

Comment by Doctor Gibarian

2010-04-18T14:26:51Z

Ok. Give me a while.

Comment by Doctor Gibarian

2010-02-28T12:55:01Z

A name could be enough but it would be better to find those conditions, S.Ramesh, mostly since the paper I mention below doesn't give too much info.

Comment by Doctor Gibarian

2010-02-25T17:35:21Z

Yes, you can construct that diagram and that (prim rec) set but not to do it with all pair of functions. So that category has not pullbacks, as Reid Barton explains below. I was not sure about it. Thank you to all.

Comment by Doctor Gibarian

2010-02-25T16:34:30Z

Mh. In that case the square giving raise to the pullback woludn't be commutative and therefore the pullback set would be empty. Isn't it? My question is: could we make that for prim. rec. functions (where all of them are total and we've not the empty set as a possible domain)? Have they pullbacks? F.G.Dorais: I wish I could find that info in the web you send, but I don't see it there. Thank you anyway.

Comment by Doctor Gibarian

2010-02-25T15:37:32Z

Pullback to a point? You mean a degenerate case of a pullback? Makes it any sense? And..what if we haven't the empty set available?