Universal quantification

수학적 논리(mathematical logic)에서, 보편적 정량화(universal quantification)는 한정어(quantifier)의 한 유형으로, "임의의 ... 주어지면" 또는 "모두에 대해"로 해석(interpreted)되는 논리적 상수(logical constant)입니다. 그것은 술어(predicate)가 담론의 도메인(domain of discourse)의 모든 각 구성원(member)에 의해 만족(satisfied)될 수 있음을 표현합니다. 다시 말해서, 그것은 도메인의 모든 각 구성원에 대한 속성(property) 또는 관계(relation)의 술어(predication)입니다. 그것은 보편적 정량화의 범위(scope) 내의 술어가 술어 변수(predicate variable)의 모든 각 값(value)의 참임을 주장(asserts)합니다.

그것은 보통 거꾸로 된 A (∀) 논리 연산자(logical operator) 기호(symbol)에 의해, 표시되며, 이것은, 술어 변수와 함께 사용될 때, 보편적 한정어(universal quantifier) (" $\forall x$ ", " $\forall(x)$ ", 또는 때때로 " $(x)$ " 단독으로)라고 불립니다. 보편적 정량화는 속성 또는 관계가 도메인의 적어도 한 구성원에 대해 유지된다는 것만을 주장하는 존재적 정량화(existential quantification) ("...이 존재합니다")와 구별됩니다.

정량화는 일반적으로 정량화 (논리)에 대한 기사에서 다룹니다. 보편적 정량화는 유니코드(Unicode)에서 U+2200 ∀ FOR ALL로 인코딩되고, 레이텍(LaTeX)과 관련 공식 편집기에서 \forall로 인코딩됩니다.

Basics

다임임이 주어진다고 가정합니다:

2·0 = 0 + 0, and 2·1 = 1 + 1, and 2·2 = 2 + 2, etc.

이것은 "and"의 반복 사용때문에 논리곱(logical conjunction)으로 보일 것입니다. 어쨌든, "etc."는 형식적 논리(formal logic)에서 논리곱으로 해석될 수 없습니다. 대신, 그 명제는 다음과 같이 바뀌어야 합니다:

For all natural numbers n, one has 2·n = n + n.

이것은 보편적 정량화를 사용하는 단일 명제입니다.

이 명제는 원래의 명제보다 더 정확하다고 말할 수 있습니다. "etc."는 비공식적으로 자연수(natural number)를 포함하고, 더 이상 다른 것은 포함하지 않지만, 이것은 엄격하게 주어지지 않았습니다. 보편적 정량화에서, 다른 한편으로, 자연수는 명시적으로 언급됩니다.

이 특정 예제는 임의의 자연수가 n에 대해 대체될 수 있고 명제 "2·n = n + n"는 참(true)이기 때문에 참입니다. 대조적으로, 다음 명제는 거짓(false)인데,

For all natural numbers n, one has 2·n > 2 + n

왜냐하면 만약 n이 예를 들어 1로 대체되면, 명제 "2·1 > 2 + 1"는 거짓이기 때문입니다. "2·n > 2 + n"가 대부분의 자연수 n에 대해 참이라는 것은 중요하지 않습니다: 심지어 단 하나의 반대예제(counterexample)가 존재하더라도 보편적 정량화가 거짓임을 입증하기에 충분합니다.

다른 한편으로, 합성수(composite number) n에 대해, 2·n > 2 + n이 참임을 가지는데, 왜냐하면 반대예제의 어떤 것도 합성수가 아니기 때문입니다. 이것은 값 n이 취할 수 있는 것을 지정하는 담론의 도메인(domain of discourse)의 중요성을 나타냅니다.^{[note 1]} 특히, 담론의 도메인 특정 술어를 만족시키는 그것들 대상으로 오직 구성되도록 제한되면, 보편적 정량화에 대해 이것은 논리 조건부(logical conditional)를 요구합니다. 예를 들어, 다음은

For all composite numbers n, one has 2·n > 2 + n

다음과 논리적으로 동등(logically equivalent)합니다:

For all natural numbers n, if n is composite, then 2·n > 2 + n.

여기서 "if ... then" 구성은 논리 조건부를 나타냅니다.

Notation

기호 논리(symbolic logic)에서, 보편적 정량화 기호 $\forall$ (산-세리프 폰트에서 거꾸로된 "A", 유니코드 U+2200)는 보편적 정량화를 나타내기 위해 사용됩니다. 그것은 1935년에 게르하르트 겐첸(Gerhard Gentzen)에 의해 존재적 정량화(existential quantification)에 대해 주세페 페아노(Giuseppe Peano) $\exists$ (거꾸로 된 E) 표기법과 나중에 버트런드 러셀(Bertrand Russell)에 의해 페아노 표기법의 사용과 아날로그에 의해 처음 사용되었습니다.^[1]

