Quali grafi rappresentano categorie?
Leggo in un testo di teoria delle categorie che il grafo sottostante di una categoria è il grafo che ha come vertici gli oggetti e come archi i morfismi. Ok. Poi mi dice che ogni grafo genera una categoria detta categoria libera che ha come oggetti i vertici e come morfismi i percorsi (una sequenza finita di archi ognuno adiacente a quello precedente, insomma ci siamo capiti... ) fra i vertici. Ok. Poi mi chiede in un esercizio "dati i seguenti grafi determinare quali fra essi costituiscono il grafo sottostante di una categoria". Ma dico io se ogni grafo genera una categoria libera allora la risposta è "Tutti". Che cosa mi sto perdendo ?? 
Grazie mille!
Grazie mille!
Risposte
Se un grafo [tex]G[/tex] genera [tex]C[/tex] come categoria libera non è detto che [tex]G[/tex] sia proprio il grafo sottostante di [tex]C[/tex]. Il grafo sottostante deve avere (almeno) la proprietà indotta dalla composizione: se ci sono frecce [tex]a \to b,\ b \to c[/tex] allora ci dev'essere almeno una freccia [tex]a \to c[/tex].
Grazie mille Martino, ho messo insieme due cose che non c'entravano nulla. 
Infatti per esempio la categoria libera su un grafo contenente un solo vertice e un solo arco ammette infiniti morfismi e quindi infiniti sono anche gli archi nel grafo sottostante, giusto?
Questi sono i grafi che devo esaminare.
Per evitare equivoci premetto che io per comodità le composizioni le scrivo da destra a sinistra $fg = g \circ f$.
Il grafo (1) non va bene perchè dovrebbe esserci almeno una freccia fra il primo e il terzo puntino, ma non c'è.
Nel grafo (2) non c'è possibilità di comporre fra loro morfismi se non con le identità, quindi per costruire una categoria basta per esempio prendere come oggetti tre insiemi diciamo ${0}, {1}$ e ${0,1}$ ed elencare quali applicazioni fra loro consideriamo morfismi: per esempio le uniche due applicazioni di ${0}$ in ${0,1}$ e l'unica applicazione di ${0}$ in ${1}$
Il grafo (3) potrebbe rappresentare un preordine in questo modo: nell'insieme ${{0},{1},{0,1}}$ definiamo la relazione $A <= B <=> |A| <= |B|$ che è riflessiva e transitiva.
Il grafo (4) non va bene perchè abbiamo tre frecce $f,g: a -> b$ e $h: b -> a$ con le seguenti relazioni $fh = id_a = gh$ e $hf = id_b = hg$ da cui si deduce $f=h^{-1}=g$ quindi dovrebbero esserci due frecce invece che tre.
Sul grafo (5) non so che pensare. Se una categoria esiste per questo grafo allora dette $f:a -> b$ e $g: b -> b$ e $h:b -> a$ le frecce non identiche e dette $id_a$ e $id_b$ le identità risulta
$fg = f$
$gh = h$
$fh = id_a$
e poi abbiamo due possibilità $hf = g$ oppure $hf = id_b$ ma quest'ultimo caso ci dice che $f = h^{-1}$ è un isomorfismo e quindi da $fg=f$ ricaveremmo $g=id_b$ contro le ipotesi. Quindi deve essere $hf = g$. Infine abbiamo che $g^{2} = hfhf = h*id_a*f=hf=g$ è idempotente. Ho fatto la tabella riassuntiva della composizione
Ma non riesco a trovare un esempio da portare.
Infatti per esempio la categoria libera su un grafo contenente un solo vertice e un solo arco ammette infiniti morfismi e quindi infiniti sono anche gli archi nel grafo sottostante, giusto? Questi sono i grafi che devo esaminare.
Per evitare equivoci premetto che io per comodità le composizioni le scrivo da destra a sinistra $fg = g \circ f$.
Il grafo (1) non va bene perchè dovrebbe esserci almeno una freccia fra il primo e il terzo puntino, ma non c'è.
Nel grafo (2) non c'è possibilità di comporre fra loro morfismi se non con le identità, quindi per costruire una categoria basta per esempio prendere come oggetti tre insiemi diciamo ${0}, {1}$ e ${0,1}$ ed elencare quali applicazioni fra loro consideriamo morfismi: per esempio le uniche due applicazioni di ${0}$ in ${0,1}$ e l'unica applicazione di ${0}$ in ${1}$
Il grafo (3) potrebbe rappresentare un preordine in questo modo: nell'insieme ${{0},{1},{0,1}}$ definiamo la relazione $A <= B <=> |A| <= |B|$ che è riflessiva e transitiva.
Il grafo (4) non va bene perchè abbiamo tre frecce $f,g: a -> b$ e $h: b -> a$ con le seguenti relazioni $fh = id_a = gh$ e $hf = id_b = hg$ da cui si deduce $f=h^{-1}=g$ quindi dovrebbero esserci due frecce invece che tre.
Sul grafo (5) non so che pensare. Se una categoria esiste per questo grafo allora dette $f:a -> b$ e $g: b -> b$ e $h:b -> a$ le frecce non identiche e dette $id_a$ e $id_b$ le identità risulta
$fg = f$
$gh = h$
$fh = id_a$
e poi abbiamo due possibilità $hf = g$ oppure $hf = id_b$ ma quest'ultimo caso ci dice che $f = h^{-1}$ è un isomorfismo e quindi da $fg=f$ ricaveremmo $g=id_b$ contro le ipotesi. Quindi deve essere $hf = g$. Infine abbiamo che $g^{2} = hfhf = h*id_a*f=hf=g$ è idempotente. Ho fatto la tabella riassuntiva della composizione
Ma non riesco a trovare un esempio da portare.
Potresti prendere
Ah però era semplice ](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
Grazie ancora!
Grazie ancora!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo