라요 수

분류

큰 수

1. 개요

2. 정의

3. 해설

1 . 개요[편집]

Rayo's number Googology Wiki 페이지

[math(\text{Rayo}(10^{100}))]
2007년 MIT의 Big number duel에서 아구스틴 라요(Agustín Rayo)가 정의한 큰 수이다. #

2 . 정의[편집]

[math([\phi])]와 [math([\psi])]를 괴델 부호화(Gödel-coded)된 수식이라 하고, [math(s)], [math(t)]에 변수를 할당하자. 이때 [math(\text{Sat}([\phi],s))]는 다음과 같이 정의된다.

∀R {
{ ∀[ψ], s: R([ψ],t) ↔ ([ψ] = "x_i ∈ x_j" ∧ t(x_i) ∈ t(x_j))
ㅤㅤㅤㅤㅤㅤㅤㅤ∨ ([ψ] = "x_i = x_j" ∧ t(x_i) = t(x_j))
ㅤㅤㅤㅤㅤㅤㅤㅤ∨ ([ψ] = "(¬θ)" ∧ ¬R([θ], t))
ㅤㅤㅤㅤㅤㅤㅤㅤ∨ ([ψ] = "(θ∧ξ)" ∧ R([θ], t) ∧ R([ξ], t))
ㅤㅤㅤㅤㅤㅤㅤㅤ∨ ([ψ] = "∃x_i(θ)" ∧ ∃t′: R([θ], t′))
ㅤㅤㅤㅤㅤㅤㅤㅤ(where t′ is a copy of t with x_i changed)
ㅤ} ⇒ R([ϕ],s)
}

다음과 같은 조건을 만족하는 유일한 자유 변수로 [math(x_1)]과 [math(n)]개 미만의 기호를 갖는 수식 [math(\phi(x_1))]이 있는 경우 자연수 [math(m)]은 "라요-명명 가능(Rayo-namable)"하다고 한다.

\1. [math(\text{Sat}([\phi(x_1)\ \!\!],s))]와 같이 [math(x_1:=m)]을 할당하는 할당 변수 [math(s)]가 있다.
2. 모든 할당 변수 [math(t)]에 대해, 만약 [math(\text{Sat}([\phi(x_1)\ \!\!],t))]라면, [math(t)]는 반드시 [math(x_1=m)]이여야 한다.

여기서 [math(\text{Rayo}(n))]을 라요-명명 가능한 수 보다 큰 가장 작은 정수로 정의한다.

3 . 해설[편집]

쉽게 말해서, Rayo(n)은 최대 n개의 ∈, =, ￢, ∧, ∃[1]기호들과 이 기호들이 사용되는 대상 x_i만을 이용해서 만들 수 있는, 즉 1차 집합론(First Order Set Theory, FOST)에서 최대 n개의 기호를 이용해 정의 가능한 모든 유한한 양의 정수보다 큰 가장 작은 양의 정수'로 정의되었다고 할 수 있다. 쓸 수 있는 문자는 6가지 밖에 없지만, 이것들로 수학에서 가능한 모든 것을 할 수 있다.

정의에서 알 수 있듯, 우리가 쓸 수 있는 FOST에는 숫자가 정의되어 있지 않다. 따라서 자연수의 폰 노이만식 정의를 이용해서 자연수를 정의해야 하는데, 예를 들어 0을 정의하려면 폰 노이만의 정의를 따라 공집합을 정의하면 된다. 따라서 [math((\neg\ \exists\ x_2(x_2 \in x_1))=\emptyset=0)]으로 0을 정의하면, 10개의 기호로 정의할 수 있는 가장 큰 정수 0보다 큰 가장 작은 정수는 1이고, 그래서 Rayo(10)이 1이 되는 것이다.[2] 뿐만 아니라, 0을 정의하기 위해서는 최소 10개의 기호가 필요하기에, Rayo(0)~Rayo(9)의 값은 모두 0이다. 또, 1을 정의하려면 공집합을 원소로 가지는 집합을 정의하면 되는데, 이는 [math( (\exists\ \ x_2(x_2 \in x_1) \land (\neg\ \exists x_2((x_2 \in x_1 \land \exists\ x_3(x_3 \in x_2))))))](30개의 기호)이므로 Rayo(30)의 하한은 2다. Rayo(10)~Rayo(29)는 모두 1이 된다. 이런 식으로 공집합, 공집합의 집합, 공집합과 공집합의 집합의 집합....과 같은 식으로 자연수를 정의하면 Rayo(10¹⁰⁰)의 하한을 구할 수는 있겠지만, 이런 방식으로 FOST를 쓰는 것은 아주아주 약한 하한을 찾을 수 있을 뿐이다. 예를 들어, 같은 방식으로 Rayo(861)의 하한은 무려 4가 나오며, Rayo(926)의 하한은 16이 나오게 된다. 현재는 최적화되어 Rayo(88)의 하한이 4이다.

만약 FOST를 그저 자연수를 폰 노이만식으로 정의하는 데에 낭비하지 않고 다른 방식으로 사용한다면 더욱 큰 하한값을 얻을 수 있다. 예를 들어 먼저 약간의 트릭을 이용해 4개의 원소를 갖는 집합[3]을 정의 한 후, 그 집합의 멱집합의 멱집합인 집합을 정의하면,[4]그 집합의 원소의 개수는 65536개가 된다. 그리고 이 집합의 원소의 개수인 기수를 정의하면,[5] Rayo(590)의 하한은 65536+1=65537이라는 점을 알 수 있고, 집합의 멱집합을 구하는 과정을 계속 반복한다면, Rayo(294+74n)>2↑↑n이라는 관계식도 얻을 수 있다. #[6]

그리고 문자의 수가 수천이 된다면, FOST로 바쁜 비버 함수와 같은 튜링 머신을 정의할 수 있게 되는데, 이때부터 Rayo(n) 함수는 극도로 빠르게 증가하기 시작한다. 이론적으로 Rayo(n) 함수는 Rayo(n)의 함수의 정의에서 가정한 FOST로 구현 가능한 모든 함수보다 점근적으로 빠르게 증가하고, 이는 바쁜 비버 함수 [math(\text{BB}(n))]는 물론 현재 정의된 가장 강력한 튜링 머신 함수인 무한 시간 튜링 머신 [math(\Sigma_\infty(n))]을 압도할 수 있다는 말이 된다. 또한 Googology 유저인 Emk가 Rayo(7901)이 이미 현재 수학 체계로는 측정이 불가능한 상태인 [math({\rm FF}(2^{65536})]) 보다 더 크다고 증명하였는데[7], 7901이 10⁴ 즉 1만보다도 작은 수라는 것을 감안하면 Rayo(10¹⁰⁰)이 얼마나 큰 수일지 아주 약간은 감이 올 것이다.

여담으로 라요 수의 정의 자체가 꽤나 복잡하고 이해하기 어렵기 때문에 라요수보다 큰 수를 만들려는 시도에서 잘못 정의된 수들이 나오고 라요 수의 크기를 오해하는 사람들도 googology사이트에서 굉장히 많았다. 계산할 수 없는 수중 하나인 Xi function을 만들어낸 Adam Goucher도 Xi function이 라요 함수보다 크다고 잘못 주장한 적이 있었다.

[1] 수리논리학을 배운 사람이라면 ∀가 왜 없는지 의문을 품을 수도 있는데, 이는 [math(∀x(e))]를 [math((¬(∃x((¬e)))))]로 나타낼 수 있기 때문이다.[2] Googology wiki 유저 Emk가 Rayo(10)의 하한이었던 1이 정확한 값임을 증명했다. #[3] [math(A:=∃b∃c∃d∃e(b∈y∧c∈b∧d∈c∧e∈d∧c∈y∧d∈y∧e∈y∧¬∃f((¬f=b)∧(¬f=c)∧(¬f=d)∧(¬f=e)∧f∈y))][4] [math(𝒫(x):=(¬∃t((t⊆x∧t∉y)))∧(¬∃t(((∃z(z∈t∧z∉x))∧t∈y)))\\𝒫(𝒫(A))=2^{2^A}\\B:=𝒫(𝒫(A)))][5] [math(|B|=65536)], FOST에서 기수를 정의하는 과정은 매우 복잡하므로 여기에는 싣지 않겠다.[6] 현재는 더욱 최적화되어, Rayo(260+20n)>2↑↑n임이 밝혀졌다. 따라서 Rayo(320)>16이고, Rayo(340)>65536이며, Rayo(360)>2⁶⁵⁵³⁶이 된다.[7] 현재는 Rayo(7339)로 더욱 최적화 되었다.

이 문서의 내용 중 전체 또는 일부는 2023-11-25 00:53:19에 나무위키 라요 수 문서에서 가져왔습니다.

라요 수

분류

1. 개요[편집]

2. 정의[편집]

3. 해설[편집]

관련 문서

1 . 개요[편집]

2 . 정의[편집]

3 . 해설[편집]