기본 동치

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

1. 개요
2. 정의
3. 성질
4. 예시
5. 타르스키-보트 판정법 (Tarski-Vaught Test)
참조

1. 개요

기본 동치는 같은 언어의 두 구조가 모든 1차 논리 문장에 대해 동일한 진리값을 가질 때 성립하는 관계이다. 기본 동치는 기본 매장, 기본 부분 구조와 밀접하게 연관되어 있으며, 모형 이론에서 중요한 개념으로 사용된다. 예를 들어, 실수와 유리수는 순서 관계를 가지는 구조로서 기본 동치이며, 워시 정리에 따라 어떤 모형과 그 초거듭제곱은 기본 동치이다.

2. 정의

모형 이론에서 사용되는 몇 가지 기본적인 개념은 다음과 같다.

'''기본 동치'''(elementary equivalence^영어): 같은 언어의 두 구조 $M$ , $N$ 이 모든 1차 논리 문장(자유 변수가 없는 공식) $\phi$ 에 대해 $M\models\phi$ 와 $N\models\phi$ 가 동치일 때, 두 구조는 서로 기본 동치라고 한다. 즉, 두 구조는 정확히 같은 1차 논리 문장들을 만족시킨다.

'''기본 매장'''(基本埋藏, elementary embedding^영어): 같은 언어의 구조 $M$ 에서 $N$ 으로 가는 함수 $j\colon M\to N$ 가, $k$ 개의 자유 변수 $\vec x$ 를 갖는 임의의 1차 논리 공식 $\phi$ 와 $M$ 의 임의의 원소 $\vec m \in M^k$ 에 대해 $M\models\phi[\vec m/\vec x]$ 와 $N\models\phi[j(\vec m)/\vec x]$ 가 동치일 때, 이 함수 $j$ 를 기본 매장이라고 한다. 이는 1차 논리 공식의 참, 거짓 여부를 보존하는 함수이다.

'''기본 부분 구조'''(基本部分構造, elementary substructure^영어): 구조 $N$ 이 구조 $M$ 의 부분 집합이고( $N \subset M$ ), $N$ 이 $M$ 의 부분 구조이며, 포함 함수(즉, $N$ 의 모든 원소를 자기 자신으로 대응시키는 함수)가 기본 매장을 이룰 때, $N$ 을 $M$ 의 기본 부분 구조라고 한다. 다르게 표현하면, $N$ 과 $M$ 이 같은 서명 ''σ''를 가지고, ''N''의 원소 ''a''₁, …, ''a''_''n''를 사용하는 모든 1차 ''σ''-논리식 ''φ''(''x''₁, …, ''x''_''n'')에 대해, ''φ''(''a''₁, …, ''a''_''n'')가 ''N''에서 성립하는 것과 ''M''에서 성립하는 것이 동치일 때 $N$ 은 $M$ 의 기본 부분 구조이다.^[1]^[2]

2. 1. 기본 동치

같은 언어의 구조

M

,

N

에 대하여, 다음 조건들은 서로 동치이며, 이 조건이 성립할 때

M

과

N

이 서로 '''기본 동치'''(elementary equivalence^영어) 또는 '''초등 동치'''라고 한다.

모든 1차 논리 문장(자유 변수가 없는 공식) $\phi$ 에 대하여, $M\models\phi\iff N\models\phi$
모든 1차 논리 문장 $\phi$ 에 대하여, $M\models\phi\implies N\models\phi$
모든 1차 논리 문장 $\phi$ 에 대하여, $N\models\phi\implies M\models\phi$

즉, 두 구조

M

과

N

이 동일한 시그니처

\sigma

를 가지며,

\sigma

에 대한 모든 1차 논리 문장이

M

에서 참이면

N

에서도 참이고, 그 반대도 성립하는 경우를 의미한다. 이는

M

과

N

이 동일한 완비된 1차 논리 이론을 가진다는 것과 같다.

