Tag. nominal-set

Notes (3)

Definition. Nominal Sets nominal-set

Fix a countably infinite set of names 𝔸. A nominal set [1] is a set 𝑋 equipped with an action by the group of finite permutations 𝖯𝖾𝗋𝗆(𝔸), such that every element π‘₯βˆˆπ‘‹ has a finite support.

A finite set of names π‘†βŠ†π”Έ supports π‘₯ if any permutation fixing 𝑆 pointwise also fixes π‘₯.

The category of nominal sets is equivalent to the Schanuel topos. Under this equivalence, a nominal set 𝑋 corresponds to a functor π•€β†’π’πžπ­, where 𝕀 is the category of finite sets and injections, given by mapping a finite set of names 𝑑 to the set of elements supported by 𝑑:

𝑋(𝑑)={π‘₯βˆˆπ‘‹|𝑑supportsπ‘₯}

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.

Definition. The Schanuel Topos schanuel-topos

Let 𝕀 be the category of finite sets and injections. The Schanuel topos is the category of pullback-preserving functors 𝕀opβ†’π’πžπ­.

Equivalently, it is the category of nominal sets, which are sets equipped with an action by the group of permutations on a countable set of names 𝔸, such that every element has finite support.

References (3)

A Nominal Approach to Probabilistic Separation Logic li-2024-a

DOI Β· arXiv

Generalised Name Abstraction for Nominal Sets clouston_generalised_2013

Nominal Sets: Names and Symmetry in Computer Science pitts_nominal_sets

tag-nominal-set tag