순서 표기법
Ordinal notation수학적 논리와 집합 이론에서 서수 표기법은 모든 유한한 기호 순서의 집합, 그 자체가 유한한 알파벳의 구성원을 계수 가능한 서수 집합에 매핑하는 부분 함수다. 괴델 번호 매기는 어떤 형식 언어의 잘 형성된 공식 집합(서수 표기 함수가 정의된 유한한 기호 순서)을 자연 숫자에 매핑하는 함수다. 이것은 잘 형성된 각각의 공식과 그것의 괴델 수라고 불리는 독특한 자연수를 연관시킨다. 괴델 번호 매기기(Gödel numbering)가 고정된 경우, 서수의 부분 집합 관계는 잘 형성된 공식에 대한 주문을 유도하며, 이는 자연수의 부분 집합에 대한 잘 정렬을 유도한다. 재귀 서수 표기법은 다음 두 가지 추가 특성을 충족해야 한다.
- 자연수의 부분 집합은 재귀 집합이다.
- 자연수의 부분 집합에 대해 유도된 잘 조절된 것은 재귀적 관계다.
There are many such schemes of ordinal notations, including schemes by Wilhelm Ackermann, Heinz Bachmann, Wilfried Buchholz, Georg Cantor, Solomon Feferman, Gerhard Jäger, Isles, Pfeiffer, Wolfram Pohlers, Kurt Schütte, Gaisi Takeuti (called ordinal diagrams), Oswald Veblen. Stephen Cole Kleene은 Kleene's O라고 불리는 표기 체계를 가지고 있는데, 이것은 순서형 표기법을 포함하고 있지만, 여기에서 설명한 다른 체계들만큼 잘 행동하지는 않는다.
일반적으로 서수에서 서수까지 여러 함수를 정의하고 기호로 각 해당 함수를 나타냄으로써 진행된다. 베블렌의 잘 알려진 시스템과 같은 많은 시스템에서 그 기능들은 정상적인 기능이며, 즉 적어도 하나의 주장에서는 엄격히 증가하고 지속적이며, 다른 주장에서는 증가하고 있다. 그러한 기능에 대한 또 다른 바람직한 특성은 함수의 값이 그 각 주장보다 크기 때문에 서수가 항상 작은 서수의 관점에서 설명되고 있다는 것이다. 그런 바람직한 성질은 몇 가지 있다. 불행하게도, 어느 시스템도 그들이 서로 모순되기 때문에 그것들을 모두 가질 수 없다.
페어링 기능을 사용한 간단한 예
늘 그렇듯이 우리는 0을 나타내는 상수 기호인 "0"으로 시작해야 하는데, 이것은 우리가 아리티 0의 함수라고 생각할 수도 있다. 0을 기술할 수 있는 관점에서 더 작은 서수가 없기 때문에 이것은 필요하다. 가장 분명한 다음 단계는 단항함수인 "S"를 정의하는 것인데, 이 함수는 그것보다 큰 최소 서수로 서수를 가져가는 것이다. 즉, S는 후속함수다. 0과 결합하여, 후계자는 자연수의 이름을 지을 수 있게 한다.
세 번째 함수는 위의 두 함수와 이 함수의 이전 값으로 아직 설명할 수 없는 가장 작은 서수에 각 서수를 매핑하는 함수로 정의될 수 있다. 이것은 β가 해당 함수의 고정 지점과 Ω·(β+1)를 사용하는 한정된 숫자를 더한 경우를 제외하고 β를 Ω·β에 매핑한다.
네 번째 함수는 α가 Ωω·(α+1)를 사용하는 유한한 숫자에 더하여 고정된 점인 경우를 제외하고 α를 Ωω·α에 매핑한다.
ξ-notation
하나는 이런 식으로 계속될 수 있지만, 그것은 우리에게 무한한 기능을 줄 것이다. 대신 단항 함수를 이항 함수로 병합하도록 합시다. α에 대한 트랜스피나이트 재귀에 의해 β에 트랜스피나이트 재귀에 의해 α < α, β) = α < β와 β < and과 and은 더 작은 α에 대한 α의 값이 아니거나 β가 더 작은 동일한 α에 대한 for의 값을 정의 할 수 있다.
따라서 다음과 같이 ξ-notation을 정의한다.
- "0"은 0을 나타내는 ξ-notation이다.
- "A"와 "B"가 "ξAB"에서 α와 β에 대한 ξ-notation으로 대체되면, 그 결과는 ,(α,β)에 대한 not-notation이 된다.
- 다른 언급은 없다.
함수 ξ은 모든 서수 쌍에 대해 정의되며 일대일이다. 항상 인수보다 큰 값을 제공하며 범위는 0과 엡실론 수( (=Ωε)를 제외한 모든 서수이다.
α(α, β) < α(α) > < Δ)> 또는 (α < α = α, β < Δ) 또는 (α > α, β) Δ가 있는 경우에만 있다.
이 정의에서 처음 몇 가지 ξ-notation은 다음과 같다.
- 0의 경우 "0". 1을 위한 "0000" ξ(0,1)=2의 경우 "000000"이다. ξ(1,0)=Ω의 경우 "ξξ000"이다. 3인용 "00000 for00" Ω+1의 경우 "ξ0ξξ000". Ω·2의 경우 "ξξ00ξ00". Ω의ω 경우 "ξξ0ξ000".의 "ξξξ0000". {\omega ^{\
일반적으로 ξ(0,β) = β+1이다. 특별한 상황에 따라 k = 0 또는 1 또는 2의 k(1+α,β) = Ωωα·(β+k) = Ω·(β+k)인 경우:
k = α가 엡실론 수이고 β가 유한한 경우 2이다.
그렇지 않으면 k = 1 β가 Ωωα+1 + 유한수의 배수인 경우.
그렇지 않으면 k = 0.
ξ-notation은 ε보다0 작은 서수의 이름을 두 개의 기호("0"과 "ξ")만으로 지정할 수 있다. 만약 이러한 공식이 엡실론 숫자를 열거하는 함수를 추가하여 확장된다면, 그들은 추가된 함수에 의해 명명될 수 없는 첫 번째 엡실론 숫자보다 적은 서수 이름을 지정할 수 있을 것이다. 서수의 초기 세그먼트 내에 기호를 추가하는 이 마지막 속성을 해당 세그먼트 내에 이름을 부여하며, (솔로몬 페페르만 뒤에) refrecentity라고 부른다.
리스트
다양한 저자에 의해 소개된 서수 표기법에는 많은 다른 시스템들이 있다. 종종 다른 시스템들 사이에서 전환하기가 꽤 어렵다.
칸토어
0과 Ω의 "Exponential polyomials"는 엡실론 0보다 작은 서수형 표기법을 제공한다. 이것들을 쓰는 데는 많은 동등한 방법들이 있다; 기하급수적인 다항식 대신, 뿌리깊은 나무나 내포된 괄호, 또는 위에서 설명한 시스템을 사용할 수 있다.
베블렌
2-변수 베블렌 함수(Veblen 1908)는 Feferman-Schutte 서수보다 적은 서수들에 대해 서수 표기법을 부여하는 데 사용될 수 있다. 한정된 수의 변수에 포함된 Veblen 함수는 작고 큰 Veblen 서수보다 적은 서수식 표기 시스템을 제공한다.
아커만
아커만(1951)은 앞에서 베블렌이 설명한 체계보다 다소 약한 서수 표기법을 기술했다. 그의 체계의 한계는 때때로 아커만 서수형이라고 불린다.
바흐만
바흐만(1950) 은 셀 수 없는 서수를 사용하여 새로운 카운트 가능한 서수를 만드는 핵심 아이디어를 소개했다. 그의 원래 시스템은 각 서수로 수렴되는 특별한 순서를 선택해야 했기 때문에 사용하기 다소 번거로웠다. 후에 페퍼만 등이 도입한 표기법 체계는 이러한 복잡성을 피했다.
타케우티(순서도)
타케우티(1987)는 "순서도"라고 불리는 매우 강력한 서수 표기법을 설명했는데, 이것은 이해하기 어렵지만 후에 페페르만에 의해 단순화되었다.
페퍼만의 θ 함수
페퍼만은 부홀츠(1986)에서 설명한 세타 함수를 다음과 같이 소개했다. 서수 α의 경우, α는α 서수에 대한 함수 매핑 서수다. 흔히 θα(β)는 θαβ로 표기된다. 세트 C(α, β)는 α에 대한 유도에 의해 정의되며, 0, Ω, Ω12, ..., Ωω, Ω과 함께 β 미만의 서수 및 α에 대한 함수 θξ. 그리고 θγ 함수는 Δ∉C(γ,Δ)로 서수 Δ를 열거하는 함수로 정의된다. 이 시스템의 문제는 서수 표기법과 붕괴 함수가 동일하지 않고, 따라서 이 함수는 서수 표기법으로 적합하지 않다는 것이다. 관련 서수 표기법은 알려져 있지 않다.
부홀츠
부홀츠(1986)는 다음과 같은 서수 표기법을 페퍼만의 세타 함수의 단순화라고 기술했다. 정의:
- Ωξ = Ωξ 이상일 경우 Ω, Ω0 = 1
α 서수, v 서수, 최대 Ω에 대한 함수 αv(α)는 다음과 같이 α에 대한 유도로 정의된다.
- ψv(α)는 Cv(α)가 아닌 가장 작은 서수이다.
여기서 Cv(α)는 다음과 같은 최소 집합이다.
- Cv(α)는 Ω보다v 작은 모든 서수를 포함한다.
- Cv(α)가 순서형 추가에 따라 닫힘
- Cv(α)는 α 미만 인수에 적용되는 함수 ψu (u≤Ω의 경우)에 따라 닫힌다.
This system has about the same strength as Fefermans system, as for v ≤ ω. 그러나, 이 시스템은 강력하지만, 서수 표기법으로는 적합하지 않다. Buchholz는 연관 서수 표기법을 만들었지만, 그것은 복잡하다: 정의는 주요 기사에 있다.
의 O
클레네(1938년)는 모든 재귀 서수(Church-Kleene 서수보다 작은 것)에 대한 표기법을 설명했다. 불행히도 위에서 설명한 다른 시스템과 달리, 일반적으로 일부 자연수가 서수를 나타내는 것인지 또는 두 숫자가 동일한 서수를 나타내는지를 구분하는 효과적인 방법은 없다. 그러나 클린의 에서 주어진 두 개의 공지에 대한 서수합, 제품, 검정력을 나타내는 표기법(서수 산술 참조)을 효과적으로 찾을 수 있으며, 서수의 표기법에는 각 작은 서수 및 서수마다 하나의 원소를 포함하는 반복적으로 열거된 표기법 집합이 있다. 효과적으로 명령된다. Kleene의 {\ {은(는) 표준 표기(및 매우 계산 불가능한) 집합을 의미한다. 기호의 유한 문자열 대신 자연수의 부분집합을 사용하며, 재귀적이지 않기 때문에 다시 한 번 서수 표기법으로 적격하지 않는다.
타라놉스키의 C
드미트로 Taranovsky 자비 출판한 웹 페이지에 나와 있는 C잘 짜여진 세트(S,<>){\displaystyle(S,<.)}추가 구조 D가 장착된에서 S⊂ S× 적절한 조건 explaine을 만족시키{\displaystyle D\subset S\times S}{C\displaystyle}이진 함수를 건설하기 위해 다음과 같은 일반적인 뼈대를 묘사했다.d 늦게r. Let denote the least element of . For an , we put , 존재한다고 가정) 및():{ : < =\{Sc\in:c<, a\}}.(S,<>){\displaystyle(S,<.)}에서 에스′S⊂{\displaystyle S'\subset S}, 우리는 나는에 의해 나는(S′)치고를 의미한다 ⊂ S{\displaystyle lim(S)\subset S}은 부분 집합의 한계의 요소들의 S′{\displaystyle S}기 위해서. 우리는(S,<>){\dis에 D{D\displaystyle} 학사라고 말한다.playstyle(S다음 사항이 유지되는 경우):
이가) (,<) 에 대한 학위라면 ) ) : : < 이후 D{D\displaystyle}은 특별하지 않다 ={\textrm{분}}\{c\in C_{}:b<, c\}}. 특히, 이 구조는 한계 서수 η{\displaystyle \eta}학위(η, ∈){\displaystyle(\eta ,\in)}에 D⊂ η ×η{\displaystyle D\subset \eta \times \eta}이 장착된., 결과function C{ 일한다.\di은(는) 의 선택에 크게 좌우된다타라노프스키는 몇 가지 명백한 학위 예를 소개했다.
다양한 서수 표기 및 접기 함수의 한계 목록
표기법 | 표현 가능한 카운트 가능 서수의 우수성 |
---|---|
칸토르 정상형 | 엡실론노우트 |
바이너리 베블렌 함수 | 페페르만슈튀테 서수날 |
파인니터리 베블렌 함수 | 작은 베블렌 서수 |
버드 함수 | 작은 베블렌 서수 ( )^{\ |
확장 베블렌 함수 | 대형 베블렌 서수 |
바흐만의 함수 | 바흐만-하워드 서수날 |
마도르의 함수 | 바흐만-하워드 Ω ){\ |
Weiermann의 함수 | 바흐만-하워드 서수 ( + ) |
Feferman의 함수 | 타케우티-페퍼만-부크홀츠 서수 Ω+ ( ){\ _}:1}}( |
Buchholz의 함수 | 타케우티-페퍼만-부크홀츠 서수 + ) |
Rathjen의 함수 | |
Rathjen의 함수 | > ( + ) |
Stegert의 첫 번째 } 함수 | > ( P ) + 1 {\varipsilon varpsilon |
Stegert의 두 번째 함수 | > 대형 스테거트 서수 (+; P ) + 1 |
의 C 함수 | 존재는 알 수 없지만, 재귀적이고 매우 크다. |
의 O 함수 | 교회-클레인 서수 |
의 O+ 함수 | 쓰기 가능한 서수의 우월성 |
Klev의 ++ 함수 | 궁극적으로 쓰기 가능한 서수의 {\ |
참고 항목
참조
- Ackermann, Wilhelm (1951), "Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse", Math. Z., 53 (5): 403–413, doi:10.1007/BF01175640, MR 0039669
- Buchholz, W. (1986), "A new system of proof-theoretic ordinal functions", Ann. Pure Appl. Logic, 32 (3): 195–207, doi:10.1016/0168-0072(86)90052-7, MR 0865989
- 프레드릭 가스의 "건설적 서수 표기법"
- Kleene, S. C. (1938), "On Notation for Ordinal Numbers", The Journal of Symbolic Logic, 3 (4): 150–155, doi:10.2307/2267778, JSTOR 2267778
- Steffen Lempp의 "재귀 이론에서의 고산술 지수 세트"
- Hilbert Levitz, Transfinite Ordinals 및 공지: 기록되지 않은 기사인 경우, 1999(8페이지, PostScript)
- Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", The Journal of Symbolic Logic, 41 (2): 439–459, doi:10.2307/2272243, JSTOR 2272243
- Pohlers, Wolfram (1989), Proof theory, Lecture Notes in Mathematics, vol. 1407, Berlin: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN 978-3-540-51842-6, MR 1026933
- Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3
- Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 978-3-540-07911-8, MR 0505313
- Takeuti, Gaisi (1987), Proof theory, Studies in Logic and the Foundations of Mathematics, vol. 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 978-0-444-87943-1, MR 0882549
- Veblen, Oswald (1908), "Continuous Increasing Functions of Finite and Transfinite Ordinals", Transactions of the American Mathematical Society, 9 (3): 280–292, doi:10.2307/1988605, JSTOR 1988605