맨위로가기

절대 논리식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

절대 논리식은 모형 이론과 집합론에서 사용되는 개념으로, 논리식이나 집합의 성질이 모델이나 구조에 따라 변하지 않고 동일한 진리값을 갖는 것을 의미한다. 모형 이론에서는 전칭 문장(전칭 양자화사만 있는 문장)이 하향 절대적이고, 존재 문장은 상향 절대적인 것이 예시이며, 두 구조가 공유 언어의 모든 문장의 진리값에 동의하면 기초 동치라고 정의된다. 집합론에서는 집합의 성질이 모델에 따라 절대적인지 여부가 중요하며, 공집합, 순서수, 유한 순서수 등은 절대적이지만, 유한하다는 것, 가산하다는 것 등은 절대적이지 않다. 또한, 숀필드 절대성 정리는 분석적 위계의 특정 문장이 체르멜로-프렝켈 집합론의 모델과 그 모델의 구성 가능 우주 사이에서 절대적임을 보여주며, 강제법을 이용한 독립성 증명에 한계를 제시한다. 일부 거대 기수는 구성 가능 우주에서 존재하지 않으므로, 그 정의가 하위 모델에 절대적이지 않다.

더 읽어볼만한 페이지

  • 모형 이론 - 괴델의 불완전성 정리
    괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
  • 모형 이론 - 괴델의 완전성 정리
    괴델의 완전성 정리는 1차 논리 이론에서 모형 이론적 진리와 증명 이론적 진리가 같음을 나타내며, 연역 체계가 완전함을 보장하고 일차 논리에서 통사론적 결과와 의미론적 결과가 동일하다는 것을 의미한다.
  • 논리학 개념 - 추론
    추론은 하나 이상의 명제를 전제로 결론을 도출하는 사고 과정으로, 논리학에서는 전제와 결론 간의 관계를 통해 정확성을 판단하며, 연역 추론, 귀납 추론, 가추법 등으로 나뉘고 인공지능 등 다양한 분야에서 활용된다.
  • 논리학 개념 - 마음
    마음은 의식, 사고, 지각, 감정, 동기, 행동, 기억, 학습 등을 포괄하는 심리적 현상과 능력의 총체이며, 다양한 분야에서 연구되고 인간 삶의 중추적인 역할을 한다.
절대 논리식
개요
분야수리 논리학
설명어떤 대상이 특정 공식에 대해 절대적인지 여부
정의
배경집합론의 형식 언어 L에 대한 공식 φ(x)가 주어졌을 때, 여기서 x는 자유 변수임.
M과 N을 L의 전달적 집합이라고 가정.
M이 N의 전달적 부분 집합이고, x가 M에 있는 모든 값에 대해 다음 조건을 만족하는 경우 φ(x)는 M에 절대적이라고 함: M이 φ(x)를 만족하면 N도 φ(x)를 만족함.
절대성 종류Σ1 절대성: Σ1 공식에 대해 M에서 N으로의 절대성
Δ1 절대성: Δ1 공식에 대해 M에서 N으로의 절대성
성질
기본 연산에 대한 절대성M이 표준적이고 전달적인 집합 (예: H(κ) 또는 Lκ, 여기서 κ는 무한 기수)인 경우, 기본적인 집합 연산 (예: 순서쌍, 합집합, 멱집합)은 M에 절대적임.
Σ1 공식의 절대성M이 N의 Σ1-기본 부분 구조이고 φ(x)가 Σ1 공식이면 φ(x)는 M에 절대적임.
Δ0 공식의 절대성φ가 제한된 수량자(∀y ∈ z 또는 ∃y ∈ z 형태의 수량자)만 포함하는 공식인 경우, φ는 모든 전달적 집합에 대해 절대적임. 이러한 공식은 Δ0 또는 Σ0로 알려져 있음.
Σ1 공식의 예시'x가 함수이다'는 Σ1 공식임.
'x가 순서쌍이다'는 Σ1 공식임.
Δ0 공식의 예시'x ⊆ y'는 Δ0 공식임.
'x = {y, z}'는 Δ0 공식임.
절대성이 없는 예시'x는 추이적이다'는 Δ0가 아님. 추이성은 ∀y ∈ x ∀z ∈ y (z ∈ x)로 정의되며, 이는 제한되지 않은 수량자(∀z ∈ y)를 포함함.
함의φ(x)가 Δ1이고 M과 N이 φ(x)에 대해 절대적이면 M ⊨ φ(x) iff N ⊨ φ(x)임.