M

과

N

이 기본 동치(초등 동치)일 때, 이를

M \equiv N

으로 표기한다.

1차 이론이 완비되었다는 것은 그 이론의 어떤 두 모델이라도 서로 기본 동치(초등 동치)라는 것과 동치이다.

예를 들어, 하나의 이항 관계 기호 '<'만 갖는 언어를 생각해 보자. 통상적인 순서를 갖는 실수의 집합 '''R'''과 유리수의 집합 '''Q'''는 기본 동치이다. 이는 두 구조 모두에서 '<'가 무한하고 조밀한 선형 순서로 해석되기 때문이다. Łoś–Vaught 검정에 따르면, 무한하고 조밀한 선형 순서의 이론은 완비 이론이므로, '''R'''과 '''Q'''는 기본 동치이다.

더 일반적으로, 무한 모델을 가지는 모든 1차 논리 이론은 뢰벤하임-스콜렘 정리에 의해 서로 동형이 아니면서도 기본 동치인 모델들을 가진다. 예를 들어, 페아노 산술에는 표준적인 자연수 0, 1, 2, ... 외에 다른 객체들을 포함하는 비표준 모델이 존재하며, 이 비표준 모델은 표준 모델과 기본 동치이다.

=== 기본 매장과 기본 부분 구조 ===

같은 언어에 대한 구조

M

과

N

사이의 '''기본 매장'''(elementary embedding^영어)은 다음 성질을 만족시키는 함수

j\colon M\to N

이다.

$k$ 개의 자유 변수 $\vec x$ 를 갖는 임의의 1차 논리 공식 $\phi$ 및 임의의 $\vec m\in M^k$ 에 대하여, $M\models\phi[\vec m/\vec x]$ 일 때와 $N\models\phi[j(\vec m)/\vec x]$ 일 때가 동치이다.

만약

M

이

N

의 부분 구조이고(

M\subset N

), 포함 함수(즉, 모든

m \in M

에 대해

j(m)=m

인 함수)가 기본 매장이면,

M

을

N

의 '''기본 부분 구조'''(elementary substructure^영어)라고 한다. 만약

M

이

N

의 기본 부분 구조이거나,

M

과

N

사이에 기본 매장이 존재하면,

M

과

N

은 기본 동치이다.

2. 2. 기본 매장

같은 언어에 대한 구조

M

과

N

사이의 '''기본 매장'''(基本埋藏, elementary embedding^영어)은 다음 성질을 만족시키는 함수

j\colon M\to N

이다.

$k$ 개의 자유 변수 $\vec x$ 를 갖는 임의의 1차 논리 공식 $\phi$ 및 임의의 $\vec m\in M^k$ 에 대하여, 만약 $M\models\phi[\vec m/\vec x]$ 라면 $N\models\phi[j(\vec m)/\vec x]$ 이다.

즉, 구조

M

의 원소들을 사용하여 참이 되는 모든 1차 논리 공식은, 그 원소들을 함수

j

를 통해 구조

N

으로 옮겼을 때에도 여전히 참이 되어야 한다.

만약

M

이

N

의 부분 집합이고(

M\subset N

), 부분 집합 포함 함수(즉,

M

의 모든 원소

m

에 대해

j(m)=m

인 함수)가 기본 매장을 이룬다면,

M

을

N

의 '''기본 부분 구조'''(基本部分構造, elementary substructure^영어)라고 한다.

모든 기본 매장은 강한 준동형사상이며, 그 이미지(함수값들의 집합)는

N

의 기본 부분 구조가 된다.

기본 매장은 모형 이론에서 매우 중요한 개념이다. 특히 집합론에서는 정의역이 전체 집합론의 우주 ''V''인 기본 매장이 거대 기수 이론에서 핵심적인 역할을 한다(임계점 참조).

2. 3. 기본 부분 구조

같은 언어에 대한 구조

M

과

N

이 주어졌을 때, 만약

