For questions about type theory, including normalization, dependent types, identity types, inductive types, universe types, functional programming languages, proofs as programs in simply-typed lambda-calculi, Martin-Löf's intuitionistic type theory or related.Consider using one of the following ...

learn more… | top users | synonyms

15
votes
2answers
452 views

Looking for an approach to mathematical notation wherein the universe is divided into disjoint worlds.

Is there a rigorous approach to mathematical notation wherein the "universe" is divided into disjoint "worlds," and the meaning of notation is world-dependent? This would solve a few pesky problems. ...
4
votes
1answer
162 views

Curry-Howard Correspondence (Proof Theory)

As you all know, the Curry-Howard correspondance provides a link between type theory and predicate logic. Concepts featured in the former, such as $\Pi$-type and $\Sigma$-type can, by the ...
2
votes
1answer
84 views

How to extract the sets “produced” by a axiomatic set theory, into some newly introduced collection?

Say I know well how to reason in a set theory, which for the sake of this question I'll call $\bf{ST}$, say one of those, it can by $\bf ZFC$. It's principally written down via first order logic and ...
1
vote
1answer
86 views

Mistake in http://plato.stanford.edu/entries/type-theory/#2

There seems to be mistake in http://plato.stanford.edu/entries/type-theory/#2: First-order logic considers only types of the form $i,…,i → i$ (type of function symbols), and $i,…,i → o$ ...
0
votes
1answer
77 views

Is there a sense in which a formal theory can be more or less “metamathematically aware”?

For example, in classical logic, because of the law of the excluded middle, all propositions must be true or false, so in order to prove that a proposition is actually independent of the theory, we ...
0
votes
1answer
98 views

Define inl : $σ → σ ∨ τ$

