Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorMike Shulman
   • CommentTimeOct 30th 2018
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexStarting to state the lemmas here. <a href="https://ncatlab.org/nlab/revision/Initiality+Project+-+Substitution/1">v1</a>, <a href="https://ncatlab.org/nlab/show/Initiality+Project+-+Substitution">current</a>

   Starting to state the lemmas here.

   v1, current

2. • CommentRowNumber2.
   • CommentAuthorMike Shulman
   • CommentTimeOct 30th 2018
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexFinished statements, maybe? Not sure about the best way to deal with renaming of variables. <a href="https://ncatlab.org/nlab/revision/Initiality+Project+-+Substitution/1">v1</a>, <a href="https://ncatlab.org/nlab/show/Initiality+Project+-+Substitution">current</a>

   Finished statements, maybe? Not sure about the best way to deal with renaming of variables.

   v1, current

3. • CommentRowNumber3.
   • CommentAuthorMike Shulman
   • CommentTimeNov 2nd 2018
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexI am confused about how to deal with $\alpha$-equivalence in the interpretation. The "exchange" part of the first lemma on this page implies that the partial interpretation of a raw term or type is "equivariant" under renaming of its *free* variables. But how do we deal with the necessary *invariance* under renaming of *bound* variables ($\alpha$-equivalence)? (Streicher elides this point completely, as far as I can tell.) On the one hand, since the interpretation of a binder like $\lambda(x:A.B).M$ is defined in terms of the interpretation of subterms like $M$ in which the bound variable is free, it seems like invariance under renaming of bound variables depends on equivariance under renaming of free variables. But on the other hand, capture-avoiding substitution is only a total function when we are allowed to rename the *bound* variables of its inputs, so it seems like the opposite dependence also holds. Do we need to prove them in mutual induction? I suppose we could give up and use de Bruijn indices for the input to the interpretation, with translation from named variable syntax into de Bruijn syntax as a "preprocessing" step to go along with the adding of type annotations, Russell universe coercions and cumulativity, etc. But I want to resist that as long as possible....

   I am confused about how to deal with $\alpha$-equivalence in the interpretation.

   The “exchange” part of the first lemma on this page implies that the partial interpretation of a raw term or type is “equivariant” under renaming of its free variables. But how do we deal with the necessary invariance under renaming of bound variables ($\alpha$-equivalence)? (Streicher elides this point completely, as far as I can tell.)

   On the one hand, since the interpretation of a binder like $\lambda(x:A.B).M$ is defined in terms of the interpretation of subterms like $M$ in which the bound variable is free, it seems like invariance under renaming of bound variables depends on equivariance under renaming of free variables. But on the other hand, capture-avoiding substitution is only a total function when we are allowed to rename the bound variables of its inputs, so it seems like the opposite dependence also holds. Do we need to prove them in mutual induction?

   I suppose we could give up and use de Bruijn indices for the input to the interpretation, with translation from named variable syntax into de Bruijn syntax as a “preprocessing” step to go along with the adding of type annotations, Russell universe coercions and cumulativity, etc. But I want to resist that as long as possible….

4. • CommentRowNumber4.
   • CommentAuthordlicata335
   • CommentTimeNov 3rd 2018
   • (edited Nov 3rd 2018)
   • PermaLink
   Author: dlicata335
   Format: MarkdownItexOne way to build alpha-equivalence classes of terms is to define name *swapping* $T[x \leftrightarrow y]$, where T is a completely raw term (not considered up to alpha yet, so just a regular datatype with "strings" for variables in it), and where swapping applies the swap to all positions, including bound variables. Then everything is equivariant under swapping, before you define capture-avoiding substitution. Then it's a lemma after the fact that $T[ x \leftrightarrow y ]$ is (alpha-equivalent to) $T [ x / y ]$ when x doesn't occur in T.

   One way to build alpha-equivalence classes of terms is to define name swapping $T[x \leftrightarrow y]$, where T is a completely raw term (not considered up to alpha yet, so just a regular datatype with “strings” for variables in it), and where swapping applies the swap to all positions, including bound variables. Then everything is equivariant under swapping, before you define capture-avoiding substitution. Then it’s a lemma after the fact that $T[ x \leftrightarrow y ]$ is (alpha-equivalent to) $T [ x / y ]$ when x doesn’t occur in T.

5. • CommentRowNumber5.
   • CommentAuthoratmacen
   • CommentTimeNov 4th 2018
   • PermaLink
   Author: atmacen
   Format: TextI don't understand the problem from #3. Is it solved?

   I don't understand the problem from #3. Is it solved?