N

이

M

의 부분 집합이고

N

이

M

의 부분 구조라면,

N

이

M

의 '''기본 부분 구조'''(elementary substructure^영어) 또는 '''기본 부분 모형'''이라고 하는 것은 다음 조건을 만족할 때이다.

N

과

M

은 동일한 서명 ''σ''를 가지며, 자유 변수 ''x''₁, …, ''x''_''n''을 갖는 모든 1차 논리 ''σ''-논리식 ''φ''(''x''₁, …, ''x''_''n'')와 ''N''의 모든 원소 ''a''₁, …, ''a''_''n''에 대해, ''φ''(''a''₁, …, ''a''_''n'')가 ''N''에서 성립하는 것과 ''M''에서 성립하는 것이 동치이다. 이를 기호로 나타내면 다음과 같다.

N \models \varphi(a_1, \dots, a_n) \text{ iff } M \models \varphi(a_1, \dots, a_n).

이 정의는 타르스키(Alfred Tarski)와 바우트(Robert Lawson Vaught)가 1957년에 처음 제시하였다.^[1] 이 정의는

N

이

M

의 부분 구조임을 함의한다.

만약

N

이

M

의 기본 부분 구조라면, 이를

N \preceq M

로 표기하며, 이때

M

을

N

의 '''기본 확장'''(elementary extension^영어)이라고 하고

M \succeq N

로 표기한다.

N

이

M

의 부분 구조일 때,

N

과

M

모두 서명 ''σ''에

N

의 모든 원소에 대한 새로운 상수 기호를 추가한 확장된 서명 ''σ''_''N''에 대한 구조로 해석될 수 있다. 이때,

N

이

M

의 기본 부분 구조가 되기 위한 필요충분 조건은

N

이

M

의 부분 구조이면서, 동시에

N

과

M

이 ''σ''_''N''-구조로서 기본 동치인 것이다.

'''타르스키-바우트 검정'''(Tarski–Vaught test^영어) 또는 '''타르스키-바우트 기준'''(Tarski–Vaught criterion^영어)은 구조

M

의 부분 구조

N

이 기본 부분 구조인지 판별하는 필요충분 조건이다. 이 검정은 다음과 같다:

M

을 서명 ''σ''의 구조,

N

을

M

의 부분 구조라고 하자. 그러면

N

이

M

의 기본 부분 구조일 필요충분 조건은, 모든 ''σ'' 위의 1차 논리식 ''φ''(''x'', ''y''₁, …, ''y''_''n'')과

N

의 임의의 원소 ''b''₁, …, ''b''_''n''에 대해, 만약

M \models \exists x \, \phi(x, b_1, \dots, b_n)

이라면, 반드시

N

의 어떤 원소 ''a''가 존재하여

M \models \phi(a, b_1, \dots, b_n)

이 성립하는 것이다. 이 검정은 큰 구조의 기본 부분 구조를 구성하는 데 유용하게 사용될 수 있다.

뢰벤하임-스코렘 정리는 기본 부분 구조 및 기본 확장의 존재성을 보장한다. 하향 뢰벤하임-스코렘 정리에 따르면, 가산 서명을 가진 무한 1차 구조는 항상 가산 기본 부분 구조를 가진다. 반대로, 상향 뢰벤하임-스코렘 정리에 따르면, 모든 무한 1차 구조는 임의로 큰 기수를 가지는 기본 확장을 가진다.

3. 성질

구조 간의 기본 동치는 동치 관계이다.

기본 매장은 단사 함수이며 강준동형사상의 성질을 만족한다. 또한, 기본 매장은 그 자체로 기본 동치 관계를 유도하며, 매장의 상(image)은 원래 구조의 기본 부분 구조가 된다.