2. 모델 이론에서의 절대성

모형 이론에서 절대성은 특정 논리식의 진리값이 모델에 따라 변하지 않는 성질을 의미한다. 하향 절대성의 예로, 어떤 구조에서 참인 전칭 문장(전칭 양화사만 있는 문장)은 원래 구조의 모든 부분 구조에서도 참이다. 반대로, 존재 문장은 어떤 구조에서 그것을 포함하는 모든 구조로 상향 절대적이다.

두 구조가 공유 언어의 모든 문장의 진리 값에 동의하는 경우, 즉 언어의 모든 문장이 두 구조 사이에서 절대적인 경우 기초 동치라고 정의된다. 어떤 이론에서 ''M''과 ''N''이 그 이론의 모형이고 ''M''이 ''N''의 부분 구조일 때, ''M''이 ''N''의 기초 부분 구조이면 그 이론은 모형 완전이라고 정의된다.

2. 1. 절대 문장

1차 논리 언어 \mathcal L의 구조들의 모임 \mathcal M이 주어졌다고 가정한다. (예를 들어, \mathcal M은 어떤 \mathcal L의 문장들의 집합 \mathcal T\subseteq\operatorname{Sent}(\mathcal L)이 성립하는 \mathcal L-구조들의 모임일 수 있다.)

1차 논리 언어 \mathcal L의 문장 \phi\in\operatorname{Sent}(\mathcal L)이 다음 조건을 만족시킨다면, \mathcal M 속에서 '''절대 문장'''(absolute sentence영어)이라고 한다.

  • 임의의 두 \mathcal L-구조 M,M'\in\mathcal M에 대하여, M\models\phi\iff M'\models\phi이다. 즉, \mathcal M에 속하는 모든 구조에서 동시에 참이거나 동시에 거짓이다.

2. 2. 상향·하향 절대 논리식

1차 논리 언어 \mathcal L의 구조 M이 주어졌다고 하자.

\mathcal L-논리식 \phi(x_1,\dots,x_n)\in\operatorname{wff}(\mathcal L)가 n개의 자유 변수 x_1,\dots,x_n를 갖는다고 하자. 만약 다음 조건이 성립한다면, \phi가 '''M-하향 절대 논리식'''(downward-absolute formula영어)이라고 한다.

:M의 임의의 \mathcal L-부분 구조 M'\subseteq M 및 임의의 m_1,m_2,\dots,m_n\in M'에 대하여, M\models\phi[m_1,\dots,m_n]\implies M'\models\phi[m_1,\dots,m_n]이다.

마찬가지로, 만약 다음 조건이 성립한다면, \phi가 '''M-상향 절대 논리식'''(upward-absolute formula영어)이라고 한다.

