시스템 U

수학 논리학에서 시스템 U와 시스템 U는⁻ 순수 유형 시스템이다. 즉 임의의 수의 정렬, 공리 및 규칙(또는 정렬 간의 종속성)을 가진 특수 형태의 람다 미적분학이다.이 둘은 1972년 장 이브 지라드에 의해 일관성이 없다는 것이 증명되었다.^[1]이 결과는 마르틴 뢰프의 1971년형 원론이 지라드의 역설로 착취하는 것과 같은 '유형인' 행동을 허용함으로써 일관성이 없다는 것을 깨닫게 했다.

형식 정의

시스템 U는 다음을 포함하는 순수 유형 시스템으로 정의된다^{[2]: 352} .

• 3종류${{\ast ,\square ,\square$ $\backslash \};$
• 두 개의 공리 {${\displaystyle \ast }$ :${\displaystyle ◻}$ , ${\displaystyle ◻}$:${\displaystyle \mathrm{}\}}$ ${\displaystyle \{\ast :\square ,\square :\square \}$ ;$$및
• 5가지 규칙${\displaystyle }${ (${\displaystyle \ast }$ ,${\displaystyle }$∗${\displaystyle }$,${\displaystyle \ast }$ , , (${\displaystyle (}$ ,${\displaystyle ◻}$ ) , (${\displaystyle \mathrm{}},$${\displaystyle }$, ${\displaystyle △}$) , (${\displaystyle △)\}}$ ${\displaystyle \{(\ast ,\steam ,\ast$ ), $(\square ,\square$ ), $(\square ,\square )}}.$

시스템 U는⁻ ${\displaystyle \mathrm{(=}}$ ,${\displaystyle \ast }$) ${\displaystyle (\triangle ,\ast )}$ 규칙을$$ 제외하고 동일하게 정의된다.

${\displaystyle$ \$ast$}과$($와$$)${\displaystyle \square }$은(는) 일반적으로 "유형"과 "유형"으로 불리며$$$,{\displaystyle \mathrm{}}$ ${\displaystyle \triangle }$은(는) 특정 이름이 없다$$.두 공리는 종류별 격납(∗ :$$${\displaystyle ◻}$ : ◻ : ◻ :$$\$displaystyle \$$ast$ $:\square })$과 종류별 격납을${\displaystyle }$기술하고 있다${\displaystyle .<img\; alt="\backslash triangle\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d909fe94e8277a4c44a50853cb7dbbf0fa3148ed"\; style="vertical-align:\; -0.338ex;\; width:2.066ex;\; height:2.176ex;"\; papago-attr-id="45">}$직관적으로, 그 종류들은 용어의 성격에 있어서 계층구조를 묘사한다.

1. All values have a type, such as a base type (e.g. ${\displaystyle b:\mathrm {Bool} }$ is read as “b is a boolean”) or a (dependent) function type (e.g. ${\displaystyle f:\mathrm {Nat} \to \mathrm {Bool} }$ is read as “f is a function from natural numbers to booleans”).
2. ${\displaystyle \ast }$ ${\displaystyle \ast}$은(t$$:${\displaystyle :}$ ${\displaystyle$ t$:\ast }$은(는) "t is a type"으로 읽음) 모든 유형이다.From ${\displaystyle \ast }$ we can build more terms, such as ${\displaystyle \ast \to \ast }$ which is the kind of unary type-level operators (e.g. ${\displaystyle \mathrm {List} :\ast \to \ast }$ is read as “List is a function from types to types”, that is, a polymorphic type).규칙은 우리가 어떻게 새로운 종류를 형성할 수 있는지를 제한한다.
3. ${\displaystyle ◻}$ ${\displaystyle \square }$은(는) 모든 종류의 유형이다(${\displaystyle }$: ${\displaystyle ◻}$ ${\displaystyle$ k$:\square }$은(는) "k is a kind"로 읽음).마찬가지로 우리는 규칙이 허용하는 것에 따라 관련 용어를 만들 수 있다.
4. ${\displaystyle }$\$displaystyle \cHB }$은(는$)$ 그런 용어의 일종이다${\displaystyle \mathrm{.}}$

The rules govern the dependencies between the sorts: ${\displaystyle (\ast ,\ast )}$ says that values may depend on values (functions), ${\displaystyle (\square ,\ast )}$ allows values to depend on types (polymorphism), ${\displaystyle (\square ,\square )}$ allows types to depend on types (type operat오즈), 등등.

지라드의 역설

시스템 U와 U의⁻ 정의는 시스템 F와 같은 고전적인 폴리모픽 람다 칼쿨리 용어에 있는 폴리모픽 유형의 용어에 유추하여 일반 생성자에 폴리모픽 종류를 할당하는 것을 허용한다.이러한 일반 생성자의 예는 (k가 종류 변수를 나타내는 경우)일^{[2]: 353} 수 있다.

$){\displaystyle \lambda$$\알파(\alpha \beta )\;\\\Pi k:\square(((k\to$ k$)\to k$ .

${\displaystyle 이}$ 메커니즘은 모든 유형이 거주하고 있음을 암시하는 유형$({\displaystyle }$ ${\displaystyle \mathrm{\forall }}$ p${\displaystyle }$: ${\displaystyle \ast }$, ${\displaystyle p}$)${\displaystyle }$= ${\displaystyle \mathrm{\perp }}$ ${\displaystyle (\forall p:\ast ,p)=\bot$ $\})$으로 용어를 구성하기에 충분하다.Curry-Howard 통신에 의해, 이것은 모든 논리적 명제가 증명 가능한 것과 동등하며, 이것은 시스템을 일관성이 없게 만든다.

지라드의 역설은 세트 이론에서 러셀의 역설의 유형-이론적 아날로그다.

참조

추가 읽기

• Barendregt, Henk (1992). "Lambda calculi with types". In S. Abramsky; D. Gabbay; T. Maibaum (eds.). Handbook of Logic in Computer Science. Oxford Science Publications. pp. 117–309.
• Coquand, Thierry (1986). "An analysis of Girard's paradox". Logic in Computer Science. IEEE Computer Society Press. pp. 227–236.