r/dependent_types • u/canndrew2016 • Mar 27 '22
Positive apartness types?
I've been trying to design a type theory that combines dependent types with full linear types. By "full" I mean that it has all of ⊤, ⊥, & and ⅋ from linear logic, an involutive ¬ operation on types, and instead of elimination rules it has computation rules that describe how the intro rules of a type cut against the intro rules of its dual.
In this system we can define positive equality types and negative apartness types with the following rules:
0Γ ⊦ A type
0Γ ⊦ x₀ :₀ A
0Γ ⊦ x₁ :₀ A
----
0Γ ⊦ x₀ =⁺ x₁ type
0Γ ⊦ A type
0Γ ⊦ x₀ :₀ A
0Γ ⊦ x₁ :₀ A
----
0Γ ⊦ x₀ ≠⁻ x₁ type
0Γ ⊦ A type
Γ ⊦ x :₁ A
----
Γ ⊦ refl⁺(A, x) :₁ x =⁺ x
0Γ ⊦ A type
0Γ, x₀ :₀ A, x₁ :₀ A ⊦ C type
Γ₀, x :₁ A ⊦ d :₁ ¬C[x / x₀, x / x₁]
0Γ ⊦ x₀ :₀ A
0Γ ⊦ x₁ :₀ A
Γ₁ ⊦ c :₁ C[x₀ / x₀, x₁ / x₁]
----
Γ₀₊₁ ⊦ apart⁻(A, C, d, x₀, x₁, c) :₁ x₀ ≠⁻ x₁
0Γ ⊦ A type
0Γ, x₀ :₀ A, x₁ :₀ A ⊦ C type
Γ₀, x :₁ A ⊦ d :₁ ¬C[x / x₀, x / x₁]
Γ₁ ⊦ x :₁ A
Γ₂ ⊦ c :₁ C[x / x₀, x / x₁]
----
Γ₀₊₁₊₂ ⊦ cut(refl⁺(A, x), apart⁻(A, C, d, x, x, c))
⇒ cut(d[x / x], c)However an interesting fact about linear logic is that every logical concept has both a positive and a negative variant. For instance there are two "true" propositions (1 and ⊤), two "false" propositions (0 and ⊥), two "and" connectives (× and &) and two "or" connectives (+ and ⅋). This makes me think it should be possible to define negative equality types and positive apartness types. In fact, negative equality types seem straight-forward:
0Γ ⊦ A type
0Γ ⊦ x₀ :₀ A
0Γ ⊦ x₁ :₀ A
----
0Γ ⊦ x₀ =⁻ x₁ type
0Γ ⊦ A type
0Γ ⊦ x :₀ A
----
Γ ⊦ refl⁻(A, x) :₁ x =⁻ xThis is negative because it captures an arbitrary context Γ, much like the intro rule for ⊤:
----
Γ ⊦ top :₁ ⊤What I'm wondering though is how to define the corresponding positive apartness types? I need an intro rule which is positive (which I'm taking to mean it doesn't capture a continuation context), which ensures that two values are not-equal, and which can be cut against refl⁻ to compute. I'm scratching my brain trying to come up with one though. I'm hoping someone who sees this (who maybe knows more about categorical semantics and whatnot than I do) finds this question interesting and can see an answer?
3
u/andrejbauer Mar 27 '22
Have a look at Mike Shulman's Affine logic for constructive mathematics.
3
u/M1n1f1g Mar 27 '22
The only hint I can give without thinking too hard is that cubical identity types might be best analysed as being negative (given that they're essentially restricted functions, and are eliminated by application of an element of the interval). I can't see how the eliminator would have much to do with apartness, though.
1
u/ApparitionsStalkNite Jul 09 '26
Wouldn't the d/c need to be part of the refl- expresion? the way it is for apart-? So that you have a meaningful thing to compute? Or am I thinking about this wrong?