같은 언어에 대한 두 구조 $M$ , $N$ 에 대하여, $N$ 이 $M$ 의 부분 구조일 때, $N$ 이 $M$ 의 기본 부분 구조인지 판별하는 필요충분조건은 '''타르스키-보트 조건'''(Tarski–Vaught criterion^영어)으로 알려져 있다.^[1]^[2] 이 조건은 $M$ 에서 어떤 성질을 만족하는 원소가 존재하고 그 성질이 $N$ 의 원소들을 사용하여 정의될 수 있다면, 그 성질을 만족하는 원소가 이미 $N$ 안에 존재해야 함을 의미한다.

3. 1. 기본 동치의 성질

구조 간의 기본 동치는 동치 관계의 성질을 만족한다. 두 구조 M과 N이 기본 동치일 때, 이를 M ≡ N으로 표기한다.

일차 이론이 완비되었다는 것은, 그 이론이 갖는 임의의 두 모델이 서로 기본 동치라는 것과 같은 의미이다.

뢰벤하임-스콜렘 정리에 따르면, 무한 모델을 가지는 모든 일차 이론은 서로 동형이 아니면서도 기본 동치인 모델들을 가진다. 예를 들어, 페아노 산술에는 우리가 아는 일반적인 자연수(0, 1, 2, ...) 외에 다른 대상들을 포함하는 비표준 모델이 존재하는데, 이 모델은 표준 모델(일반적인 자연수 집합)과 기본 동치이다.

또 다른 예로, '<'라는 순서 관계 기호만 가진 언어를 생각해 보자. 일반적인 순서가 주어진 실수의 집합 '''R'''과 유리수의 집합 '''Q'''는 모두 '<'를 경계 없는 조밀 선형 순서로 해석하기 때문에 기본 동치이다. 이는 경계 없는 조밀 선형 순서의 이론이 완비되었다는 사실(Łoś–Vaught 검정으로 증명 가능)로부터 알 수 있다.

3. 2. 기본 매장의 성질

같은 시그니처 ''σ''를 가진 구조 ''N''에서 구조 ''M''으로의 '''기본 매장'''(elementary embedding) 또는 '''초등 매립'''은 다음 조건을 만족시키는 사상(map) ''h'': ''N'' → ''M''을 말한다. 모든 1차 논리 ''σ''-공식 ''φ''(''x''₁, …, ''x''_''n'')와 ''N''의 원소 ''a''₁, …, ''a''_n에 대해,

:''N''

\models

''φ''(''a''₁, …, ''a''_''n'') 일 때 그리고 오직 그럴 때만 ''M''

\models

''φ''(''h''(''a''₁), …, ''h''(''a''_''n''))이다.

기본 매장은 다음 성질들을 만족시킨다.

단사 함수이다. 이는 1차 논리가 등호 기호를 포함하며, 따라서 $m_1\ne m_2$ 이면 $h(m_1)\ne h(m_2)$ 가 성립하기 때문이다.
강준동형사상이다.
정의에 따라 기본 동치 관계를 유도한다. 즉, 구조 ''N''과 그 상(image) ''h''(''N'')은 기본적으로 동치이다.
기본 매장의 상 ''h''(''N'')은 ''M''의 기본 부분 구조이다.

기본 매장은 모형 이론에서 매우 중요한 개념으로 다루어진다. 특히 집합론에서는 정의역이 전체 우주 ''V''인 기본 매장이 거대 기수 이론에서 핵심적인 역할을 수행한다(임계점 참조).

3. 3. 기본 부분 구조의 성질

구조 ''N''이 구조 ''M''의 '''기본 부분 구조'''(elementary substructure) 또는 '''기본 부분 모형'''(elementary submodel)이라는 것은, ''N''과 ''M''이 동일한 서명 ''σ''를 가지며, ''N''이 ''M''의 부분 구조이고, 자유 변수 ''x''₁, ..., ''x''_''n''을 갖는 모든 1차 ''σ''-논리식 ''φ''(''x''₁, ..., ''x''_''n'')와 ''N''의 모든 원소 ''a''₁, ..., ''a''_''n''에 대해 다음 조건이 성립하는 것을 의미한다.^[1]^[2]

N \models \varphi(a_1, \dots, a_n) \text{ iff } M \models \varphi(a_1, \dots, a_n).

이는 ''N''의 원소들로 해석될 때, ''N''에서 참인 모든 1차 논리식은 ''M''에서도 참이며, 그 역도 성립한다는 뜻이다. ''N''이 ''M''의 기본 부분 구조이면, ''N''

\preceq

''M''로 표기하며, ''M''을 ''N''의 '''기본 확장'''(elementary extension)이라고 한다 (''M''

\succeq

''N'').

''N''이 ''M''의 부분 구조일 때, ''N''이 ''M''의 기본 부분 구조가 되기 위한 필요충분 조건은 ''N''과 ''M''이 ''N''의 모든 원소에 대한 새로운 상수 기호를 포함하는 확장된 서명 ''σ''_''N''에 대해 기본 동치라는 것이다.

'''타르스키-보트 조건'''(Tarski–Vaught criterion^영어)은 구조 ''M''의 부분 구조 ''N''이 기본 부분 구조인지 판별하는 데 사용되는 중요한 조건이다.^[1]^[2] ''M''을 서명 ''σ''의 구조, ''N''을 ''M''의 부분 구조라고 할 때, 다음 조건은 ''N''

\preceq

''M''과 동치이다:

임의의 1차 논리식 ''φ''(''x'', ''y''₁, ..., ''y''_''n'')와 ''N''의 임의의 원소 ''b''₁, ..., ''b''_''n''에 대하여, 만약 ''M''에서 ''x''에 대한 해가 존재하여 ''φ''(''x'', ''b''₁, ..., ''b''_''n'')를 만족하면(즉, $M \models \exists x \, \phi(x, b_1, \dots, b_n)$ ), 반드시 ''N'' 안에도 해 ''a''가 존재하여 ''φ''(''a'', ''b''₁, ..., ''b''_''n'')를 만족한다(즉, $M \models \phi(a, b_1, \dots, b_n)$ 인 ''a'' ∈ ''N''이 존재한다).

이 조건은 ''M''에서 어떤 성질을 만족하는 원소가 존재하고 그 성질이 ''N''의 원소들을 사용하여 정의될 수 있다면, 그 성질을 만족하는 원소가 이미 ''N'' 안에 존재해야 함을 의미한다. 타르스키-보트 조건은 큰 구조의 기본 부분 구조를 구성하는 데 유용하게 활용된다.

기본 부분 구조의 존재성은 뢰벤하임-스콜렘 정리와 관련이 있다. 하향 뢰벤하임-스콜렘 정리는 가산 서명을 가진 무한 1차 구조는 항상 (그 구조보다 작거나 같은 크기의) 가산 기본 부분 구조를 가짐을 보장한다. 반대로 상향 뢰벤하임-스콜렘 정리는 모든 무한 1차 구조가 임의로 큰 기수를 갖는 기본 확장을 가짐을 보장한다.

4. 예시

모형 이론에서 다루는 기본 동치, 기본 부분 구조, 기본 매장의 개념을 이해하는 데 도움이 되는 여러 구체적인 예시들이 있다.

예를 들어, 기본 동치의 개념은 유리수의 집합 $\mathbb Q$ 와 실수의 집합 $\mathbb R$ 가 단순한 순서 관계 '<' 아래에서는 같은 1차 논리적 성질을 공유하지만, 덧셈과 곱셈까지 포함하는 순서체 구조에서는 서로 다른 성질을 가진다는 점을 통해 살펴볼 수 있다. 또한, 실수체 $\mathbb R$ 와 초실수체 $^*\mathbb R$ 는 순서체로서 기본 동치인 대표적인 예이다.

기본 부분 구조와 기본 확장의 개념은 뢰벤하임-스콜렘 정리와 밀접하게 연관되어 있으며, 이 정리는 특정 조건을 만족하는 구조 내부에 더 작은 기본 부분 구조가 존재하거나, 외부로 더 큰 기본 확장이 존재함을 보장한다.

기본 매장은 두 구조 사이의 관계를 나타내는 중요한 사상으로, 특히 집합론에서 거대 기수의 존재와 관련된 기본 매장은 중요한 연구 대상이다.

각 개념에 대한 더 자세한 예시는 아래의 해당 하위 섹션에서 구체적으로 설명한다.

4. 1. 기본 동치 예시

워시 정리에 따라, 어떤 모형 M과 그 초거듭제곱 Mⁿ/U는 서로 기본 동치이다.

하나의 이항 관계 기호 '<'만을 가진 언어를 생각해 보자. 이 언어에서 통상적인 순서를 갖는 실수의 집합 ℝ과 유리수의 집합 ℚ는 '<'를 경계 없는 조밀 선형 순서로 해석하기 때문에 서로 기본 동치이다. 이는 Łoś–Vaught 검정(Łoś–Vaught test)을 통해 증명될 수 있는데, 경계 없는 조밀 선형 순서의 이론이 완전하기 때문에 기본 동치가 보장된다.

그러나 유리수의 집합 ℚ와 실수의 집합 ℝ은 순서체의 언어 <+, ·, -, 0, 1, ≤>의 구조로서는 서로 기본 동치가 아니다. 예를 들어, 실수의 완비성 공리(모든 상계를 갖는 공집합이 아닌 부분집합은 최소 상계를 갖는다는 성질)는 ℝ에서는 참이지만 ℚ에서는 거짓이기 때문이다.

반면, 실수체 ℝ와 초실수체 *ℝ는 순서체의 언어 구조로서 서로 기본 동치이다. 이는 초실수체가 실수의 모든 일차 논리적 성질을 만족하도록 구성되었기 때문이다.

또한, 뢰벤하임-스콜렘 정리에 따르면, 무한 모델을 갖는 모든 일차 논리 이론은 서로 동형이 아니면서도 기본 동치인 모델들을 갖는다. 예를 들어, 페아노 산술에는 표준적인 자연수 모델 외에도, 0, 1, 2 등 표준적인 수 외에 다른 객체(무한대 등)를 포함하는 비표준 모델들이 존재한다. 이러한 비표준 모델들은 표준 모델과 기본 동치이다. 즉, 페아노 공리계의 모든 일차 논리 문장에 대해 표준 모델과 비표준 모델은 동일한 진리값을 갖는다.

4. 2. 기본 부분 구조 예시

뢰벤하임-스콜렘 정리는 모델 이론에서 중요한 결과로, 기본 부분 구조와 기본 확장의 존재에 대한 정보를 제공한다. 이 정리는 하향 정리와 상향 정리로 나뉜다.

'''하향 뢰벤하임-스콜렘 정리'''는 가산 서명을 가진 무한 구조는 항상 가산 크기의 기본 부분 구조를 가진다는 것을 보여준다.^[1]^[2] 즉, 아무리 큰 무한 구조라도 그 안에 기본적인 성질을 모두 유지하는 더 작은(가산) 부분 구조를 찾을 수 있다는 의미이다.

'''상향 뢰벤하임-스콜렘 정리'''는 무한 구조가 주어졌을 때, 그 구조의 기본적인 성질을 유지하면서 임의로 더 큰 크기를 갖는 기본 확장을 만들 수 있음을 보여준다.^[1]^[2]

이러한 결과는 어떤 1차 논리 이론이 무한 모델을 하나라도 가진다면, 그 이론은 반드시 서로 동형이 아닌, 즉 크기가 다른 기본 동치 모델들을 무수히 많이 가진다는 것을 함의한다. 이는 1차 논리만으로는 특정 무한 구조(예: 자연수 전체)를 유일하게 특정할 수 없음을 보여주는 중요한 결과이다.

4. 3. 기본 매장 예시

같은 시그니처 ''σ''를 가진 구조 ''N''에서 구조 ''M''으로의 '''초등 매립'''(''elementary embedding'')은 함수 ''h'': ''N'' → ''M''이며, 모든 1차 논리식 ''φ''(''x''₁, …, ''x''_''n'')와 ''N''의 모든 원소 ''a''₁, …, ''a''_n에 대해 다음 조건을 만족한다.

:''N''에서 ''φ''(''a''₁, …, ''a''_''n'')가 참인 것과 ''M''에서 ''φ''(''h''(''a''₁), …, ''h''(''a''_''n''))가 참인 것이 동치이다.

모든 초등 매립은 강한 준동형 사상이며, 그 상(image)은 매립되는 구조 ''M''의 초등 부분구조가 된다.

초등 매립은 모형 이론에서 중요한 위치를 차지하는 사상이다. 특히 집합론 분야에서 중요한 예시를 찾아볼 수 있는데, ''V'' (집합론의 우주 전체)를 정의역으로 하는 초등 매립의 존재 여부는 거대 기수의 존재와 밀접한 관련이 있다. 이러한 초등 매립과 그 임계점에 대한 연구는 거대 기수 이론의 핵심적인 부분을 이루며, 집합론에서의 초등 매립은 거대 기수 이론을 연구하는 데 중요한 도구로 활용된다.

5. 타르스키-보트 판정법 (Tarski-Vaught Test)

'''타르스키-보트 판정법'''(Tarski–Vaught test) 또는 '''타르스키-보트 기준'''(Tarski–Vaught criterion)은 모델 이론에서 어떤 구조 ''M''의 부분 구조 ''N''이 ''M''의 기본 부분 구조가 될 필요충분조건을 제시하는 방법이다.^[2] 이 판정법은 큰 구조의 기본 부분 구조를 구성하는 데 유용하게 사용될 수 있다.

서명 ''σ''를 갖는 구조 ''M''과 ''M''의 부분 구조 ''N''이 있다고 하자. 이때, ''N''이 ''M''의 기본 부분 구조가 되기 위한 필요충분 조건은 다음과 같다:

> 모든 일차 ''σ''-논리식 ''φ''(''x'', ''y''₁, …, ''y''_''n'') (여기서 ''x'', ''y''₁, …, ''y''_''n''은 자유 변수)와 ''N''의 모든 원소 ''b''₁, …, ''b''_''n''에 대해, 만약 ''M''에서 $\exists x \varphi(x, b_1, \dots, b_n)$ 가 성립한다면 (즉, ''M'' 안에 ''φ''를 만족시키는 원소 ''x''가 존재한다면), 반드시 ''N'' 안에도 어떤 원소 ''a''가 존재하여 ''M''에서 $\varphi(a, b_1, \dots, b_n)$ 가 성립해야 한다.

수학적으로 표현하면 다음과 같다:

''N'' $\preceq$ ''M'' (''N''이 ''M''의 기본 부분 구조)인 것은 다음 조건과 동치이다.

모든 논리식 ''φ''(''x'', ''y''₁, …, ''y''_''n'')와 모든 ''b''₁, …, ''b''_''n'' $\in$ ''N''에 대해,

$M \models \exists x \varphi(x, b_1, \dots, b_n) \implies \exists a \in N \text{ s.t. } M \models \varphi(a, b_1, \dots, b_n)$

이 판정법은 타르스키와 로버트 본 보트(Robert Lawson Vaught)가 1957년에 처음 제시하였다.^[2]

참조

_[1] 논문 The use of elementary substructures in combinatorics https://www.scienced[...] Discrete Mathematics 1993
_[2] 논문 The use of elementary substructures in combinatorics https://www.scienced[...] Discrete Mathematics 1993

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

문의하기 : help@durumis.com