예를 들어, 만약 P(n)가 술어 "2·n > 2 + n"가 있고 N이 자연수의 집합(set)이면, 다음은

\forall n\!\in \!\mathbb {N} \;P(n)

다음 (거짓) 명제입니다:

"for all natural numbers n, one has 2·n > 2 + n".

유사하게, 만약 Q(n)가 술어 "n is composite"이면, 다음은

\forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}

다음 (참) 명제입니다:

"for all natural numbers n, if n is composite, then 2·n > 2 + n".

수량화에 대해 표기법에서 여러 변형 (모든 형식에 적용됨)은 한정어(Quantifier) 기사에서 볼 수 있습니다.

Properties

Negation

보편적 정량화 함수의 부정은 보편적 한정어를 존재적 한정어(existential quantifier)로 변경하고 정량화된 공식을 부정함으로써 얻습니다. 즉,

\lnot \forall x\;P(x)\quad {\text{is equivalent to}}\quad \exists x\;\lnot P(x)

여기서 $\lnot$ 는 부정(negation)을 나타냅니다.

예를 들어, 만약 $P (x)$ 가 전제적 함수(propositional function) " $x$ is married"이면, 모든 살아있는 사람의 집합(set)에 대해, 다음 보편적 정량화는

Given any living person $x$ , that person is married

다음으로 쓰입니다:

\forall x\in X\,P(x)

이 명제는 거짓입니다. 진실되게, 다음임을 말합니다:

It is not the case that, given any living person $x$ , that person is married

또는, 기호적으로:

\lnot \ \forall x\in X\,P(x)

.

만약 함수 $P (x)$ 가 $X$ 의 모든 각 원소에 대해 참이 아니면, 그 명제가 거짓인 적어도 하나의 원소가 있어야 합니다. 즉, $\forall x\in X\,P(x)$ 의 부정이 "There exists a living person $x$ who is not married", 또는 다음과 논리적으로 동등합니다:

\exists x\in X\,\lnot P(x)

"all persons are not married" (즉, "there exists no person who is married")와 "not all persons are married" (즉, "there exists a person who is not married")와 혼동하는 것은 잘못된 것입니다:

\lnot \ \exists x\in X\,P(x)\equiv \ \forall x\in X\,\lnot P(x)\not \equiv \ \lnot \ \forall x\in X\,P(x)\equiv \ \exists x\in X\,\lnot P(x)

Other connectives

보편적 (및 존재적) 한정어는, 다른 피연산자가 영향을 받지 않은 한, 논리적 연결(logical connective) ∧, ∨, →, 및 ↚에 걸쳐 변경없이 이동합니다. 즉:

{\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\land Q(y))\\P(x)\lor (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\to (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\to Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nleftarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y))\\P(x)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\lor (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\lor Q(y))\\P(x)\to (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\to Q(y))\\P(x)\nleftarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nleftarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \end{aligned}}

반대로, 논리적 연결 ↑, ↓, ↛, 및 ←에 대해, 한정어는 뒤집힙니다:

{\begin{aligned}P(x)\uparrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y))\\P(x)\downarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\nrightarrow (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\downarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\downarrow Q(y))\\P(x)\nrightarrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\nrightarrow Q(y))\\P(x)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\\end{aligned}}

Rules of inference

추론의 규칙(rule of inference)은 가설에서 결론에 이르는 논리적 단계를 정당화하는 규칙입니다. 보편적 한정어를 활용하는 몇 가지 추론의 규칙이 있습니다.

보편적 예제화(Universal instantiation)는, 만약 전제적 함수가 보편적인 참으로 알려져 있으면, 그것은 담론의 우주의 임의의 임의적인 원소에 대해 참이어야 한다고 결론을 내립니다. 기호적으로, 이것은 다음과 같이 표현됩니다:

\forall {x}{\in }\mathbf {X} \,P(x)\to P(c)

여기서 c는 담론의 우주의 완전하게 임의적인 원소입니다.

보편적 일반화(Universal generalization)는 전제적 함수가 만약 그것이 담론의 우주의 임의의 임의적인 원소에 대해 참이면 보편적으로 참이어야 한다고 결론을 내립니다. 기호적으로, 임의적인 c에 대해,

P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).

원소 c는 완전하게 임의적이어야 합니다; 그렇지 않으면, 그 논리가 따르지 않습니다: 만약 c가 임의적이지 않고, 대신 담론의 우주의 특정 원소이면, P(c)는 전제적 함수의 존재적 정량화를 오직 의미합니다.

The empty set

관례에 따라, 공식 $\forall {x}{\in }\emptyset \,P(x)$ 는 공식 P(x)에 관계없이 항상 참입니다; 공허한 진리(vacuous truth)를 참조하십시오.

Universal closure

공식 φ의 보편적 클로저(universal closure)는 φ에서 모든 각 자유 변수(free variable)에 대해 보편적 한정어를 추가함으로써 얻어진 자유 변수를 가지지 않는 공식입니다. 예를 들어, 다음의 보편적 클로저는

P(y)\land \exists xQ(x,z)

다음입니다:

\forall y\forall z(P(y)\land \exists xQ(x,z))

.

As adjoint

카테고리 이론(category theory)과 기본 토포스(elementary topoi) 이론에서, 보편적 한정어는 거듭제곱 집합(power set) 사이의 함수자(functor), 집합 사이의 함수의 역 이미지(inverse image) 함수자의 오른쪽 인접(right adjoint)으로 이해될 수 있습니다; 마찬가지로, 존재적 한정어(existential quantifier)는 왼쪽 인접(left adjoint)입니다.^[2]

집합 $X$ 에 대해, ${\mathcal {P}}X$ 를 그것의 거듭제곱집합(powerset)을 나타낸다고 놓습니다. 집합 $X$ 와 $Y$ 사이의 임의의 함수 $f:X\to Y$ 에 대해, f의 코도메인의 부분집합을 그것의 도메인의 부분집합으로 다시 가져오는 거듭제곱집합 사이의 역 이미지(inverse image) 함수자 $f^{*}:{\mathcal {P}}Y\to {\mathcal {P}}X$ 가 있습니다. 이 함수자의 왼쪽 인접은 존재적 한정어 $\exists _{f}$ 이고 오른쪽 인접은 보편적 한정어 $\forall _{f}$ 입니다.

즉, $\exists _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ 는, 각 부분집합 $S\subset X$ 에 대해, $f$ 아래에서 $S$ 의 이미지에서 그들 $y$ 와 다음에 의해 제공된 부분집합 $\exists _{f}S\subset Y$ 을 제공하는 함수자입니다:

\exists _{f}S=\{y\in Y\;|\;\exists x\in X.\ f(x)=y\quad \land \quad x\in S\}

.

유사하게, 보편적 한정어 $\forall _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ 는, 각 부분집합 $S\subset X$ 에 대해, $f$ 아래에서 그것들의 이전-이미지가 $S$ 에 포함되는 그것들 $y$ 와 다음에 의해 제공된 부분집합 $\forall _{f}S\subset Y$ 를 제공하는 함수자입니다:

\forall _{f}S=\{y\in Y\;|\;\forall x\in X.\ f(x)=y\quad \implies \quad x\in S\}

.

한정어의 보다 친숙한 형식은 일차 논리(first-order logic)에서 ${\mathcal {P}}(1)=\{T,F\}$ 가 값 참과 거짓을 보유하는 두-원소 집합이고, 부분집합 S가 술어(predicate) $S(x)$ 가 유지되는 해당 부분집합이고, 다음이 되도록 함수 f를 고유한 함수 $!:X\to 1$ 이도록 취함으로써 얻습니다:

{\begin{array}{rl}{\mathcal {P}}(!)\colon {\mathcal {P}}(1)&\to {\mathcal {P}}(X)\\T&\mapsto X\\F&\mapsto \{\}\end{array}}

\exists _{!}S=\exists x.S(x),

이것은 만약 $S$ 가 빈 것이 아니고, 다음이면 참입니다:

\forall _{!}S=\forall x.S(x),

이것은 만약 $S$ 가 X가 아니면 거짓입니다.

위에 주어진 보편적 및 실존적 한정어는 이전-층 카테고리(presheaf category)로 일반화됩니다.

Notes

^ Further information on using domains of discourse with quantified statements can be found in the Quantification (logic) article.

References

^ Miller, Jeff. "Earliest Uses of Symbols of Set Theory and Logic". Earliest Uses of Various Mathematical Symbols.
^ Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 See page 58

Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
Franklin, J. and Daoud, A. (2011). Proof in Mathematics: An Introduction. Kew Books. ISBN 978-0-646-54509-7.{{cite book}}: CS1 maint: multiple names: authors list (link) (ch. 2)

External links

The dictionary definition of every at Wiktionary

[1] Further information on using domains of discourse with quantified statements can be found in the Quantification (logic) article.

[2] Miller, Jeff. "Earliest Uses of Symbols of Set Theory and Logic". Earliest Uses of Various Mathematical Symbols.

[3] Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 See page 58

[note 1]

[1]

[2]