Reference. Generalised Name Abstraction for Nominal Sets

Richard Clouston ·

Cite

Cite as @clouston_generalised_2013 (helia, typst) · \cite{clouston_generalised_2013} (LaTeX)
BibTeX
bibtex · 8 lines
@inproceedings{clouston_generalised_2013,
  title={Generalised name abstraction for nominal sets},
  author={Clouston, Richard},
  booktitle={International Conference on Foundations of Software Science and Computational Structures},
  pages={424--438},
  year={2013},
  organization={Springer}
}
hayagriva YAML (typst)
yaml · 10 lines
clouston_generalised_2013:
  type: article
  title: Generalised name abstraction for nominal sets
  author: Clouston, Richard
  date: 2013
  page-range: 424-438
  parent:
    type: proceedings
    title: International Conference on Foundations of Software Science and Computational Structures
    organization: Springer
Cited by (1)

Definition. Nominal Sets as Day Quotients nominal-sets-quotient

In the Schanuel topos, the underlying category for Day convolution is 𝐶=𝕀op, where 𝕀 is the category of finite sets and injections.

Given a nominal set 𝑋, its presheaf action describes elements supported by 𝑡:

𝑋(𝑡)={𝑥∈𝑋|𝗌𝗎𝗉𝗉(𝑥)⊆𝑡}

Instead of taking 𝑋 a priori as a presheaf, we can view it as a finitely- supported 𝖯𝖾𝗋𝗆(𝔸)-set. We can restrict our attention to the groupoid core 𝐺=𝖼𝗈𝗋𝖾(𝕀), asking for the support to be exactly the input:

𝑋𝑠={𝑥∈𝑋|𝗌𝗎𝗉𝗉(𝑥)=𝑠}

This family 𝑋•:𝐺→𝐒𝐞𝐭 is functorial on finite sets and bijections.

By extending this functor along the inclusions described in Quotient Coincidence, we can extend 𝑋• to both a presheaf 𝗆𝗄𝖯𝗌𝗁(𝑋•) and a copresheaf 𝗆𝗄𝖢𝗈𝗉𝗌𝗁(𝑋•) on 𝐶. This suggests the equivalence:

𝗆𝗄𝖯𝗌𝗁(𝑋•)⊸𝑌≅𝐷𝗆𝗄𝖢𝗈𝗉𝗌𝗁(𝑋•)𝑌

I suspect this allows us to describe name abstraction [𝑋]𝑌 [1] —which ordinarily looks like an operation on two presheaves of the same variance—as the quotient of 𝑌 by the induced copresheaf 𝗆𝗄𝖢𝗈𝗉𝗌𝗁(𝑋•).

Concretely, [𝑋]𝑌 is usually given by the quotient of the product by an equivalence relation:

[𝑋]𝑌≅𝑋×𝑌∼

where (𝑥,𝑦)∼(𝜋𝑥,𝜋𝑦) for permutations 𝜋 fixing 𝗌𝗎𝗉𝗉(𝑦)−𝗌𝗎𝗉𝗉(𝑥).

On the other hand, the Day quotient computes to a coend:

(𝐷𝗆𝗄𝖢𝗈𝗉𝗌𝗁(𝑋•)𝑌)(𝑐)=∫𝑠𝑋𝑠×𝑌(𝑠⊎𝑐)

A priori, a coend over 𝑠 of the product 𝑋𝑠×𝑌(𝑠⊎𝑐) is expressed as the quotient of a set of triples by an equivalence relation ≈:

{(𝑠,𝑥,𝑦)|𝑠=𝗌𝗎𝗉𝗉(𝑥),𝗌𝗎𝗉𝗉(𝑦)⊆𝑠⊎𝑐}/≈

However, because the comprehension formula fixes 𝑠=𝗌𝗎𝗉𝗉(𝑥), we reduce to a quotient of pairs:

{(𝑥,𝑦)|𝗌𝗎𝗉𝗉(𝑦)⊆𝗌𝗎𝗉𝗉(𝑥)⊎𝑐}/≈

I suspect that this quotient will equate to the one given by [𝑋]𝑌, thus resolving the apparent issues with variance. I further suspect that one will need the sheaf condition (pullback-preservation) of nominal sets to establish this equivalence.

Cites 1 works (0 here)
External (1)
  • Generalised name abstraction for nominal sets (2013)
clouston_generalised_2013 reference entries/refs/clouston_generalised_2013/clouston_generalised_2013.hel