Type theory Tuple



in type theory, commonly used in programming languages, tuple has product type; fixes not length, underlying types of each component. formally:







(

x

1


,

x

2


,

,

x

n


)
:



t



1


×



t



2


×

×



t



n




{\displaystyle (x_{1},x_{2},\ldots ,x_{n}):{\mathsf {t}}_{1}\times {\mathsf {t}}_{2}\times \ldots \times {\mathsf {t}}_{n}}



and projections term constructors:








π

1


(
x
)
:



t



1


,
 

π

2


(
x
)
:



t



2


,
 

,
 

π

n


(
x
)
:



t



n




{\displaystyle \pi _{1}(x):{\mathsf {t}}_{1},~\pi _{2}(x):{\mathsf {t}}_{2},~\ldots ,~\pi _{n}(x):{\mathsf {t}}_{n}}



the tuple labeled elements used in relational model has record type. both of these types can defined simple extensions of typed lambda calculus.


the notion of tuple in type theory , in set theory related in following way: if consider natural model of type theory, , use scott brackets indicate semantic interpretation, model consists of sets




s

1


,

s

2


,

,

s

n




{\displaystyle s_{1},s_{2},\ldots ,s_{n}}

(note: use of italics here distinguishes sets types) such that:







[

[



t



1


]

]
=

s

1


,
 
[

[



t



2


]

]
=

s

2


,
 

,
 
[

[



t



n


]

]
=

s

n




{\displaystyle [\![{\mathsf {t}}_{1}]\!]=s_{1},~[\![{\mathsf {t}}_{2}]\!]=s_{2},~\ldots ,~[\![{\mathsf {t}}_{n}]\!]=s_{n}}



and interpretation of basic terms is:







[

[

x

1


]

]

[

[



t



1


]

]
,
 
[

[

x

2


]

]

[

[



t



2


]

]
,
 

,
 
[

[

x

n


]

]

[

[



t



n


]

]


{\displaystyle [\![x_{1}]\!]\in [\![{\mathsf {t}}_{1}]\!],~[\![x_{2}]\!]\in [\![{\mathsf {t}}_{2}]\!],~\ldots ,~[\![x_{n}]\!]\in [\![{\mathsf {t}}_{n}]\!]}

.

the n-tuple of type theory has natural interpretation n-tuple of set theory:







[

[
(

x

1


,

x

2


,

,

x

n


)
]

]
=
(

[

[

x

1


]

]
,
[

[

x

2


]

]
,

,
[

[

x

n


]

]

)


{\displaystyle [\![(x_{1},x_{2},\ldots ,x_{n})]\!]=(\,[\![x_{1}]\!],[\![x_{2}]\!],\ldots ,[\![x_{n}]\!]\,)}



the unit type has semantic interpretation 0-tuple.








Comments

Popular posts from this blog

Biography Pavel Yablochkov

Discography Three Man Army

History VMFA-121