[TYPES] what does a negative proposition represent in type theory?
Giuseppe Castagna
gc at pps.jussieu.fr
Sun May 23 11:19:38 EDT 2010
Le 21/05/2010 23:25, Noam Zeilberger a écrit :
> [ The Types Forum,http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
>
> Well yes you're right that there are other interpretations of negation
> -- I wasn't sure what you were looking for! With this clarification,
> I think the question you are asking is really at the "extrinsic" or
> "refinement type" level (related to intersection and union types,
> etc.).
>
> Before we can get there, we need to start at the intrinsic level.
>
> Let's say that a type A denotes some set of values.
> At this level, the standard interpretation of negation is as building
> the set of continuations, i.e., the type ~A denotes the set of
> continuations for A with answer type _|_.
>
Or, you can take the "semantic subtyping" setting where types are set of
values, and union, intersection, containement *and* negationtypes are
interpreted set-theoretically. So in particular not(A) is the set of all
values that do not have type A. However you end up in a more syntactic
world since for instance the implication A -> B is the set of
well-typed lambda abstractiond that when applied to an expression of
type A, if they return a value, then this is in B; but for cardinality
reasons it cannot denote the set of functions from A to B (For more
details see JACM vol. 55, n. 4, pag. 1-64, 2008.)
Beppe
More information about the Types-list
mailing list