하위 가산성

구성 수학에서 $X$ $X$ 집합은 자연수에서 부분 사영이 존재할 경우 부분적으로 계산할 수 있습니다 $X$ .이는 다음과 같이 표현할 수 있습니다.

\exists (I\subseteq {\mathbb {N}}).\,\exist f.\,(f\colon I\two headright arrow X),

여기서

f\colon I\twoheadrightarrow X

:

f\colon I\twoheadrightarrow X

↠

f\colon I\twoheadrightarrow X

{\displaystyle f\colon I\two

headright arrow

X}

는 f

f

가

I

I

에서

X

X

로의 주관 함수임을 나타냅니다

X

사영은

{\mathbb {N} }\rightharpoonup X

⇀

{\mathbb {N} }\rightharpoonup X

{\mathbb {N}}\rightharpoonup X

의 멤버이며, 여기서

{\mathbb {N} }

{\mathbb {N}}

의 하위 클래스

I

I

은(는) 집합이어야 합니다.즉, 하위 카운트 집합

X

X

의 모든 요소는 기능적으로 계수 집합

I\subseteq {\mathbb {N} }

⊆

I\subseteq {\mathbb {N} }

I\subseteq {\mathbb {N}}

의 이미지에 있으므로

X

X

X

는 계수 집합

{\mathbb {N} }