I'm a bit stuck in Geuvers' "Introduction to Type Theory" (http://www.cs.ru.nl/~herman/onderwijs/provingwithCA/paper-lncs.pdf), p. 39: Exercise 13. Prove the derivability of some of the other logical ...
11
votes
0answers
210 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
7
votes
0answers
87 views

Turning ZFC into a free typed algebra

The standard way of using ZFC to encode the rest of mathematics is sometimes criticized because it introduces unnecessary, strange properties such as, for example $1\in 2$ if we encode integers by ...
5
votes
0answers
178 views

What is the likely future of Univalent Foundations?

Univalent foundations has been hyped up as the foundation for mathematics for the future in articles such as this one. Now I've given HoTT a brief look, and at least seen that it appears on the face ...
5
votes
0answers
80 views

Elementary proof of compact space = exhaustible space?

(This is a repost of a question I asked last year on cs.stackexchange.) The work of Martín Escardó has demonstrated close parallels between classical topology on one hand and computability on the ...
5
votes
0answers
69 views

Path structure of an odd-looking higher inductive type.

Consider the (putative) higher inductive type $\mathtt{PNest}$, with the constructors: $\mathtt{base} : \mathtt{PNest}$ $\mathtt{nest} : \mathtt{base} = \mathtt{base} \to \mathtt{base} = ...
4
votes
0answers
61 views

Proof by reflection and Homotopy Type Theory

I have been looking into various proof assistants, and came across the method of proof by reflection in Coq, which (from what I understand) allows one to verify a program provides the correct "answer" ...
4
votes
0answers
126 views

Logic in closed symmetric monoidal categories; reference request.

Suppose we want an algebraic theory $T$ to be interpretable in any closed symmetric monoidal category $\mathbf{C}.$ I am thinking in particular of the case where $\mathbf{C}$ is the category of models ...
3
votes
0answers
24 views

What to call a term-in-context whose context contains exactly the variables occurring in the term?

In type theory, a term-in-context $\Gamma \vdash t : \tau $ is only well-formed when $\Gamma$ contains all the variables occurring in $t:\tau$. Is there a name for when it contains exactly the ...
3
votes
0answers
25 views

Extensionality of a hierarchy of functionals over $\mathbb{N}$

Let $H$ be the complete hierarchy of functionals over $\mathbb{N}$. To be precise: let the set $T$ of 'simple types' be the smallest set such that '0' $\in T$ and $(α→β) \in T$ whenever $α, β \in T$. ...
3
votes
0answers
47 views

Contrapositive in Type Theory

We define $\neg P=P\rightarrow 0$ in Martin-Lof type theory. So, we have a function $$ (P\to Q)\to [(Q\to 0)\to (P \to 0)] $$ given by function composition. Am I right that there is not reverse ...
3
votes
0answers
89 views

What is the desirable function identification when setting up arrows in the category of types?

My question is which functions can not be allowed in a statically typed programming language, so that the "canonical" category is less coarse than what you get if you define it's arrows to be ...
3
votes
0answers
100 views

Are large cardinals bi-interperable with type theory?

"Sets in Types, Types in Sets" establishes that the calculus of constructions is bi-interpretable with ZFC + infinitely many inaccessibles. Are there any more results like this higher up the large ...
2
votes
0answers
22 views

Consistency of Martin-Löf Type Theory and Categorical Models

Having read the parts of the hott book that introduce intuitionistic type theory (+univalence), I want to continue by studying some meta theory. I'm particularly interested in strategies for proving ...
2
votes
0answers
38 views

What strongly normalizing lambda calculi exist that can be integrated with/as logic?

If I'm trying to implement a logical system for deduction based on propositional reasoning, I can start with predicates and quantifiers and functions to obtain first order logic. I can further extend ...
2
votes
0answers
52 views

When is the higher-order theory of a model categorical?

I'm interested in (classical) type theories $L$ with the following property. For $M$ any model of $L$ (in Set), let $T(M)$ be the type theory of $M$, i.e., the strongest extension of $L$ satisfied by ...
2
votes
0answers
162 views

Continuations vs. Yoneda

There is this observation (worldpress blog) that the continuation monad (Wikipedia) stems from the Yoneda embedding. For fixed data types $R$, the monad maps data types $T$ to types $(T\to R)\to R$. ...
2
votes
0answers
51 views

What if typing judgements were propositions?

Suppose we created a modified type theory in which typing judgments like $x : X$ are not judgments at all; rather, they're propositions. Would this be a bad idea? If so, why? A good answer should ...
2
votes
0answers
70 views

Set Theory - Well Order (Lexiographical combination)

Question: Prove constructively that if $(A_{1},\prec_{1})$ and $(A_{2},\prec_{2})$ are two well-ordered sets then their lexicographical combination $(A_{1} \times A_{2},<_{1,2})$ is also well ...
2
votes
0answers
89 views

What are the main differences between set theory versus pure type systems?

According to wikipedia, a pure type system: ...is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these... Pure type systems may ...
2
votes
0answers
126 views

Introductory text about different stratification methods in higher-order logic and set theory

Could someone recommend me a good overview text about stratification of predicates, comprehension axioms, and other methods of avoiding the paradoxes in untyped or only loosely/relatively typed ...
1
vote
0answers
60 views

What is the relationship between Realizability and the Curry-Howard isomorphism?

I have recently been studying the Curry-Howard isomorphism/correspondence. My sources have primarly been Sørensen [1] and Girard [2]. Realizability is introduced here in the form of Kleene's ...
1
vote
0answers
49 views

Resources for learning functional programming/Haskell for the mathematically inclined.

I am a math student wanting to learn some functional programming with Haskell. From what I understand, many type theory concepts are analogous, even equivalent, to category theory concepts (e.g. ...
1
vote
0answers
62 views

Ordinal Numbers within Simple Type Theory

A little preamble: I recently came across the system of higher-order logic known as simple type theory, and I was immediately intrigued by it, as it seemed to be exactly what I was looking for as an ...
1
vote
0answers
61 views

Is this a good way to define “n-paths” in a type?

$\DeclareMathOperator{\succ}{succ}$ Define these two type families by "indexed induction induction." $$\text{_-boundary} : \mathbb{N} \to \mathcal{U} \to \mathcal{U}$$ $$\text{_-path} : \prod_{n : ...
1
vote
0answers
29 views

Proving the Identity Type Has a Term

I am trying to get used to type theory. I have a two things to ask. Let $1$ be the unit type with unique term $\star : 1$. As an exercise I was trying to prove that $$ ...
1
vote
0answers
63 views

Proof of $(\forall x. \varepsilon(x)) \Rightarrow \bot $ in $\lambda\pi $ calculus $\equiv$

What is the right representation of the proof of $(\forall x. \varepsilon(x)) \Rightarrow \bot $ in simple type theory as a term of $\lambda\pi $ calculus $\equiv$? Note on notation: The epsilon ...
1
vote
0answers
42 views

Reductions under lambda in dependently typed lambda calculus

I am currently reading a Simon Thompson's Type Theory book. In chapter 5 he introduces a system TT(0,C), which limits a notion of reduction . In this notion of reduction, reductions under lambda are ...
1
vote
0answers
52 views

Enumeration of symbols in grammatical expressions or vertices in tree graphs

I have expressions (type of a function) like e.g. $$f:(A\to B)\to C \to (D\to E)\to F.$$ (Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.) There might be information ...
0
votes
0answers
21 views

reflexive-transitive closure of --->, how to understand that?

given term t and t', decide whether t --->* t' -/->, where --->* is the reflexive-transitive closure of --->. Above two lines are from a paper about programming language meta-theory. I did not ...
0
votes
0answers
50 views

Turnstile (\vdash) in adjoint functor and type theory.

Is common symbol $\vdash$ an abuse of notation or there is a deep sacred connection between $$\Gamma \vdash \lambda(a:A).a:\Pi(a:A).A$$ which is preorder and $$G \vdash F \quad \mbox{($F$ is left ...
0
votes
0answers
24 views

Syntax in Robert Harper's book

I'm trying to read Practical Foundations For Programming Languages by Robert Harper, especially I'm interested in existential types. So I started with this introduction: In the beginning I was ...
0
votes
0answers
56 views

Category Theory compared with Meta-Grammars (or Hyper-Grammars) in Programming Languages

This may be a simple minded question. First, background: Coming from a linguistic and computer science background, I keep on getting Category Theory shoved, ah, shown to me, when studying both ...
0
votes
0answers
32 views

Structural induction over types that accept functions, in Coq

If you define an inductive type in Coq with a constructor that accepts a function mapping to that type, you get a somewhat odd induction rule. ...
0
votes
0answers
33 views

Proper terminology for a pair of magmas

Given two magmas, call them $f$ and $g$ over the same set $a$, what do I call a tuple $h$ of them? With extra properties we call them such names as fields and rings. I am just looking for the generic ...
0
votes
0answers
38 views

Using types instead for basic proofs

Disclaimer: I know close to nothing about formal type theory, but I program intensively so prefer to think in terms of types. In typical math you write $a \in A$ to speak of the nature of your ...