:M을 부분 구조로 포함하는 임의의 \mathcal L-구조 (M',\in) 및 임의의 m_1,m_2,\dots,m_n\in M에 대하여, M\models\phi[m_1,\dots,m_n]\Longleftarrow M'\models\phi[m_1,\dots,m_n]이다.

모형 이론에서 하향 절대성의 기본적인 예는 구조 내에서 참인 전칭 문장(전칭 양화사만 있는 문장)은 원래 구조의 모든 부분 구조에서도 참이라는 것이다. 반대로, 존재 문장은 구조에서 이를 포함하는 모든 구조로 상향 절대적이다.

3. 집합론에서의 절대성

현대 집합론의 주요 부분은 ZF와 ZFC의 다양한 모델 연구를 포함한다. 이러한 모델 연구에서 집합의 어떤 성질이 서로 다른 모델에 대해 절대적인지 아는 것은 매우 중요하다. 일반적인 방법으로는 집합론의 모델을 고정하고, 그것과 같은 순서수를 갖는 추이적 모델로 제한하여 검토한다.

몇몇 성질은 집합론의 모든 추이적 모델에 대해 절대적이다.


  • ''x''는 공집합이다.
  • ''x''는 순서수이다.
  • ''x''는 유한 순서수이다.
  • ''x''는 후속 순서수이다.
  • ''x''는 극한 순서수이다.
  • ''x'' = ω.
  • ''x''는 함수 (의 그래프)이다.


절대적이지 않은 성질은 다음과 같다.

3. 1. 추이적 절대 논리식

ZFC의 표준 추이적 모형 M과 집합 m_1,\dots,m_k\in M에 대하여, (M\models\phi[m_1,\dots,m_k])\iff \phi[m_1,\dots,m_k]를 만족하는 \mathcal L_\in-논리식 \phi(x_1,\dots,x_n)\in\operatorname{wff}(\mathcal L_\in)를 '''추이적 절대 논리식'''이라고 한다.[3]

현대 집합론에서는 ZF와 ZFC의 다양한 모델을 연구하며, 이때 집합의 어떤 속성이 다른 모델에 대해서도 절대적인지 파악하는 것이 중요하다. 일반적으로 집합론의 고정된 모델에서 시작하여 동일한 서수를 포함하는 다른 추이적 집합 모델만 고려한다.

모든 추이적 모델에 대해 절대적인 속성과 그렇지 않은 속성은 다음과 같다.

절대적인 속성절대적이지 않은 속성


3. 2. 절대적인 성질의 예


  • ''x''는 공집합이다.
  • ''x''는 순서수이다.
  • ''x''는 유한 순서수이다.
  • ''x''는 후속 순서수이다.
  • ''x''는 극한 순서수이다.
  • ''x'' = ω.
  • ''x''는 함수 (의 그래프)이다.[1]

3. 3. 절대적이지 않은 성질의 예


스콜렘의 역설은 실수 집합이 비가산이라는 점(이는 ZFC 또는 ZFC의 작은 유한 부분 체계 ZFC'에서 증명 가능)과 ZFC'의 가산 추이 모형이 있다는 점(이는 ZFC에서 증명 가능) 사이의 겉보기 모순이다. 이러한 모형에서 실수 집합은 가산 집합이 된다. 이 역설은 가산성이 ZFC의 특정 모형의 부분 모형에 대해 절대적이지 않다는 점을 통해 해결할 수 있다. 집합 ''X''가 집합론의 한 모형에서는 가산 집합이지만, ''X''를 포함하는 부분 모형에서는 가산이 아닐 수 있는데, 이는 부분 모형이 ''X''와 ω 사이의 전단사 함수를 포함하지 않을 수 있기 때문이다. 뢰벤하임-스콜렘 정리는 ZFC에 적용될 때 이러한 상황이 실제로 발생한다는 것을 보여준다.

3. 4. 숀필드 절대성 정리

'''숀필드 절대성 정리'''(Shoenfield absoluteness theorem영어)는 분석적 위계의 \Pi^1_2 및 \Sigma^1_2 문장이 체르멜로-프렝켈 집합론(ZF)의 모델과 그 구성 가능 우주 사이에서 절대적임을 보여주는 정리이다.[1][2]

이 정리는 ZFC의 독립성 증명, 특히 강제법의 한계를 설명하는 데 중요한 역할을 한다. 예를 들어, 리만 가설 및 P = NP 문제와 같은 많은 유명한 미해결 문제들은 \Pi^1_2 문장(또는 더 낮은 복잡도의 문장)으로 표현될 수 있으며, 따라서 강제법으로 ZFC와 독립적임을 증명할 수 없다.

숀필드 절대성 정리의 한 결과는 선택 공리와 관련이 있다. 괴델은 ''V''가 ZF를 만족하는 것으로 가정될 때에도 구성 가능 우주 ''L''은 항상 선택 공리를 포함하여 ZFC를 만족한다는 것을 증명했다. 숀필드 정리는 주어진 \Sigma^1_3 문장 ''φ''가 거짓인 ZF의 모델이 있다면, ''φ''는 해당 모델의 구성 가능 우주에서도 거짓임을 보여준다. 이는 ZFC가 \Sigma^1_3 문장을 증명하면 해당 문장이 ZF에서도 증명될 수 있음을 의미한다.

3. 5. 거대 기수

집합론의 임의의 모형의 구성 가능 우주(''L'')에는 존재할 수 없는 특정 거대 기수가 있다. 그럼에도 불구하고, 구성 가능 우주는 원래 집합론 모형이 포함하는 모든 서수를 포함한다. 이 "역설"은 일부 거대 기수의 정의 속성이 하위 모형에 절대적이지 않다는 점에 주목하여 해결할 수 있다.

그러한 비절대적 거대 기수 공리의 한 예는 가측 기수에 대한 것이다. 서수가 가측 기수가 되려면 특정 속성을 만족하는 다른 집합(측도)이 존재해야 하는데, 그러한 측도는 구성 불가능하다는 것을 보일 수 있다.

참조

[1] 서적 Classical Recursion Theory 1989
[2] 서적 Classical Recursion Theory 1989
[3] 서적 Set theory: an introduction to independence proofs http://store.elsevie[...] North-Holland 1980


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com