Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Under which name is the following proposition filed actually:

Every poset $P$ embeds fully and faithfully in the powerset of $P$, ordered by subset inclusion.

Let me call it Dedekind's lemma. Next to Cayley's theorem:

Every group $G$ is isomorphic to a subgroup of the symmetric group acting on $G$.

it is a prominent special case of Yoneda's lemma.

All proofs are constructive, and so is the proof of Erdős' lemma on intersection graphs:

Every graph $G$ is isomorphic to a family of subsets $S_i$ of a set S such that $v_i$ and $v_j$ are joined by an edge iff $S_i \cap S_j \neq \emptyset$

What I wonder about is:

Is Erdős' lemma on intersection graphs a special case of Yoneda's lemma?

share|improve this question
11  
Well, posets and groups are both special cases of categories, but graphs aren't, so I'm not sure what category you'd be applying Yoneda to. –  Qiaochu Yuan Feb 7 '12 at 18:23
4  
Note that if Erdös Lemma isn't a special case of Yoneda's Lemma (which I suspect it isn't, for reasons that Qiaochu mentions), this will be very hard to prove - it will require some Gödel-like effort on a meta-level. –  Dominic van der Zypen Sep 2 '14 at 10:22
    
Note you could think of a graph as a category $G$ together with a functor $L : G \to \mathbb{N}$. The objects of $G$ are the vertices, the morphisms from $v$ to $w$ are the walks from $v$ to $w$, composition of morphisms is concatenation of walks. The functor $L$ tells you the length of a walk (which lets you recover the edges as the walks of length $1$). –  Mike F Jun 28 at 23:15
    
This is not really Erdös' Lemma. The lemma was proven by Szpilrajn-Marczewski (see matwbn.icm.edu.pl/ksiazki/fm/fm33/fm33131.pdf). Erdös, Goodman and Posa have given a bound for $\# S$. –  Martin Brandenburg Jun 28 at 23:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.