Movatterモバイル変換

[0]ホーム

Jump to content

Universal quantification

Edit links

From Wikipedia, the free encyclopedia

Mathematical use of "for all"

For "for every" in computing, seeForeach loop.

Universal quantification
Type	Quantifier
Field	Mathematical logic
Statement	$\forall xP(x)$ is true when $P(x)$ is true for all values of $x {\displaystyle x}$ .
Symbolic statement	$\forall xP(x)$

Inmathematical logic, auniversal quantification is a type ofquantifier, alogical constant which isinterpreted as "given any", "for all", "for every", or "given anarbitrary element". It expresses that apredicate can besatisfied by everymember of adomain of discourse. In other words, it is thepredication of aproperty orrelation to every member of the domain. Itasserts that a predicate within thescope of a universal quantifier is true of everyvalue of apredicate variable.

It is usually denoted by theturned A (∀)logical operator symbol, which, when used together with a predicate variable, is called auniversal quantifier ("∀x", "∀(x)", or sometimes by "(x)" alone). Universal quantification is distinct fromexistential quantification ("there exists"), which only asserts that the property or relation holds for at least one member of the domain.

Quantification in general is covered in the article onquantification (logic). The universal quantifier is encoded asU+2200 ∀FOR ALL inUnicode, and as\forall inLaTeX and related formula editors.

Basics

[edit]

Suppose it is given that

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

This would seem to be an infinitelogical conjunction because of the repeated use of "and". However, the "etc." cannot be interpreted as a conjunction informal logic, Instead, the statement must be rephrased:

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

This is a single statement using universal quantification.

This statement can be said to be more precise than the original one. While the "etc." informally includesnatural numbers, and nothing more, this was not rigorously given. In the universal quantification, on the other hand, the natural numbers are mentioned explicitly.

This particular example istrue, because any natural number could be substituted forn and the statement "2·n =n +n" would be true. In contrast,

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

isfalse, because ifn is substituted with, for instance, 1, the statement "2·1 > 2 + 1" is false. It is immaterial that "2·n > 2 +n" is true formost natural numbersn: even the existence of a singlecounterexample is enough to prove the universal quantification false.

On the other hand,for allcomposite numbersn, one has 2·n > 2 +nis true, because none of the counterexamples are composite numbers. This indicates the importance of thedomain of discourse, which specifies which valuesn can take.^{[note 1]} In particular, note that if the domain of discourse is restricted to consist only of those objects that satisfy a certain predicate, then for universal quantification this requires alogical conditional. For example,

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

islogically equivalent to

For all natural numbersn, ifn is composite, then 2·n > 2 +n.

Here the "if ... then" construction indicates the logical conditional.

Notation

[edit]

Insymbolic logic, the universal quantifier symbol $\forall$ (a turned "A" in asans-serif font, Unicode U+2200) is used to indicate universal quantification. It was first used in this way byGerhard Gentzen in 1935, by analogy withGiuseppe Peano's $\exists$ (turned E) notation forexistential quantification and the later use of Peano's notation byBertrand Russell.^[1]

For example, ifP(n) is the predicate "2·n > 2 +n" andN is theset of natural numbers, then

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

is the (false) statement

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

Similarly, ifQ(n) is the predicate "n is composite", then

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

is the (true) statement

"for all natural numbersn, ifn is composite, then2·n > 2 + n".

Several variations in the notation for quantification (which apply to all forms) can be found in theQuantifier article.

Properties

[edit]

Negation

[edit]

The negation of a universally quantified function is obtained by changing the universal quantifier into anexistential quantifier and negating the quantified formula. That is,

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

where $\lnot$ denotesnegation.

For example, ifP(x) is thepropositional function "x is married", then, for thesetX of all living human beings, the universal quantification

Given any living personx, that person is married

is written

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

This statement is false. Truthfully, it is stated that

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

or, symbolically:

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

If the functionP(x) is not true forevery element ofX, then there must be at least one element for which the statement is false. That is, the negation of $\forall x\in X\,P(x)$ is logically equivalent to "There exists a living personx who is not married", or:

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