{\mathbb {N}

에 의해 지배되는 것으로 이해할 수 있습니다

{\mathbb {N} }

논의

명명법

가산성과 유한성 속성의 명명법은 상당히 다양한데, 이는 부분적으로 제외된 중간을 가정할 때 많은 속성이 일치하기 때문입니다.반복하자면, 여기서는 특성화되는 $X$ 집합 $X$ $X$ 에 대한 사영의 관점에서 정의된 속성에 대해 논의합니다.여기서 언어는 구성 집합 이론 텍스트에서 일반적이지만 하위 계수라는 이름은 특성화되는 집합 밖의 주입의 관점에서 속성에 부여되었습니다.

정의에서 집합 ${\mathbb {N} }$ ${\mathbb {N} }$ ${\$ 은(는) 추상화될 수도 있으며, 보다 일반적인 $개념$ X ${\$ $displaystyle$ $X}$ 을(를 $)$ N {\displaystyle ${\mathbb {N}}$ 의 하위 계수라고 할 수 있습니다 $X$ ${\mathbb {N} }$

예

중요한 경우는 해당 집합이 계산 가능성 이론에서 연구된 함수의 더 큰 클래스의 하위 클래스인 경우입니다.

${\mathbb {N} }$ 구성의 함수 $n\mapsto f_{n}(n)+1$ ↦ $n\mapsto f_{n}(n)+1$ $n\mapsto f_{n}(n)+1$ ( $n\mapsto f_{n}(n)+1$ n $n\mapsto f_{n}(n)+1$ ) $n\mapsto f_{n}(n)+1$ + $n\mapsto f_{n}(n)+1$ $n\mapsto f_{n}$ 을(를) 통해 표시된 것처럼 $X$ $N$ {\ $displaystyle$ {\ $mathbb$ {N $}}}$ 에서 총 계산 $X$ 한함수 X {\ $displaystyle X}$ 집합으로 계산 가능한 사영 $n\mapsto f_{n}$ ↦ $n\mapsto f_{n}$ $n\mapsto f_{n}$ {\mapsto f_ ${n$ }( $n)+1$ 이 있을 수 없습니다.그러나 종료되지 않는 프로그램도 허용하는 모든 가능한 부분 계산 가능 함수의 코드를 통해 전체 함수와 같은 함수의 하위 집합이 하위 집합으로 보입니다.총 함수는 자연수의 일부 $I$ 엄격한 부분 $집합$ I $I$ 의 범위입니다.계산할 수 없고, 따라서 구조적으로 셀 수 없는 수들의 집합에 의해 지배되므로, 부분수라는 이름은 구조적으로 셀 수 없는 집합 $X$ ${\$ $displaystyle$ $X}$ 가 $X$ ${\mathbb {N} }$ ${\mathbb {N}}}$ 보다 크지 않음을 전달합니다 ${\mathbb {N} }$ 모든 수 ${\mathbb {N} }$ ${\$ 과 ${\mathbb {N} }$ (와) 경계 없음 및 없음 사이에는 유효한 맵이 없음을 유의하십시오.n개의 유한 인덱스 집합 $I$ $I$ 이(가) 여기서 주장됩니다. 단지 부분 집합 관계 $I\subseteq {\mathbb {N} }$ ⊆ N ${\displaystyle I\subseteq {\mathbb {}}}.$ 전체가 되는 것은 결정할 수 없는 속성이 아닌 것으로 유명합니다.인덱스 집합에 대한 Rice의 정리에 의해, 인덱스의 대부분의 도메인은 사실 계산 가능한 집합이 아닙니다.

$X$ $X$ 이 $X$ (가) 하위 계산 가능하다는 것을 보여주는 것은 또한 X가 고전적으로(구성적으로) 공식적으로 계산 가능하다는 것을 의미하지만, 이것은 효과적인 계산 가능성을 반영하지 않습니다.즉, 순서대로 모든 총 함수를 나열하는 알고리즘이 코드화될 수 없다는 사실은 집합 및 함수 존재에 관한 고전적 공리에 의해 포착되지 않습니다.우리는 이론의 공리에 따라 부분 가산성이 가산성보다 증명 가능성이 더 높을 수 있다는 것을 알고 있습니다.

제외중과의관계

구성 논리학과 집합론에서 무한 집합 사이의 함수의 존재는 결정 가능성과 가능한 유효성의 문제와 연결됩니다.거기서 하위 가산성 속성은 가산성에서 분리되므로 중복되는 개념이 아닙니다.자연수의 색인 $I$ 집합 $I$ $I$ 은(는) 예를 들어 분리 공리 스키마와 같은 집합 이론 공리를 통해 부분 집합으로 존재하는 것으로 가정될 수 있습니다.그러면 $I\subseteq {\mathbb {N} }$ ⊆ $I\subseteq {\mathbb {N} }$ 의 $I\subseteq {\mathbb {N} }$ 정의에 $따라$ {\ $displaystyle I\subseteq {\mathbb$ {N $I\subseteq {\mathbb {N} }$

\forall (i\in I).(i\in {\mathbb {N}}).

하지만 이 세트는 여전히 탈부착에 실패할 수 있습니다.

\forall(n\in {\mathbb {N}})입니다.{\big(}(n\in I)\lor \neg(n\in I){\big}

그것을 공리로 가정하지 않고서는 증명할 수 없을 것입니다.이러한 이유로 카운트

{\mathbb {N} }

N

{\

을(를) 인덱싱 세트

I

I

에

{\mathbb {N} }

매핑하지 못하면 하위

X

카운트 수

집합

X

X

을(를) 효과적으로 카운트하지 못할 수 있습니다

I

셀 수 있다는 것은 셀 수 없다는 것을 의미합니다.마르코프 원리의 적절한 맥락에서, 역은 배제된 중의 법칙과 동등합니다. 즉, 모든 명제 ϕ

\phi

{\

displaystyle \phi }

이(가) ϕ ∨ ¬ ϕ

{\displaystyle \phi \lor \neg

\phi

}

을(를) 보유합니다

\phi \lor \neg \phi

특히, 구성적으로 이 역방향은 일반적으로 성립하지 않습니다.

고전수학에서

고전 논리학의 모든 법칙을 주장하면서, 위에서 $I$ 한 $I$ I {\ $displaystyle$ I $}$ 의 논리합 성질은 실제로 모든 집합에 성립합니다.그러면 비어 있지 않은 $X$ $X$ 에 대해 숫자화할 수 있는 속성 $X$ 여기서 $X$ ${\displaystyle$ $X}$ 는 $X$ N ${\$ displaystyle ${\mathbb {$ N}}), ${\mathbb {N} }$ ${\mathbb {N} }$ $가능$ (N ${\$ displaystyle ${\mathbb {N}}),$ $범위$ 는 X {\ $displaystyle$ X $}$ 입니다 ${\mathbb {N} }$ ),부분 카운트 가능( $X$ ${\displaystyle$ ${\mathbb$ { $N}}}$ 의 부분 집합) $X$ 및 ω $\omega$ -productive( $X$ $X$ 의 부분 집합에서 본질적으로 정의된 카운트 가능성 속성 $X$ 모두 동일하며 집합이 유한하거나 셀 수 없이 무한하다는 것을 표현합니다.

비고전적 주장

배제 중간의 법칙이 없다면, 고전적으로(즉, 비건설적으로) 자연수의 카디널리티를 초과하는 집합의 하위 가산성을 주장하는 것이 일관될 수 있습니다.구성적인 설정에서는 N ↠ $N$ 과 ${\mathbb {N} }$ 같이 전체 ${\mathbb {N} }$ N ${\displaystyle {\$ $mathbb {N}}^{\$ $mathbb {N}}}$ 중 함수 공간 ${\mathbb {N} }^{\mathbb {N} }$ ${\displaystyle {\mathbb {N}}^{\mathbb$ {N $}}^{\mathbb {N$ 에 대한 가산성 주장이 반증될 수 있습니다. $I\subseteq {\mathbb {N} }$ 하위 카운트 가능성 $I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ ↠ ${\mathbb {N} }^{\mathbb {N} }$ ${\$ $displaystyle I\twoheadrightarrow {\mathbb {N}}^{\mathbb {N$ $}}}$ 의 $I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ ${\$ $displaystyle$ ${\mathbb {N} }^{\mathbb {N} }$ I ${\$ $mathbb {N}^{\mathbb {N}}}$ 을(를) $집합$ I {\ $displaystyle$ I $\subseteq$ {\mathbb ${N$ $}}$ 에서 효과적으로 분리할 수 없는 $I\subseteq {\mathbb {N} }$ ${\$ displaystyle I $}\mathbb {N}}$ 을(를) 허용할 수 있습니다.

${\mathbb {N} }^{\mathbb {N} }$ ${\$ 은 ${\mathbb {N} }^{\mathbb {N} }$ 셀 수 없고 고전적으로 셀 수 없는 것이기 때문에 큰 함수 공간을 가진 고전적인 프레임워크는 러시아 구성주의의 공리인 구성 교회의 논문과 양립할 수 없습니다.

하위 카운트와 ω 생산성은 상호 배타적입니다.

${\mathbb {N} }$ $X$ $X$ 을(를 $W\subset X$ $\omega$ ⊂ {\ $displaystyle$ W $\subset$ X $}$ 중 $W\subset X$ 가 $N$ {\ $displaystyle$ {N $}}$ 의 일부 부분 함수의 범위일 ${\mathbb {N} }$ 때마다 해당 범위의 여집합에 남아 있는 $d\in X\setminus W$ 와 ∖ X ∈ $d\in X\setminus W$ W {\ $displaystyle d\in X\setminus$ W $}$ 가 항상 존재한다면 집합 X를 ω {\ $displaystyle \omega}$ 라고 합니다.

일부 $X$ $X$ 에 대한 돌출이 있는 경우 $X$ 설명된 대로 해당 보완은 빈 집합 $X\setminus X$ ∖ X $X\setminus X$ 와 같으므로 $X\setminus X$ 하위 카운트 가능 집합은 ω $\omega$ - 생산적이지 않습니다.위에서 정의한 바와 같이, ω $\omega$ {\ $displaystyle \omega}$ -productive는 임의 부분 $W$ 의 범위W {\ $displaystyle$ W $}$ 를 함수 범위에 $d\in X$ $d\in X$ 특정 값 $d\in X$ ∈ $d\in X$ X {\ $displaystyle$ d\ $in X}$ 와 연관시키며, $d\notin W$ 는 $d\notin W$ ${\displaystyle d\notin$ W $}$ 을 ∉합니다 $d\notin W$ 이러한 방식으로,ω ${\displaystyle$ \ $omega$ }인 $\omega$ 집합 X ${\displaystyle$ X $}$ - 생산적인 것은 그것의 모든 요소를 생성하는 것이 얼마나 어려운지를 말해줍니다.이들은 단일 함수를 사용하여 자연적으로 생성할 수 없습니다.ω ${\displaystyle$ \ $omega}$ - 생산성 속성은 하위 카운트에 방해가 됩니다.이것은 또한 셀 수 없음을 의미하기 때문에, 대각선 논쟁은 종종 70년대 후반부터 명백하게 이 개념을 포함합니다.

계산 가능한 열거 가능 부분 집합 $W$ $W$ 만을 고려하여 $X$ $X$ $X$ 의 계산 가능한 열거 가능성을 불가능하게 설정할 수도 있고, 모든 $W$ $d$ 되는 $d$ 의 $d$ 집합을 소위 생산 함수라고 하는 총 재귀적 이미지로 요구할 수도 있습니다.

부분 함수들이 쌍들의 집합으로 모델링되는 집합론에서, ${\mathbb {N} }\rightharpoonup X$ N은 $\cup _{I\subseteq {\mathbb {N} }}X^{I}$ ∪ $\cup _{I\subseteq {\mathbb {N} }}X^{I}$ ⊆로 ${\mathbb {N} }\rightharpoonup X$ X {\ $displaystyle$ ${\mathbb {N} }\rightharpoonup X$ {\ $mathbb$ {N $}}\rightarpoonup$ X $}$ 를 ⇀ N $\cup _{I\subseteq {\mathbb {N} }}X^{I}$ I $\cup _{I\subseteq {\mathbb {N}}}X^{$ $I}}$ 은(는) ${\mathbb {N} }$ 로서 $X$ {\ $displaystyle X}$ 의 $W$ 집합 W{\ $displaystyle W}$ 만을 갖는 N {\ $displaystyle {N}}$ 의 모든 부분 함수를 정확하게 보유합니다. $X$ $ω$ $\omega$ -생산 집합 X {\ $displaystyle$ X $}$ 의 경우 $찾을$ 수 $X$ .

\forall(w\in)({\mathbb {N}}\rightharpoon up X)입니다.\존재합니다 (d\in X).\neg \exists (n\in {\mathbb {N}}).w(n)=d.

구성적으로 읽으십시오. 이것은 $w$ 의 모든 부분 함수를 해당 함수 범위에 있지 않은 $d$ 요소 $및$ {\ $displaystyle d}$ 과 $w$ (와) 연결합니다.이 속성은 ω $\omega$ - 생산적 집합 $X$ $X$ 과(와) 모든 주관적(일부일 수 있음) 함수의 호환성을 강조합니다.아래는 하위 가산성 가정 연구에 적용됩니다.

이론을 정합니다.

자연의 부분집합에 대한 칸토리아적 주장

참조 이론으로서, 우리는 대체, 경계 분리, 강한 인피니티를 갖는 구성 집합 이론 CZF를 살펴보는데, 이 이론은 멱집합의 존재에 대해 불가지론적이지만, $X,$ Y $X,Y$ 도 집합일 $X,Y$ 때, 임의의 함수 $Y^{X}$ Y $Y^{X}$ ${\$ 가 집합이라고 $Y^{X}$ 주장하는 공리를 포함합니다.이 이론에서는 모든 집합이 하위 셀 수 있다고 주장하는 것도 일관성이 있습니다.다양한 추가 공리의 호환성에 대해서는 이 절에서 무한히 많은 수 $I\subseteq {\mathbb {N} }$ ⊆ $I\subseteq {\mathbb {N} }$ $I\subseteq {\mathbb {N}}$ 에 대한 가능한 사영을 통해 논의합니다 $I\subseteq {\mathbb {N} }$ 여기서 ${\mathbb {N} }$ ${\mathbb {N}$ 은 표준 자연수의 모형을 나타냅니다.

함수 $g\colon X\to Y$ $g\colon X\to Y$ → Y ${\displaystyle g\$ colon $X\to Y}$ 의 경우 $g\colon X\to Y$ 도메인의 모든 값 $x\in X$ ∈ $x\in X$ $x\in X$ 에 대해 고유한 반환 값이 존재합니다.

\exists!(y\in Y).g(x)=y,

그리고 부분집합의 경우, ${\mathbb {N} }$ 의 부분집합 ${\$ 에 대하여 사영이 여전히 총합입니다 ${\mathbb {N} }$ 건설적으로, 그러한 실존적 주장은 고전적인 것보다 더 적을 것입니다.

아래에서 논의되는 - 파워 클래스 대 함수 공간 - 상황은 서로 다릅니다: 술어를 정의하는 일반적인 하위 클래스와 그 진리값(반드시 참과 거짓만 있는 것은 아님)과는 반대로,(프로그래밍 항에서 종료되는) 함수는 모든 하위 도메인( $X$ $X$ 의 하위 집합)에 대한 데이터에 대한 접근 가능한 정보를 만듭니다. $X$ 부분 집합의 특징적인 함수인 함수는 반환 값을 통해 부분 집합 멤버 자격을 결정합니다.일반적으로 정의된 집합의 멤버쉽이 반드시 결정될 필요는 없으므로, (총) 함수 $X\to \{0,1\}$ → $X\to \{0,1\}$ $X\to \{0,1\}$ } ${\displaystyle X\to$ \{ $0,$ 1 $\}$ 는 X $X$ 의 모든 부분 집합과 자동으로 투영되지 않습니다 $X$ 따라서 구성적으로 부분 집합은 특성 함수보다 정교한 개념입니다.사실, CZF 위의 일부 비고전적 공리의 맥락에서, 심지어 모든 $\{0\}$ { $\{0\}$ {\ $displaystyle$ $\{$ $\}$ 의 ${\mathcal {P}}\{0\}$ 클래스 P ${\mathcal {P}}\{0\}$ ${\$ $mathcal$ { $P}\{0\}$ 가 적절한 클래스인 것으로 $\{0\}$ 나타납니다 $.$

전원 클래스로

아래에서, 부정 도입 법칙의 특수한 경우 $(P\to \neg P)\to \neg P$ → ¬ $(P\to \neg P)\to \neg P$ ) $(P\to \neg P)\to \neg P$ → ¬ $(P\to \neg P)\to \neg P$ ${\displaystyle$ $(P\to \neg$ P $)\$ $to$ \ $neg P}$ 가 $P\leftrightarrow \neg P$ 된다는 사실이 사용됩니다 $.$

단순하게 인수를 위해 ${\mathcal {P}}{\mathbb {N} }$ ${\$ 이(가) 집합이라고 ${\mathcal {P}}{\mathbb {N} }$ 가정합니다.그런 다음 부분집합 $I\subseteq {\mathbb {N} }$ ⊆ $I\subseteq {\mathbb {N} }$ $I\subseteq {\mathbb {N}$ 과 함수 $w\colon I\to {\mathcal {P}}{\mathbb {N} }$ : $w\colon I\to {\mathcal {P}}{\mathbb {N} }$ → P $w\colon I\to {\mathcal {P}}{\mathbb {N} }$ ${\displaystyle w\$ colon $I\to {\mathcal {P}}{\mathbb {N}}$ 를 생각해 보십시오 $w\colon I\to {\mathcal {P}}{\mathbb {N} }$ 또한 거듭제곱 집합에 대한 칸토어의 정리와 같이 다음을 정의하십시오.

d=\{k\in {\mathbb {N}}\mid k\in I\land D(k)\

어디에,

D(k)=\neg(k\in w(k))

w

의 종속성이 정의된

{\mathbb {N} }

{\mathbb {N} }

의 {\

mathbb

{

N}}

개의 하위 클래스이며, 쓰기도

w

가능합니다.

d=\{k\in I\mid \neg (k\in w(k))\

분리를 통해 하위 집합으로 존재합니다.

w(n)=d

w

w(n)=d

=

w(n)=d

{\displaystyle w(n

) =

d}

인

n\in I

의 ∈

n\in I

{\in

I

}

이(가) 존재한다고 가정하면 모순을 의미합니다.

n\ind\,\left right arrow \,\neg (n\ind)

따라서 집합으로서

{\mathcal {P}}{\mathbb {N} }

{\mathcal {P}}{\mathbb {N}

이(가) ω

\omega

- 임의의 주어진 사영에 대해

d

되는

d

을(를) 정의할 수 있다는 점에서 생산적입니다.또한 사영

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }

의

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }

는

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }

↠

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }

N

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N}}

이며, CZF에서 Replacement를 통해

{\mathcal {P}}{\mathbb {N} }

{\mathcal {P}}{\mathbb {N} }

{\mathcal {P}{\mathbb {N}

을(를) 자동으로 집합으로 만들기 때문에 이 함수의 존재는 무조건 불가능합니다.

우리는 모든 집합이 부분 카운트 가능하다고 주장하는 부분 가산성 공리가 멱집합 공리에 의해 암시된 대로 ${\mathcal {P}}{\mathbb {N} }$ ${\mathcal {P}}{\mathbb {N} }$ 인 ${\mathcal {P}}{\mathbb {N} }$ {\ $displaystyle$ {\ $mathcal$ {P $}}{\mathbb$ { $N}}}$ 와 양립할 수 없다고 결론짓습니다.

위의 증명에 따르면 $I$ $I$ 을(를) ${\mathcal {P}}I$ ${\mathcal {P$ 에만 $I$ 매핑할 수 없음이 명백합니다. $저$ 도 ${\mathcal {P}}I$ 마찬가지입니다 $.$ 경계 분리는 실제로 집합 $X$ $X$ 가 $X$ ${\mathcal {P}}X$ ${\mathcal {P}$ 에 매핑되지 않음을 의미합니다 ${\mathcal {P}}X$

관련하여 임의의 함수 $h\colon {\mathcal {P}}Y\to Y$ 에 $h\colon {\mathcal {P}}Y\to Y$ 대하여 : $h\colon {\mathcal {P}}Y\to Y$ → $h\colon {\mathcal {P}}Y\to Y$ Y {\ $displaystyle$ h $\$ colon $h\colon {\mathcal {P}}Y\to Y$ {\ $mathcal$ { $P}$ $범위$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ { $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $∈$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $∣ ∃$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ ( $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $∈$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ 의 부분 집합을 사용한 유사한 분석인 $h\colon {\mathcal {P}}Y\to Y$ Y $\to$ Y $}.$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $=$ h $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ ) $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $∧$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $∉$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ $\{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}$ ${\displaystyle \{y\in Y\mid \$ $exists$ ( $S\in {\mathcal {P}Y).$ $y=h(S)\landy\notin S\}$ 는 $h$ $h$ 이(가) 주입이 될 수 없음을 나타냅니다.기능 공간의 경우 상황이 더 복잡합니다.^[3]

파워셋이나 그 등가물이 없는 고전적인 ZFC에서는 집합인 실수의 모든 하위 클래스가 하위 셀 수 있다는 것도 일관성이 있습니다.그런 맥락에서, 이것은 모든 실수 집합이 셀 수 있다는 문장으로 해석됩니다.^[4]물론 이 이론에는 함수 공간 ${\mathbb {N} }^{\mathbb {N} }$ ${\mathbb {N} }^{\mathbb {N} }$ ${\$ 이(가 ${\mathbb {N} }^{\mathbb {N} }$ 없습니다.

함수 공간으로

함수 공간의 정의에 따라 집합 ${\mathbb {N} }\times {\mathbb {N} }$ ${\$ $mathbb$ ${N}}^{\mathbb$ { $N$ $}}}$ 는 집합 N × N {\displaystyle ${\$ mathbb ${$ N}}\times ${\$ mathbb ${N}}\$ times {\mathbb {N $}}$ 의 부분 집합을 보유합니다 ${\mathbb {N} }^{\mathbb {N} }$ ${\mathbb {N} }\times {\mathbb {N} }$ .모든 집합의 허용된 하위 카운트 가능성을 주장하면 특히 ${\mathbb {N} }^{\mathbb {N} }$ ${\$ 이(가) 하위 카운트 가능 집합으로 바뀝니다 ${\mathbb {N} }^{\mathbb {N} }$ .

따라서 여기서는 $f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ ↠ $f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ $f\colon I\twoheadrightarrow {\mathbb {N}}^{\mathbb {N}$ 와 ${\mathbb {N} }\times {\mathbb {N} }$ × N {\ $displaystyle$ {\ $mathbb {N}}\times {\mathbb {N}}}$ 로 구분된 ${\mathbb {N} }\times {\mathbb {N} }$ $f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ 을 고려합니다.

{\Big \{}\mathbb {N}}\times {\mathbb {N}}\mid {\big (}n\in I\land D(n,y){\big )}\lor {\big (}\neg (n\in I)\land y=1{\big )}{\Big \}

사선화 술어를 다음과 같이 정의합니다.

D(n,y)={\big(})\neg(f(n)(n)\geq 1)\land y=1{\big}\lor {\big(}\neg(f(n)=0)\land y=0{\big}

부정 없이도 우리가 표현할 수 있는 것은

D(n,y)={\big(}f(n)(n)=0\land y=1{\big}}\or {\big(}f(n)\geq 1\land y=0{\big}

이 집합은 n

{\

displaystyle

{\mathbb {N} ^{\mathbb {N}}}

의 함수로

{\mathbb {N} }^{\mathbb {N} }

특정

n

n

{\

displaystyle

n}

에 대해

y=0

= 0

{\displaystyle

y =

0}

값을 취하도록 설계되었습니다

n

그리고 그것은 사영으로서

f

f

의 존재가 실제로 모순된다는 것을 증명하는 데 고전적으로 사용될 수 있습니다.그러나 건설적으로

n\in I

n\in I

이 실제로 함수 할당을 정의하도록 정의에

n\in I

있는

명제

n ∈ I {\

displaystyle

n\

in I}

이(가) 결정 가능하지 않다면, 우리는 이 집합이 함수 공간의 구성원임을 증명할 수 없습니다.그래서 우리는 고전적인 결론을 내릴 수 없습니다.

${\mathbb {N} }^{\mathbb {N} }$ 방식으로 ${\mathbb {N} }^{\mathbb {N} }$ ${\$ 의 하위 가산성이 허용되며 ${\mathbb {N} }^{\mathbb {N} }$ 실제로 이론의 모델이 존재합니다.그럼에도 불구하고, CZF의 경우에도, 도메인 ${\mathbb {N} }$ 이 ${\displaystyle$ ${\mathbb$ { $N$ $}}$ 인 ${\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ 완전한 ${\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ N ↠ ${\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ ${\displaystyle$ {\ $mathbb {N}}\displaystyle {\$ $mathbb {N$ $}}^{\mathbb {N$ $}}}$ 의 존재는 실제로 모순됩니다 ${\mathbb {N} }$ $I={\mathbb {N} }$ = $I={\mathbb {N} }$ ${\displaystyle$ I = {\ $mathbb {N}}}$ 의 판별 가능한 구성원 자격은 집합도 셀 수 없게 만듭니다. 즉, 셀 수 없게 만듭니다.

이러한 관측치 외에도, 영이 아닌 임의의 $a$ ${\displaystyle a$ $i\mapsto f(i)(i)+a$ 에 대해 $a$ $I\to {\mathbb {N} }$ → $f$ 의 ${\displaystyle I\$ $to$ ${\displaystyle$ f $}($ $i)(i)+a}$ 함수의 {\ $displaystyle$ I $\$ $to$ {\ $mathbb {N}}$ 을(를 $)$ 유사한 모순 인수로 ${\mathbb {N} }$ 의 모든 ${\mathbb {N}$ 로 확장할 수 없습니다. ${\mathbb {N} }\to {\mathbb {N} }$ 는 ${\mathbb {N} }\to {\mathbb {N} }$ → ${\mathbb {N} }\to {\mathbb {N} }$ N {\ $displaystyle$ {\ $mathbb {N}}\$ to {\ $mathbb$ {N $}}$ 에서 전체 함수로 확장할 수 없는 부분 함수가 존재한다는 것을 의미합니다. ${\mathbb {N} }\to {\mathbb {N} }$ ∈ $n\in {\mathbb {N} }$ $n\in {\mathbb {N}}$ 이 주어졌을 $n\in {\mathbb {N} }$ 때 반드시 $n\in I$ ∈ $n\in I$ $n\in I$ 여부를 결정할 수는 없으며 $n\in I$ 따라서 n ∈ I {\displaystyle n\in I} 여부조차 결정할 수 없습니다. $n$ $n$ 의 잠재적 함수 확장의 e 값이 이전에 특성화된 $돌출부$ $f$ 에 대해 이미 결정되었습니다 $n$ $f$

하위 계수 공리는 모든 집합이 하위 계수임을 주장하며, LEM을 포함하여 $I$ $I$ 을(를) 계산할 $I$ 수 있게 만드는 새로운 공리와 호환되지 않습니다.

모델들

위의 분석은 $\mathbb {R}$ ${\$ 의 코딩의 형식 속성에 영향을 미칩니다 $\mathbb {R}$ 하위 계수 가정에 의한 CZF 이론의 비고전적 확장에 대한 모델이 구성되었습니다.^[6]그러한 비건설적 공리는 선택 원칙으로 볼 수 있지만 이론의 증명 이론적 강점을 크게 증가시키지 않는 경향이 있습니다.

거리 관계가 있는 모든 집합이 부분 계산 가능한 IZF 모형이 있습니다.^[7]
예를 들어, CZF는 마르틴-뢰프 유형 이론 ${\mathsf {ML_{1}V}}$ ${\mathsf {ML_{1}V}}$ V ${\$ 에 모형을 가지고 있습니다 ${\mathsf {ML_{1}V}}$ 고전적으로 셀 수 없는 함수 공간을 가진 이 구성 집합 이론에서, 모든 집합은 부분집합이라고 말하는 부분집합 공리를 주장하는 것은 실제로 일치합니다.논의된 바와 같이, 결과론은 권력의 공리 세트와 모순되며 배제된 중의 법칙과도 모순됩니다.
함수 공간 가정이 없는 이론인 Kripke-Platek 집합 이론의 일부 모델은 모든 집합이 셀 수 있음을 검증합니다.

크기의 개념.

작은 크기의 판단으로서 하위 가산성은 Cantor에 의해 정의된 카디널리티 관계의 표준 수학적 정의와 연관되지 않아야 하며, 작은 카디널리티는 주사의 관점에서 정의되고 카디널리티의 동일성은 편향의 관점에서 정의됩니다.구성적으로 집합 클래스의 사전 $\leq$ 순서 $"≤$ {\ $displaystyle$ \ $leq$ 은 결정할 수 없고 반대칭적입니다.적당히 풍부한 집합 이론의 함수 공간 ${\mathbb {N} }^{\mathbb {N} }$ ${\$ ${\mathbb {N}}^{\mathbb {N}}}($ 또한 $1$ N {\displaystyle $\{$ 1 $\}^{\mathbb {N}}})$ 은 항상 칸토어의 대각 논법에 의해 ${\mathbb {N} }$ {\ $displaystyle {\mathbb {N}}$ 과(와) 유한하거나 사사되지 않음을 알 수 있습니다 ${\mathbb {N} }$ 이것이 셀 수 없다는 것의 의미입니다.그러나 어떤 의미에서 해당 집합의 카디널리티가 자연수의 카디널리티를 초과할 것이라는 주장은 고전적인 크기 개념과 카디널리티에 의한 집합의 유도 순서에 대한 제한에 의존합니다.

계산 가능성 이론에서 고려된 함수 공간의 예에서 볼 수 있듯이, ${\mathbb {N} }$ ${\$ 의 모든 무한 부분 집합이 반드시 ${\mathbb {N} }$ ${\mathbb {N} }$ ${\$ 과(와) 건설적 사영 상태에 있는 것은 아니므로 ${\mathbb {N} }$ 건설적인 맥락에서 셀 수 없는 집합 간의 더 정교한 구별을 위한 공간을 만듭니다.위 절에서 영감을 받아 무한 집합 ${\mathbb {N} }^{\mathbb {N} }$ ${\$ 은 클래스 ${\mathcal {P}}{\mathbb {N} }$ ${\$ 보다 "작은" 것으로 간주될 수 있습니다 ${\mathbb {N} }^{\mathbb {N} }$ ${\mathcal {P}}{\mathbb {N} }$

참고 항목

참고문헌

^ Gert Smolka, 스콜렘스 역설과 구성주의, 강의 노트, Saarland University, 2015년 1월
^ Méhkeri, Daniel (2010), A simple computational interpretation of set theory, arXiv:1005.4380
^ 바우어, A. "N^N에서 N으로의 주사", 2011
^ Gitman, Victora (2011), What is the theory ZFC without power set, arXiv:1110.2430
^ Bell, John L. (2004), "Russell's paradox and diagonalization in a constructive context" (PDF), in Link, Godehard (ed.), One hundred years of Russell's paradox, De Gruyter Series in Logic and its Applications, vol. 6, de Gruyter, Berlin, pp. 221–225, MR 2104745
^ Rathjen, Michael (2006), "Choice principles in constructive and classical set theories" (PDF), in Chatzidakis, Zoé; Koepke, Peter; Pohlers, Wolfram (eds.), Logic Colloquium '02: Joint proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Biannual Meeting of the German Association for Mathematical Logic and the Foundations of Exact Sciences (the Colloquium Logicum) held in Münster, August 3–11, 2002, Lecture Notes in Logic, vol. 27, La Jolla, CA: Association for Symbolic Logic, pp. 299–326, MR 2258712
^ McCarty, Charles (1986), "Subcountability under realizability", Notre Dame Journal of Formal Logic, 27 (2): 210–220, doi:10.1305/ndjfl/1093636613, MR 0842149

[1] Gert Smolka, 스콜렘스 역설과 구성주의, 강의 노트, Saarland University, 2015년 1월

[2] Méhkeri, Daniel (2010), A simple computational interpretation of set theory, arXiv:1005.4380

[3] 바우어, A. "N^N에서 N으로의 주사", 2011

[4] Gitman, Victora (2011), What is the theory ZFC without power set, arXiv:1110.2430

[5] Bell, John L. (2004), "Russell's paradox and diagonalization in a constructive context" (PDF), in Link, Godehard (ed.), One hundred years of Russell's paradox, De Gruyter Series in Logic and its Applications, vol. 6, de Gruyter, Berlin, pp. 221–225, MR 2104745

[6] Rathjen, Michael (2006), "Choice principles in constructive and classical set theories" (PDF), in Chatzidakis, Zoé; Koepke, Peter; Pohlers, Wolfram (eds.), Logic Colloquium '02: Joint proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Biannual Meeting of the German Association for Mathematical Logic and the Foundations of Exact Sciences (the Colloquium Logicum) held in Münster, August 3–11, 2002, Lecture Notes in Logic, vol. 27, La Jolla, CA: Association for Symbolic Logic, pp. 299–326, MR 2258712

[7] McCarty, Charles (1986), "Subcountability under realizability", Notre Dame Journal of Formal Logic, 27 (2): 210–220, doi:10.1305/ndjfl/1093636613, MR 0842149

[3]

[4]

[6]

[7]

Search