구조(수학적 논리)

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 보다 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2010년 4월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

유니버설 대수학과 모델 이론에서 구조는 일련의 미세한 작업과 그것에 정의된 관계와 함께 집합으로 구성된다.

유니버설 대수학은 그룹, 고리, 장, 벡터 공간과 같은 대수 구조를 일반화하는 구조를 연구한다. 유니버설 대수라는 용어는 관계 기호가 없는 구조물에 사용된다.^[1]

모델 이론은 세트 이론의 모델과 같은 기초 구조를 포함하여, 보다 자의적인 이론을 포괄하는 다른 범위를 가지고 있다. 모델-이론적 관점에서 구조는 1차 논리학의 의미론을 정의하는 데 사용되는 객체다. 모델 이론에서 주어진 이론의 경우, 어떤 구조가 그 이론의 정의 공리를 만족한다면 모델이라고 불리는데, 비록 수학 모델의 더 일반적인 설정에서 개념을 논할 때 의미론적 모델로서 모호해지기도 한다. 논리학자들은 때때로 구조를 해석이라고 말한다.^[2]

데이터베이스 이론에서, 함수가 없는 구조는 관계형 데이터베이스의 모델로서 관계형 모델의 형태로 연구된다.

정의

형식적으로는 도메인 A, 서명 σ, 해석 함수 I로 구성된 트리플 $A{\displaystyle \mathcal{}}$=${\displaystyle }$( A${\displaystyle }$, ${\displaystyle \sigma }$, ${\displaystyle I}$) ${\displaystyle {\mathcal{A}=(A,\sigma ,I)}$로 정의할$$ 수 있다. 구조물에 특정 시그니처가 있음을 나타내기 위해 σ 구조라고 할 수 있다.

도메인

구조의 영역은 임의의 집합이다. 구조의 기초 집합, 그 전달자(특히 보편적 대수학), 또는 그 우주(특히 모델 이론)라고도 불린다. 고전적인 1차 논리에서는 구조의 정의가 빈 영역을 금지한다.^{[citation needed][3]}

Sometimes the notation ${\displaystyle \operatorname {dom} ({\mathcal {A}})}$ or ${\displaystyle {\mathcal {A}} }$ is used for the domain of ${\displaystyle {\mathcal {A}}}$, but often no notational distinction is made between a structure and its domain. (I.e. the same symbol ${\disp$$레이스타일 {\mathcal{A}}$은(는) 구조와 그 영역을 모두 가리킨다$$.^[4]

서명

구조물의$$ 시그니처 $\sigma {\displaystyle }$=${\displaystyle }$( S ,${\displaystyle \mathrm{ar}}$) ${\displaystyle \sigma =(S,\operatorname {ar}$)는 함수 ${\displaystyle ar\text{:}}$ S${\displaystyle }$→ N ${\displaystyle {\mathrm{}}_{}}$ ${\$과(와)의 $함수$ 기호의 S ${\displaystystyle S}$로 구성된다$.$$}}\S\to \mathb{N} _{0}$ 각 기호에 귀속되는 $자연수$ n${\displaystyle }$= ${\displaystyle \mathrm{ar}}$ ${\displaystyle }$( s$){\displaystyn=\operatorname {ar}}}}$은(는$)$ s의 해석의 경성이기 때문에 s의 경성이라고 불린다.

대수에서 발생하는 서명은 함수 기호만 포함하는 경우가 많기 때문에 관계 기호가 없는 서명은 대수서명이라고 한다. 그러한 서명이 있는 구조를 대수라고도 한다. 이것은 한 분야에 걸친 대수학의 개념과 혼동해서는 안 된다.

해석함수

$A{\displaystyle \mathcal{}}$ ${\$의 해석 함수 I는 서명의 기호에 함수 및 관계를 할당한다$$. arity n의 각 함수 기호 f는 도메인에서$$ ${\displaystyle {n-ary\mathcal{}}^{}}$ $함수{\displaystyle {}^{}}$ f${\displaystyle {}^{}}$= I${\displaystyle }$( ${\displaystyle f}$) ${\displaystyle$ f$^{\mathcal{A}=I(f)}$가 할당된다. arity n의 각 관계 기호 $R$에 ${\displaystyle {n-ary\mathcal{}}^{}}$ 관계 R${\displaystyle {}^{}}$= I${\displaystyle }$( ${\displaystyle R}$) ${\displaystyle \subseteq }$ ${\displaystyle {A\mathrm{}}^{}}$ ${\displaystyle {}^{}}$( $){\$ R$^{\mathcal{A}}=I(R)}}=$I(R)\$subseteq A^{\operatorname {ar(R)}}}}}}}$ 도메인이$$ 할당된다. 무효 함수 기호 c는 그 해석 I(c)를 도메인의 상수 요소로 식별할 수 있기 때문에 상수 기호라고 한다.

구조(따라서 해석함수)가 문맥에 의해 주어질 때, 기호 s와 해석 I 사이에 공칭적 구분이 이루어지지 않는다. For example, if f is a binary function symbol of ${\displaystyle {\mathcal {A}}}$, one simply writes ${\displaystyle f:{\mathcal {A}}^{2}\rightarrow {\mathcal {A}}}$ rather than ${\displaystyle f^{\mathcal {A}}: {\mathcal {A}} ^{2}\rightarrow {\mathcal$${A}$ $\}.$

예

필드의 표준서명 σ은_f 2개의 이항 함수 기호 +와 ×로 구성되며, 여기서 1개의 상수 기호 - (+에 의해 고유하게 결정됨)와 0과 1(+와 ×에 의해 각각 고유하게 결정됨)과 같은 추가 기호를 도출할 수 있다. 따라서 이 서명에 대한 구조(알지브라)는 단항 함수로 강화될 수 있는 두 개의 이항 함수와 두 개의 구별되는 요소와 함께 요소 A의 집합으로 구성되지만, 필드 공리를 만족시킬 필요는 없다. 다른 분야와 마찬가지로 합리적인 숫자 Q, 실제 숫자 R 및 복잡한 숫자 C도 명백한 방법으로 σ 구조로 간주할 수 있다.

${\displaystyle {\mathcal{Q}}=(Q,\sigma _{f},I_{\mathcal{Q}}}$

${\displaystyle {\mathcal{R}=(R,\sigma _{f},I_{\mathcal{R}}}$

${\displaystyle {\mathcal{C}=(C,\sigma _{f},I_{\mathcal{C}}}$

세 가지 경우 모두 다음과 같은 표준 서명을 받는다.

${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f}})$

와 함께

${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$, ${\displaystyle \operatorname {ar} _{f}(+)=\operatorname {ar} _{f}(\times )=2,\operatorname {ar} _{f}(-)=1,\operatorname {ar} _{f}(0)=\operatorname {ar} _{$$f}(1)=0}$^[5].

해석 함수:

${\displaystyle I_{}}$ ${\displaystyle Q_{}}$(${\displaystyle }$+${\displaystyle }$)${\displaystyle }$: ${\displaystyle Q}$ ${\displaystyle \times }$ Q${\displaystyle }$→ Q ${\displaystyle I_{\mathcal {{Q}(+)\colon Q\time$ Q$\to Q}$는 합리적인 숫자의 추가,

${\displaystyle I_{}}$ ${\displaystyle {Q\mathcal{}}_{}}$ (${\displaystyle \times }$ )${\displaystyle }$: ${\displaystyle Q}$ ${\displaystyle \times }$ Q${\displaystyle }$→ Q ${\displaystyle I_{\mathcal{Q}(\time )\colon Q\time$ Q$\to Q}$는 합리적인$$ 숫자의 곱셈이다.

${\displaystyle I_{}}$ ${\displaystyle Q_{}}$(${\displaystyle }$-${\displaystyle }$)${\displaystyle }$: ${\displaystyle Q}$→ ${\displaystyle Q}$ ${\displaystyle I_{\mathcal{Q}}(-)\colon$Q\$to$ Q$}$는 각 합리적인 숫자 x ~ -x를 취하는 함수로서,

${\displaystyle I_{}}$ ${\displaystyle Q_{}}$( ${\displaystyle 0}$) ${\displaystyle \in }$ ${\displaystyle Q}$ ${\displaystyle I_{\mathcal {Q}(0)\in Q}$는 숫자 0이고

${\displaystyle I_{}}$ ${\displaystyle {Q(}_{}1}$) ${\displaystyle \in }$ ${\displaystyle Q}$ ${\displaystyle I_{\mathcal{Q}(1)\in$ Q$}$는 숫자 1이다.

및 $I{\displaystyle {}_{}}$ ${\displaystyle {R\mathcal{}}_{}}$ ${\$과(와) $I{\displaystyle {}_{}}$ ${\displaystyle {C\mathcal{}}_{}}$ ${\$은(와) 유사하게 정의된다$$.^[5]

그러나 필드가 아닌 정수의 링 Z도 같은 방식으로 σ_f 구조다. 사실, 어떤 필드 공리가 σ-구조물에_f 포함되어야 하는 요구사항은 없다.

순서가 정해진 분야의 서명은 < 또는 ≤과 같은 추가적인 이항 관계가 필요하며, 따라서 그러한 서명에 대한 구조는 알헤브라가 아니며, 비록 그것들이 통상적이고 느슨한 단어의 의미에서는 물론 대수적 구조라고 하더라도 말이다.

집합 이론의 일반적인 서명은 단일 이항 관계 ∈을 포함한다. 이 서명에 대한 구조는 요소들의 집합과 이들 요소들에 대한 이진관계로서의 ∈관계의 해석으로 구성된다.

유도 하부 구조 및 폐쇄 하위 세트

${\$은(는) $B{\displaystyle \mathcal{}}$ ${\$의 (유인) 하부구조라고 한다$$.

• ${\displaystyle \mathcal{A}}$ ${\$과(와) $B{\displaystyle \mathcal{}}$ ${\$의 시그니처 $signature$(A )${\displaystyle }$= ${\displaystyle \sigma (B}$) ${\displaystyle \sigma({\mathcal {A})=\sigmatcal$ {$B}$;
• $A{\displaystyle \mathcal{}}$ ${\$의 도메인은 $B{\displaystyle \mathcal{}}$ ${\$: ${\displaystyle A\mathcal{}}$ ${\displaystyle \subseteq }$ ${\displaystyle B\mathcal{}}$ $displaystyle {\mathcal {A} \subseteq {\mathcal {B$의 도메인에 포함되어 있으며$$$,$
• ${\displaystyle 모든\mathcal{}}$ 함수 및 관계 기호의 해석은 A $displaystyle {\mathcal{A}}$에 동의한다$.$

이 관계에 대한 일반적인 표기법은 $A{\displaystyle \mathcal{}}$ ${\displaystyle \subseteq }$ ${\displaystyle B\mathcal{}}$ ${\$이다$.$

A subset ${\displaystyle B\subseteq {\mathcal {A}} }$ of the domain of a structure ${\displaystyle {\mathcal {A}}}$ is called closed if it is closed under the functions of ${\displaystyle {\mathcal {A}}}$, i.e. if the following condition is satisfied: for every natural number n, every n-ary function symbol f (in the signature of ${\displaystyle {\mathcal {A}}}$) and all elements ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in B}$, the result of applying f to the n-tuple ${\displaystyle b_{1}b_{2}\dots b_{n}}$ is again an element of B: ${\displaystyle f(b_1,b_2,}$${\displaystyle \dots }$, ${\displaystyle b_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle \in }$ ${\displaystyle B}$ ${\displaystyle f(b_{1},b_{2},\dots,b_{n}\in$ B$\}.$

$모든{\displaystyle }$ 부분 집합 B ${\displaystyle \subseteq }$ ${\displaystyle A\mathcal{}}$ $displaystyle B\subseteq {\mathcal {A}}$에 대해 B를 포함하는$$ A $displaystyle {\mathcal {A}의$ 닫힌 부분 집합이 있다$$. It is called the closed subset generated by B, or the hull of B, and denoted by ${\displaystyle \langle B\rangle }$ or ${\displaystyle \langle B\rangle _{\mathcal {A}}}$. The operator ${\displaystyle \langle \rangle }$ is a finitary closure operator on the set of subsets of ${\displaysty$$le${\$mathcal{A$ .

If ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ and ${\displaystyle B\subseteq A}$ is a closed subset, then ${\displaystyle (B,\sigma ,I')}$ is an induced substructure of ${\displaystyle {\mathcal {A}}}$, where ${\displaystyle I'}$ assigns to every symbol of σ $A{\displaystyle \mathcal{}}$ ${\$의 해석 B에 대한 제한$.$ 반대로 유도 하부 구조의 영역은 닫힌 부분집합이다.

구조물의 폐쇄 하위 집합(또는 유도 하부 구조)은 격자를 형성한다. 두 하위 집합의 만남은 그들의 교차점이다. 두 하위 집합의 결합은 그들의 결합에 의해 생성된 닫힌 하위 집합이다. 유니버설 대수학은 구조물의 하부 구조들의 격자를 자세히 연구한다.

예

σ = {+, ×, -, 0, 1}을(를) 다시 필드의 표준 서명이 되게 한다. 자연적으로 σ 구조로 간주될 때, 합리적인 숫자는 실수의 하부 구조를 형성하고, 실수는 복잡한 숫자의 하부 구조를 형성한다. 합리적인 숫자는 필드 공리를 만족하는 실제(또는 복잡한) 숫자의 가장 작은 하부 구조다.

정수의 집합은 필드가 아닌 실수의 하위 구조를 훨씬 더 작게 제공한다. 실제로, 정수는 이 서명을 사용하여 빈 집합에 의해 생성된 실수의 하부 구조다. 한 분야의 하부 구조에 해당하는 추상 대수학에서의 개념은, 이 서명에서, 하위 영역의 개념이라기보다는 하위 영역의 개념이다.

그래프를 정의하는 가장 확실한 방법은 단일 이진관계 기호 E로 구성된 시그니처 signature이 있는 구조다. 그래프의 꼭지점은 구조의 도메인을 형성하며, 두 꼭지점 a와 b, ${\displaystyle (,}$ ${\displaystyle b}$)${\displaystyle for}$ E ${\$$\in {\text{$$E}}}$은 a와 b가 엣지로 연결되어 있음을 의미한다$$. 이 부호화에서 유도 하부구조의 개념은 서브그래프의 개념보다 더 제한적이다. 예를 들어, G는 가장자리로 연결된 두 개의 정점으로 구성된 그래프가 되고 H는 가장자리는 없지만 같은 정점으로 구성된 그래프가 되도록 한다. H는 G의 하위 그래프지만 유도 하부 구조는 아니다. 유도 하부구조에 해당하는 그래프 이론의 개념은 유도 하위구조의 개념이다.

동형체 및 임베딩

동형성

Given two structures ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ of the same signature σ, a (σ-)homomorphism from ${\displaystyle {\mathcal {A}}}$ to ${\displaystyle {\mathcal {B}}}$ is a map ${\displaystyle h: {\mathcal {A}} \rightarrow$$$기능과 관계를 보존하는$$ ${\mathcal{B}}.$ 더 정확히 말하자면:

• σ의 모든 n-ary 함수 ${\displaystyle {기호\mathrm{}}_{}}$ ${\displaystyle {}_{}}$와 $1{\displaystyle {}_{}}$, a${\displaystyle {}_{}{2\mathrm{}}_{}}$ …${\displaystyle {}_{}}$,${\displaystyle }$n${\displaystyle n\mathcal{}{}_{}}$A $displaystyle a_{1},a_{2},\dots ,a_{n}\in {\mathcal{A$에 대해 다음 방정식은 다음을 포함한다.

${\displaystyle h(}$ ${\displaystyle {f\mathrm{}}_{}}$( 1${\displaystyle {}_{}}$, a ${\displaystyle 2_{}{}_{}}$,${\displaystyle }$… ,${\displaystyle }$n${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle f}$(${\displaystyle {}_{}}$)${\displaystyle }$, h${\displaystyle }$( ${\displaystyle {}_{}{}_{}}$)${\displaystyle }$,${\displaystyle }$… ,${\displaystyle h_{}}$( ${\displaystyle n{}_{}}$)${\displaystyle h(a_{1},\a_{2},\n})=f(a_{1}, h(a_{$2}), h$(a_{n$}),\h$(a_$n$}.$

• $\sigma$의 모든 n-ary 관계 기호 R과 ${\displaystyle {1\mathrm{}}_{}}$, a ${\displaystyle {2\mathrm{}}_{}}$…${\displaystyle }$, ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$ A $displaystyle a_{1},a_{2},\dots ,a_{n}\in {\mathcal{A$에 대해 다음과 같은 함축적 의미가 있다.

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R}$.

$A{\displaystyle \mathcal{}}$ ${\$에서 $B{\displaystyle \mathcal{}}$ ${\$까지의 동형동형 h에 대한 표기법은$$ h${\displaystyle }$: ${\displaystyle A\mathcal{}}$→ B ${\$이다$.$

모든 시그니처 σ에 대하여 σ 구조물을 객체로 하고 σ-호몰리즘을 형태론으로 하는 구체적인 범주가 있다.

A homomorphism ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ is sometimes called strong if for every n-ary relation symbol R and any elements ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in {\mathcal {B}} }$ such that ${\displaystyle (b_1,b_2,\dots ,b_n)\in }$${\displaystyle (b_{1},b_{2},\dots ,b_{n})\in R}$, there are ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in {\mathcal {A}} }$ such that ${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R}$ and ${\displaystyle b_1=h(a_1),b_2=h(a_2),}$${\displaystyle b_{1}=h(a_{1}),\,b_{2}=h(a_{2}),\,\,\,\,b_{n}=h(a_{n}).$$}}$ 강한$$^{[citation needed]} 동형체는 σ-Hom의 하위 범주를 낳는다.

임베딩스

A (196-)호모형성 $h{\displaystyle }$: ${\displaystyle A}$→ ${\displaystyle B\mathcal{}}$ ${\$ h$:{\mathcal {A}\오른쪽$ 화살표 ${\mathcal {B}}}}$은(는) 일대일이고, 1대1이면 (ㄴ-)엠베딩이라고 한다$$.

• ${\displaystyle {\sigma }_{}}$의 모든 n-ary 관계 기호 R과 ${\displaystyle 1_{}{}_{}}$, ${\displaystyle {a\mathrm{}}_{}}$ ${\displaystyle {}_{}}$…${\displaystyle }$, n ${\$에 대해 다음과 같은 동등성이 유지된다.

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R}$.

그러므로 임베딩은 일대일이라는 강한 동형주의와 같은 것이다. σ-Emb of σ-구조물 및 em-embedding 카테고리는 hom-Hom의 콘크리트 하위 카테고리다.

유도 하부 구조는 σ-Emb의 하위 객체에 해당한다. σ에 함수 기호만 있는 경우 σ-Emb는 σ-Hom의 단형화 하위 범주다. 이 경우 유도 하부 구조도 σ-Hom의 하위 객체에 해당한다.

예

위에서 본 바와 같이, 구조로서의 그래프의 표준 인코딩에서 유도 하부구조는 정확하게 유도 하위구조가 된다. 그러나 그래프 사이의 동형성은 그래프를 코드화하는 두 구조 사이의 동형성과 같은 것이다. 앞 절의 예에서 G의 서브그래프 H를 유도하지 않더라도, ID맵 ID: H → G는 동형성이다. 이 지도는 사실 σ-Hom 범주에 있는 단성형이며, 따라서 H는 유도 하부 구조가 아닌 G의 하위 객체다.

동형성 문제

다음과 같은 문제를 동형상주의 문제로 알려져 있다.

유한 관계 서명의$$ $A{\displaystyle \mathcal{}}$ ${\$ 및 B$$ ${\$이(가) 두 개의 유한 구조를 지정하면 동형성 $h{\displaystyle }$: A${\displaystyle }$→ ${\displaystyle B\mathcal{}}$ ${\${A$}\mathcal {B}$을 찾거나 그러한$$ 동형성이 존재하지 않음을 나타낸다.

모든 제약조건 만족 문제(CSP)는 동형성 문제에 대한 번역이 있다.^[6] 따라서 CSP의 복잡성은 유한 모델 이론의 방법을 사용하여 연구할 수 있다.

다른 애플리케이션은 데이터베이스 이론에 있는데, 데이터베이스의 관계형 모델은 관계형 구조와 본질적으로 동일하다. 데이터베이스에 대한 접속 질의를 데이터베이스 모델과 동일한 서명으로 다른 구조로 설명할 수 있는 것으로 나타났다. 관계형 모델에서 질의를 나타내는 구조로 가는 동형성은 질의에 대한 해답과 같은 것이다. 이는 결벽 질의 문제도 동형문제의 문제와 동등하다는 것을 보여준다.

구조와 1차 논리

구조물은 때때로 "1차 구조"라고 불린다. 이는 오해의 소지가 있는 것으로, 그들의 정의에서 어떤 특정한 논리와도 연관되지 않으며, 사실 그것들은 보편대수학에서 사용되는 것과 같은 1차 논리학의 매우 제한된 단편과 2차 논리 모두에 의미적 대상으로 적합하다. 1차 논리학 및 모델 이론과 관련하여, "무엇의 모델"이라는 물음에 뚜렷한 답이 없을 때에도 구조를 모델이라고 부르는 경우가 많다.

만족관계

Each first-order structure ${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$ has a satisfaction relation ${\displaystyle {\mathcal {M}}\vDash \phi }$ defined for all formulas ${\displaystyle \,\phi }$ in the language consisting of the language of ${\displaystyle {\mathcal {M}}}$ togethe$r{\displaystyle }$ 이 M ${\displaystyle M}$의 각 요소에 대한 상수 기호를 포함하며$,$ 이 기호는 이 요소로 해석된다. 이 관계는 타르스키의 T-schema를 사용하여 귀납적으로 정의된다.

A structure ${\displaystyle {\mathcal {M}}}$ is said to be a model of a theory T if the language of ${\displaystyle {\mathcal {M}}}$ is the same as the language of T and every sentence in T is satisfied by ${\displaystyle {\mathcal {M}}}$. Thus, for example, a "ring" is a structure for the language of rings that은 각각의 고리 공리를 만족시키며, ZFC 세트 이론의 모델은 각각의 ZFC 공리를 만족시키는 세트 이론 언어의 구조다.

정의 가능한 관계

$M{\displaystyle \mathcal{}}$ ${\$ {$M}$의 우주$$ $M{\displaystyle }$ ${\displaystyle M}$에 대한 n-ari 관계 R은 공식 φ(x₁,...,x_n)이 있는 경우(또는 명시적으로 정의할 수 있거나, $\varnothing {\displaystyle \mathrm{}}$ ${\displaysty \emptyset }$ -definable$$)이라고 한다$$.

${\displaystyle R=\{(a_{1},\ldots,a_{n})\in M^{n}:{n}}\mathcal {M}\vDash \varphi(a_{1},\ldots,a_{n})\}.}$

즉, 다음과 같은 공식 formula이 있는 경우에만 R을 정의할 수 있다.

${\displaystyle(a_{1},\ldots ,a_{n})\R\좌우 이동 {\mathcal {M}\vDash \vDash \varphi(a_{1},\ldots ,a_{n})}$

옳다.

중요한 특별한 경우는 특정 요소의 정의 가능성이다. $M{\displaystyle }$ ${\displaystyle M}$의 요소 m은 다음과 같은 공식 φ(x)이 있는 경우에만$$ $M{\displaystyle \mathcal{}}$ ${\$에서 정의할 수 있다$$.

${\displaystyle {\mathcal{M}\vDash \forall x(x=m\왼쪽 오른쪽 화살표 \varphi(x)).}$

매개 변수를 사용하여 정의 가능

$관계{\displaystyle \mathcal{}}$ R은 M ${\$ ${\m$}의 매개변수를 갖는 공식 φ이 있는 경우 매개변수(${\displaystyle 또는\mathcal{}}$ M $displaystyle$ ${\mathcal {M}$ - definitionable$$)로 정의할 수 있으며, R은 φ을 사용하여 정의할 수 있다. 구조물의 모든 요소는 요소 자체를 매개 변수로 사용하여 정의할 수 있다.

일부 저자는 매개변수 없이 정의 가능하다는 것을 의미하며,^{[citation needed]} 다른 저자는 매개변수로 정의 가능하다는 것을 의미한다.^{[citation needed]} 대체로, 정의 가능한 것은 매개변수 없이 정의 가능하다는 관습은 집합 이론가들 사이에서 더 일반적인 반면, 반대 개념은 모형 이론가들 사이에서 더 흔하다.

암시적 정의 가능성

위로부터 상기시켜 보십시오. $M{\displaystyle \mathcal{}}$ ${\$의 우주 $M{\displaystyle }$ ${\displaystyle M}$에 다음과 같은 공식 φ(x₁,...,x_n)이 있으면 명시적으로 정의할 수 있다$$.

${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{n}:{n}}\mathcal {M}\vDash \phi(a_{1},\ldots,a_{n}}\}}}}}}).$

여기서 관계 R을 정의하는 데 사용되는 공식 $\phi$은 M ${\$의 서명 위에 있어야 하므로$$, R이 $M{\displaystyle \mathcal{}}$ ${\$의 서명에 있지 않기 때문에, R 자체를 언급하지 않을 수 $있다{\displaystyle \mathcal{}}$$.$ M$${\$displaystyle${\$mathca$}의 언어를 포함하는 확장 언어에 공식 φ이 있는 경우$l {M}}$과(와) 새로운 기호 R, 관계 R은 $M{\displaystyle \mathcal{}}$${\displaystyle$ ${\$$mathcal$ {M}과(와) 같은$$ M${\$displaystyle ${\\mathcal {M}$에 대한 유일한 관계로서$,$ ${\displaystyle \mathrm{그러면}}$ R은 $M{\displaystyle \mathcal{}}$ ${\$에 대해 암묵적으로 정의할 수 있다고 한다$.$

베스의 정리에 의해, 암묵적으로 정의될 수 있는 모든 관계는 명백하게 정의될 수 있다.

다변형 구조물

위에서 정의한 구조물을 보다 일반적인 다변형 구조와 구별하기 위해 단변형 구조라고 부르기도 한다. 여러 종류의 구조는 임의의 수의 도메인을 가질 수 있다. 이 분류들은 서명의 일부분이며, 그것들은 다른 도메인의 이름 역할을 한다. 또한 다변형 서명은 다변형 구조의 기능 및 관계를 정의하는 것에 대해 규정한다. 따라서 함수 기호나 관계 기호의 아성은 자연수보다 분류의 튜플과 같은 더 복잡한 물체여야 한다.

예를 들어 벡터 공간은 다음과 같은 방법으로 두 갈래 구조로 간주할 수 있다. 벡터 공간의 두 가지 형태 서명은 두 가지 종류의 V(벡터용)와 S(스칼라용)와 다음과 같은 기능 기호로 구성된다.

+S 및 ×S 아리티(S, S; S) -S 경성(S; S) 0과S 1의S 아리티(S).

+V 아리티(V, V, V) -V 경건함(V; V). 0의V 아리티(V).

× 아리티(S, V; V).

If V is a vector space over a field F, the corresponding two-sorted structure ${\displaystyle {\mathcal {V}}}$ consists of the vector domain ${\displaystyle {\mathcal {V}} _{V}=V}$, the scalar domain ${\displaystyle {\mathcal {V}} _{S}=F}$, and the obvious functions, such as the vector zero ${\displaystyle 0_{V}^{\mathcal {V}}=0\in {\mathcal {V}} _{V}}$, the scalar zero ${\displaystyle 0_{S}^{\mathcal {V}}=0\in {\mathcal {V}} _{S}}$, or scalar multiplication ${\displaystyle {\times }^{\mathcal{V}}:\mathcal{V}{}_S\times \mathcal{V}{}_V\to \mathcal{V}}$${\displaystyle {}_V}$ ${\$오른쪽 $화살표 {\mathcal {V} _{V$

여러 가지 형태의 구조물은 조금만 노력해도 피할 수 있을 때도 편리한 도구로 이용되는 경우가 많다. 그러나 명시적으로 일반화를 실시하는 것은 직설적이고 지루하기 때문에, 엄밀한 방법으로 규정되는 경우는 거의 없다.

대부분의 수학적인 노력에서, 그 종류에는 별로 관심이 없다. 그러나 여러 가지 종류의 논리는 자연스럽게 유형 이론으로 이어진다. 바트 제이콥스가 말했듯이, "논리는 항상 유형 이론보다 논리적인 것이다." 이러한 강조는 결국 범주형 논리로 이어진다. 왜냐하면 형식 이론에 대한 논리는 하나의 ("전체") 범주에 분류적으로 대응하고, 논리를 포착하고, 다른 ("기본") 범주에 대해 거짓말을 하고, 유형 이론을 포착하기 때문이다.^[7]

기타 일반화

부분 알헤브라스

유니버설 대수학 및 모델 이론 모두 서명과 공리 집합에 의해 정의된 (구조체 또는) 알헤브라의 클래스를 연구한다. 모형 이론의 경우 이러한 공리는 일차 문장의 형태를 가지고 있다. 보편적 대수학의 형식주의는 훨씬 더 제한적이다; 본질적으로 그것은 단지 1차적인 문장들 사이에 보편적으로 정량화된 방정식의 형태를 가진, 예를 들어, $\forall {\displaystyle \mathrm{}}$ ${\displaystyle$\$forall}$ $x$ x $\forall {\displaystyle \mathrm{}}${\$displaystyle \for$}$y$ (x + y = y + x)를 허용한다. 한 가지 결과는 서명의 선택이 모델 이론에서보다 보편적 대수에서 더 유의하다는 것이다. 예를 들어, 이항함수 기호 ×와 상수 기호 1로 구성된 서명에 있는 그룹의 등급은 초등 등급이지만, 다양하지는 않다. 유니버설 대수학은 단항 함수 기호를 추가함으로써 이 문제를 해결한다.

필드의 경우 이 전략은 추가에만 적용된다. 곱셈의 경우 0에 곱셈 역이 없기 때문에 실패한다. 이를 처리하기 위한 임시 시도는 0⁻¹ = 0을 정의하는 것이다. (이 시도는 실패하는데, 이는 기본적으로 이 정의가 0 × 0⁻¹ = 1이 사실이 아니기 때문이다.) 따라서 자연스럽게 부분함수, 즉 도메인의 부분집합에서만 정의되는 함수를 허용하게 된다. 그러나 하부구조, 동형성, 정체성과 같은 개념을 일반화하는 몇 가지 분명한 방법이 있다.

입력된 언어에 대한 구조

유형론에는 여러 종류의 변수가 있는데, 각 변수에는 유형이 있다. 형식은 귀납적으로 정의된다. Δ와 Δ가 두 가지 유형인 경우 Δ의 개체에서 Δ의 개체까지의 기능을 나타내는 σ → Δ의 유형도 있다. 형식 언어의 구조(일반적인 1차 의미론에서)는 각 유형의 개체 세트를 별도로 포함해야 하며, 기능 유형의 경우 구조는 해당 유형의 각 개체로 대표되는 기능에 대한 완전한 정보를 가지고 있어야 한다.

고차어군

2차 논리학 논문에서 논의한 바와 같이 고차 논리학에는 두 가지 이상의 가능한 의미론들이 있다. 완전 고차수 의미론을 사용할 때 구조는 0형의 물체를 위한 우주만 있으면 되고, T-schema는 고차형 이상의 정량자가 정량적으로 참인 경우에만 모델에 의해 충족되도록 확장된다. 1차 의미론을 사용할 경우 정렬된 1차 순서 언어의 경우처럼 고차 유형별로 추가 정렬이 추가된다.

적절한 등급인 구조물

집합이론과 범주이론의 연구에서는 담론의 영역이 집합이 아닌 적절한 계급인 구조를 고려하는 것이 유용할 때가 있다. 이러한 구조물을 위에서 논의한 "세트 모델"과 구별하기 위해 클래스 모델이라고도 한다. 도메인이 적절한 클래스인 경우, 각 함수 및 관계 기호도 적절한 클래스로 나타낼 수 있다.

베르트랑드 러셀의 <프린키시아 매스매티카>에서도 구조물은 그들의 영역으로서 적절한 클래스를 가질 수 있도록 허용되었다.

참고 항목

• 수학적 구조

메모들

참조

• Burris, Stanley N.; Sankappanavar, H. P. (1981), A Course in Universal Algebra, Berlin, New York: Springer-Verlag
• Chang, Chen Chung; Keisler, H. Jerome (1989) [1973], Model Theory, Elsevier, ISBN 978-0-7204-0692-4
• Diestel, Reinhard (2005) [1997], Graph Theory, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Mathematical Logic (2nd ed.), New York: Springer, ISBN 978-0-387-94258-2
• Hinman, P. (2005), Fundamentals of Mathematical Logic, A K Peters, ISBN 978-1-56881-262-5
• Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-30442-9
• Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6
• Marker, David (2002), Model Theory: An Introduction, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98760-6
• Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98655-5
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
• Rothmaler, Philipp (2000), Introduction to Model Theory, London: CRC Press, ISBN 978-90-5699-313-9

외부 링크

• 고전논리의 의미론 섹션(스탠포드 철학 백과사전 수록)