It is erroneous to confuse "all persons are not married" (i.e. "there exists no person who is married") with "not all persons are married" (i.e. "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

[edit]

The universal (and existential) quantifier moves unchanged across thelogical connectives ∧,∨,→, and↚, as long as the other operand is not affected;^[2] that is:

{\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}}

Conversely, for the logical connectives↑,↓,↛, and←, the quantifiers flip:

{\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

[edit]

Arule of inference is a rule justifying a logical step from hypothesis to conclusion. There are several rules of inference which utilize the universal quantifier.

Universal instantiation concludes that, if the propositional function is known to be universally true, then it must be true for any arbitrary element of the universe of discourse. Symbolically, this is represented as

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

wherec is a completely arbitrary element of the universe of discourse.

Universal generalization concludes the propositional function must be universally true if it is true for any arbitrary element of the universe of discourse. Symbolically, for an arbitraryc,

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

The element c must be completely arbitrary; else, the logic does not follow: ifc is not arbitrary, and is instead a specific element of the universe of discourse, then P(c) only implies an existential quantification of the propositional function.

The empty set

[edit]

By convention, the formula $\forall {x}{\in }\emptyset \,P(x)$ is always true, regardless of the formulaP(x); seevacuous truth.

Universal closure

[edit]

Theuniversal closure of a formula φ is the formula with nofree variables obtained by adding a universal quantifier for every free variable in φ. For example, the universal closure of

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

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

As adjoint

[edit]

Incategory theory and the theory ofelementary topoi, the universal quantifier can be understood as theright adjoint of afunctor betweenpower sets, theinverse image functor of a function between sets; likewise, theexistential quantifier is theleft adjoint.^[3]

For a set $X {\displaystyle X}$ , let ${\mathcal {P}}X$ denote itspowerset. For any function $f:X\to Y$ between sets $X {\displaystyle X}$ and $Y {\displaystyle Y}$ , there is aninverse image functor $f^{*}:{\mathcal {P}}Y\to {\mathcal {P}}X$ between powersets, that takes subsets of the codomain off back to subsets of its domain. The left adjoint of this functor is the existential quantifier $\exists _{f}$ and the right adjoint is the universal quantifier $\forall _{f}$ .

That is, $\exists _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ is a functor that, for each subset $S\subset X$ , gives the subset $\exists _{f}S\subset Y$ given by

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

those $y {\displaystyle y}$ in the image of $S {\displaystyle S}$ under $f {\displaystyle f}$ . Similarly, the universal quantifier $\forall _{f}\colon {\mathcal {P}}X\to {\mathcal {P}}Y$ is a functor that, for each subset $S\subset X$ , gives the subset $\forall _{f}S\subset Y$ given by

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

those $y {\displaystyle y}$ whose preimage under $f {\displaystyle f}$ is contained in $S {\displaystyle S}$ .

The more familiar form of the quantifiers as used infirst-order logic is obtained by taking the functionf to be the unique function $!:X\to 1$ so that ${\mathcal {P}}(1)=\{T,F\}$ is the two-element set holding the values true and false, a subsetS is that subset for which thepredicate $S(x)$ holds, and

{\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),

which is true if $S {\displaystyle S}$ is not empty, and

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

which is false if S is not X.

The universal and existential quantifiers given above generalize to thepresheaf category.

Notes

[edit]

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

References

[edit]

^Miller, Jeff."Earliest Uses of Symbols of Set Theory and Logic".Earliest Uses of Various Mathematical Symbols.
^that is, if the variable $y {\displaystyle y}$ does not occur free in the formula $P(x)$ in the equivalences below
^Saunders Mac Lane, Ieke Moerdijk, (1992)Sheaves in Geometry and Logic Springer-Verlag.ISBN 0-387-97710-4See 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

[edit]

The dictionary definition ofevery at Wiktionary

Commonlogical symbols

∧ or &

¬ or ~

↔ or ≡

universal
quantification

∃

existential
quantification

General

Theorems (list)
and paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps and cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Set theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive