Catégorie des fonctions partielles

Foys

Dans ce message, $\mathcal C$ désigne la catégorie dont les objets sont des ensembles et pour tous $A,B$, les flèches de $A$ dans $B$ sont les fonctions partielles de $A$ dans $B$, et qui est munie de la composition de fonctions.

Formellement, étant donnés deux ensembles $A$ et $B$, une fonction partielle de $A$ dans $B$ est une partie $f$ de $A\times B$ telle que pour tous $x\in A$, $y\in B$ et $z\in B$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y=z$. Etant donné un ensemble $C$, La composition d'une fonction partielle $u $ de $A$ dans $B$ et d'une fonction $v$ de $B$ dans $C$ est l'ensemble des couples $(p,q)$ tels qu'il existe $r\in B$ tels que $(p,r)\in u$ et $(r,q)\in v$. On vérifie qu'il s'agit d'une fonction partielle de $A$ dans $C$, que l'on note $v \circ u$.

Exercice.
1°) Montrer que $\mathcal C$ possède des produits cartésiens.
2°) Montrer que $\mathcal C$ n'est pas une catégorie cartésienne fermée.

raoul.S

Pour le 1) c'est le produit cartésien usuel de deux ensembles et on vérifie facilement que tout fonctionne, je laisse en exercice la vérification de la propriété universelle .

Pour le 2) il faut montrer qu'il n'existe pas toujours d'objet exponentiel (si j'ai bien suivi la définition de Wikipédia)

Voici un contre exemple normalement : si on considère les ensembles $A:=\{1\}$ et $B:=\{1,2\}$ alors il n'existe pas d'objet $A^B$ et de morphisme $eval:A^B\times B\to A$ qui vérifient la propriété universelle dans cette catégorie.

Pour le voir il suffit de considérer les deux applications $g_1:\{1\}\times B\to A, (1,1)\mapsto 1, (1,2)\mapsto 1$ et $g_2:\{1\}\times B\to A, (1,1)\mapsto 1$.

(remarquer que $g_2$ n'est définie que partiellement, ce qui fait tout foirer... les détails sont laissés en exercice aux éventuels lecteurs )

Foys

@raoul.S il y a un petit problème pour ton 1°)

En fait comme une fonction partielle de $A$ dans $B$ est essentiellement la même chose qu'une fonction totale de $A$ dans $B \cup \{error\}$  avec $error\notin B$, on en déduit que $Hom_{\mathcal C} (A,B) = \left ( 1+\text{card}(B )\right) ^{\text{card}(A)}$ ce qui va avoir certaines conséquences intéressantes; notamment en exploitant le fait que, comme pour tous $A,B$ dans $\mathcal C$, $Hom_{\mathcal C} (M,A\times_{\mathcal C} B )$ est en bijection avec $Hom_{\mathcal C} (M,A) \times Hom_{\mathcal C}(M,B )$, on ne pourra pas avoir $A \times B = A \times_{\mathcal C} B$.

raoul.S

Humm je suis passé à côté d'un truc intéressant en effet.

@Foys je me corrige : le produit de $A$ et $B$ est le suivant : $A \times_{\mathcal C} B:=A\times B \sqcup A\times\{error\} \sqcup \{error\}\times B$ avec $error$ un élément qui n'est ni dans $A$ ni dans $B$. Les projections étant données par $p_A$ et $p_B$ avec $p_A:A \times_{\mathcal C} B\to A$ définie seulement sur $A\times B\sqcup A\times\{error\}$ et égale à la projection habituelle  (idem pour $p_B$ en inversant les rôles).

GaBuZoMeu

Bonsoir,

Cette catégorie n'est-elle pas équivalente à la catégorie des ensembles pointés (structures avec juste une constante) ?

Médiat_Suprème

Est-ce que je me trompe :
$A= \{0, 1\}$, $f :A \to A$ définie par $f(0)=0$
$B= \{0, 1\}$, $g :B \to B$ définie par $g(0)=0$
Alors $f\times g : A\times B \to A\times B$ est définie par $f\times g ((0, 0)) = (0, 0)$

Foys

GaBuZoMeu a dit :

Bonsoir,

Cette catégorie n'est-elle pas équivalente à la catégorie des ensembles pointés (structures avec juste une constante) ?

Oui (avec dans un sens un foncteur qui rajoute le terme d'erreur et dans l'autre un qui enlève l'objet pointé). D'où une description plus simple du produit cartésien.

raoul.S

J'ai vérifié comme exo l'équivalence dont vous parlez ci-dessus et tout semble fonctionner.

Plus précisément on a le foncteur : $F: \mathcal C \to \textrm{Ens}_{*}, X\mapsto (X\sqcup\{e\},e)$ où $e$ est un ensemble fixé, représentant "l'erreur" ainsi que le foncteur $G:\textrm{Ens}_{*}\to \mathcal C , (X,x_0)\mapsto X\setminus \{x_0\}$. Je n'écris pas l'image des morphismes car c'est pénible en latex, mais on vérifie bien que $FG\simeq 1_{\textrm{Ens}_{*}}$ et $GF\simeq 1_{\mathcal C}$.

Par conséquent j'ai fait le produit cartésien de deux objets dans $\textrm{Ens}_{*}$ et je suis revenu en arrière via $F$ pour obtenir le produit cartésien dans $\mathcal C$ et je trouve effectivement ce que j'avais trouvé ICI.

En tout cas merci pour l'exemple Foys, il était intéressant.

Thierry Poma

@raoul.S : bonsoir. En théorie des catégories, les objets sont utile à peu de choses. Ce sont les morphismes et les foncteurs qui sont fondamentaux. Dans ladite catégorie, un morphisme d’ensembles pointés $\varphi:(E,\,e)\to(F,\,f)$ n'est autre qu'une application $\phi_{_{e\to{}f}}:E\to{}F$ (dans la catégorie-mère qu'est la catégorie des ensembles) telle que $\phi_{_{e\to{}f}}(e)=f$. Remarquons que $E$ et $F$ sont nécessairement des ensembles non vides.

raoul.S

@Thierry Poma oui, ceci dit a priori on réfléchit plus facilement dans $\textrm{Ens}_{*}$ pour faire le produit, que dans la catégorie initiale du fil. Quoi qu'en explicitant les deux foncteurs ci-dessus je me suis mieux rendu compte de la familiarité des deux catégories en fait.  

Foys

Qu'est-ce qui empêche $\mathcal C$ (ou sa variante: la catégorie des ensembles pointés) d'être cartésienne fermée ?
Indication.

Étant donnés 3 objets $P,Q,R$, $Hom_{\mathcal C} (P, R^Q)$ et $Hom_{\mathcal C}(P \times_{\mathcal C} Q,R)$ sont en bijection. Mais maintenant qu'on a identifié $P\times_{\mathcal C} Q$ et qu'on sait calculer $\text{card}\big ( Hom_{\mathcal C}(M,N)\big)$ pour tous $M,N$ (voir mon message plus haut ou faire le dénombrement dans la catégorie des ensembles pointés), on peut regarder ce qui se passe avec des $P,Q,R$ finis de divers cardinaux.

raoul.S

Du moment que $\text{card}\big ( Hom_{\mathcal C}(M,N)\big)=(\text{card}(N)+1)^{\text{card}(M)}$ et que $\text{card}(Hom_{\mathcal C}(P \times_{\mathcal C} Q))=\text{card}(P)\text{card}(Q)+\text{card}(P)+\text{card}(Q)$
on a : $\text{card}\big ( Hom_{\mathcal C}(P \times_{\mathcal C} Q,R)\big)=(\text{card}(R)+1)^{\text{card}(P)\text{card}(Q)+\text{card}(P)+\text{card}(Q)}$.

Or si $R^{Q}$ existait on aurait $\text{card}(Hom_{\mathcal C} (P, R^Q))=(\text{card}(R^Q)+1)^{\text{card}(P)}$. En particulier pour  $\text{card}(P)=0$ et $\text{card}(Q)=\text{card}(R)=1$ on aurait d'un côté $\text{card}\big ( Hom_{\mathcal C}(P \times_{\mathcal C} Q,R)\big)=2$. D'un autre côté $\text{card}(Hom_{\mathcal C} (P, R^Q))=(\text{card}(R^Q)+1)^{\text{card}(P)}=1$.

Alesha

Ne peut-on pas simplement évoquer le fait que dans une catégorie cartésienne fermée ayant un objet initial $0$, on a $A \times 0 \simeq 0$ pour tout $A$ et que, ici, l'ensemble vide est initial et que $\{ \ast \} \times \emptyset = \{ \ast \}$?

Foys

Alesha
Je ne connaissais pas ce critère ! Ça va bien plus vite comme ça.
[Inutile de reproduire le message précédent. AD]

Alesha

C'est un cas particulier du fait qu'un adjoint à gauche préserve les colimites.

Foys

Ou plus simplement: étant donné un objet $A$ pour tout objet $B$, $Hom(0 \times A,B) \simeq Hom(0,B^A)$, le membre de droite est un singleton donc celui de gauche aussi et donc $0\times A$ ($\simeq A \times 0$) est initial.

raoul.S

C'est vrai que c'est beaucoup plus simple que tout ce LaTeX que tu m'as fait écrire Foys...