Universal quantification
In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a propositional function can be satisfied by every member of a domain of discourse. In other words, it is the predication of a property or relation to every member of the domain. It asserts that a predicate within the scope of a universal quantifier is true of every value of a predicate variable.
It is usually denoted by the turned A (∀) logical operator symbol, which, when used together with a predicate variable, is called a universal quantifier ("∀x", "∀(x)", or sometimes by "(x)" alone). Universal quantification is distinct from existential 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 on quantification (logic). Symbols are encoded .mw-parser-output .monospaced{font-family:monospace,monospace}
U+2200 ∀ .mw-parser-output .smallcaps{font-variant:small-caps}FOR ALL (HTML ∀ · ∀ · as a mathematical symbol).
Contents
1 Basics
1.1 Notation
2 Properties
2.1 Negation
2.2 Other connectives
2.3 Rules of inference
2.4 The empty set
3 Universal closure
4 As adjoint
5 See also
6 Notes
7 References
8 External links
Basics
Suppose it is given that
2·0 = 0 + 0, and 2·1 = 1 + 1, and 2·2 = 2 + 2, etc.
This would seem to be a logical conjunction because of the repeated use of "and". However, the "etc." cannot be interpreted as a conjunction in formal logic. Instead, the statement must be rephrased:
For all natural numbers n, 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 includes natural 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 is true, because any natural number could be substituted for n and the statement "2·n = n + n" would be true. In contrast,
For all natural numbers n, 2·n > 2 + n
is false, because if n is substituted with, for instance, 1, the statement "2·1 > 2 + 1" is false. It is immaterial that "2·n > 2 + n" is true for most natural numbers n: even the existence of a single counterexample is enough to prove the universal quantification false.
On the other hand,
for all composite numbers n, 2·n > 2 + n
is true, because none of the counterexamples are composite numbers. This indicates the importance of the domain of discourse, which specifies which values n 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 a logical conditional. For example,
For all composite numbers n, 2·n > 2 + n
is logically equivalent to
For all natural numbers n, if n is composite, then 2·n > 2 + n.
Here the "if ... then" construction indicates the logical conditional.
Notation
In symbolic logic, the universal quantifier symbol ∀{displaystyle forall }
For example, if P(n) is the predicate "2·n > 2 + n" and N is the set of natural numbers, then:
- ∀n∈NP(n){displaystyle forall n!in !mathbb {N} ;P(n)}
is the (false) statement:
For all natural numbers n, 2·n > 2 + n.
Similarly, if Q(n) is the predicate "n is composite", then
- ∀n∈N(Q(n)→P(n)){displaystyle forall n!in !mathbb {N} ;{bigl (}Q(n)rightarrow P(n){bigr )}}
is the (true) statement:
For all natural numbers n, if n is composite, then 2·n > 2 + n
and since "n is composite" implies that n must already be a natural number, we can shorten this statement to the equivalent:
- ∀n(Q(n)→P(n)){displaystyle forall n;{bigl (}Q(n)rightarrow P(n){bigr )}}
For all composite numbers n, 2·n > 2 + n.
Several variations in the notation for quantification (which apply to all forms) can be found in the quantification article. There is a special notation used only for universal quantification, which is given:
- (n∈N)P(n){displaystyle (n{in }mathbb {N} ),P(n)}
The parentheses indicate universal quantification by default.
Properties
Negation
Note that a quantified propositional function is a statement; thus, like statements, quantified functions can be negated. The notation most mathematicians and logicians utilize to denote negation is: ¬ {displaystyle lnot }
For example, if P(x) is the propositional function "x is married", then, for a universe of discourse X of all living human beings, the universal quantification
Given any living person x, that person is married
is given:
- ∀x∈XP(x){displaystyle forall {x}{in }mathbf {X} ,P(x)}
It can be seen that this is irrevocably false. Truthfully, it is stated that
It is not the case that, given any living person x, that person is married
or, symbolically:
¬ ∀x∈XP(x){displaystyle lnot forall {x}{in }mathbf {X} ,P(x)}.
If the statement is not true for every element of the Universe of Discourse, then, presuming the universe of discourse is non-empty, there must be at least one element for which the statement is false. That is, the negation of ∀x∈XP(x){displaystyle forall {x}{in }mathbf {X} ,P(x)}
- ∃x∈X¬P(x){displaystyle exists {x}{in }mathbf {X} ,lnot P(x)}
Generally, then, the negation of a propositional function's universal quantification is an existential quantification of that propositional function's negation; symbolically,
- ¬ ∀x∈XP(x)≡ ∃x∈X¬P(x){displaystyle lnot forall {x}{in }mathbf {X} ,P(x)equiv exists {x}{in }mathbf {X} ,lnot P(x)}
It is erroneous to state "all persons are not married" (i.e. "there exists no person who is married") when it is meant that "not all persons are married" (i.e. "there exists a person who is not married"):
- ¬ ∃x∈XP(x)≡ ∀x∈X¬P(x)≢ ¬ ∀x∈XP(x)≡ ∃x∈X¬P(x){displaystyle lnot exists {x}{in }mathbf {X} ,P(x)equiv forall {x}{in }mathbf {X} ,lnot P(x)not equiv lnot forall {x}{in }mathbf {X} ,P(x)equiv exists {x}{in }mathbf {X} ,lnot P(x)}
Other connectives
The universal (and existential) quantifier moves unchanged across the logical connectives ∧, ∨, →, and ↚, as long as the other operand is not affected; that is:
P(x)∧(∃y∈YQ(y))≡ ∃y∈Y(P(x)∧Q(y))P(x)∨(∃y∈YQ(y))≡ ∃y∈Y(P(x)∨Q(y)), provided that Y≠∅P(x)→(∃y∈YQ(y))≡ ∃y∈Y(P(x)→Q(y)), provided that Y≠∅P(x)↚(∃y∈YQ(y))≡ ∃y∈Y(P(x)↚Q(y))P(x)∧(∀y∈YQ(y))≡ ∀y∈Y(P(x)∧Q(y)), provided that Y≠∅P(x)∨(∀y∈YQ(y))≡ ∀y∈Y(P(x)∨Q(y))P(x)→(∀y∈YQ(y))≡ ∀y∈Y(P(x)→Q(y))P(x)↚(∀y∈YQ(y))≡ ∀y∈Y(P(x)↚Q(y)), provided that Y≠∅{displaystyle {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)),~mathrm {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)),~mathrm {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)),~mathrm {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)),~mathrm {provided~that} ~mathbf {Y} neq emptyset end{aligned}}}
Conversely, for the logical connectives ↑, ↓, ↛, and ←, the quantifiers flip:
P(x)↑(∃y∈YQ(y))≡ ∀y∈Y(P(x)↑Q(y))P(x)↓(∃y∈YQ(y))≡ ∀y∈Y(P(x)↓Q(y)), provided that Y≠∅P(x)↛(∃y∈YQ(y))≡ ∀y∈Y(P(x)↛Q(y)), provided that Y≠∅P(x)←(∃y∈YQ(y))≡ ∀y∈Y(P(x)←Q(y))P(x)↑(∀y∈YQ(y))≡ ∃y∈Y(P(x)↑Q(y)), provided that Y≠∅P(x)↓(∀y∈YQ(y))≡ ∃y∈Y(P(x)↓Q(y))P(x)↛(∀y∈YQ(y))≡ ∃y∈Y(P(x)↛Q(y))P(x)←(∀y∈YQ(y))≡ ∃y∈Y(P(x)←Q(y)), provided that Y≠∅{displaystyle {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)),~mathrm {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)),~mathrm {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)),~mathrm {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)),~mathrm {provided~that} ~mathbf {Y} neq emptyset \end{aligned}}}
Rules of inference
A rule 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
- ∀x∈XP(x)→ P(c){displaystyle forall {x}{in }mathbf {X} ,P(x)to P(c)}
where c 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 arbitrary c,
- P(c)→ ∀x∈XP(x).{displaystyle P(c)to forall {x}{in }mathbf {X} ,P(x).}
The element c must be completely arbitrary; else, the logic does not follow: if c 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
By convention, the formula ∀x∈∅P(x){displaystyle forall {x}{in }emptyset ,P(x)}
Universal closure
The universal closure of a formula φ is the formula with no free variables obtained by adding a universal quantifier for every free variable in φ. For example, the universal closure of
- P(y)∧∃xQ(x,z){displaystyle P(y)land exists xQ(x,z)}
is
∀y∀z(P(y)∧∃xQ(x,z)){displaystyle forall yforall z(P(y)land exists xQ(x,z))}.
As adjoint
In category theory and the theory of elementary topoi, the universal quantifier can be understood as the right adjoint of a functor between power sets, the inverse image functor of a function between sets; likewise, the existential quantifier is the left adjoint.[2]
For a set X{displaystyle X}
That is, ∃f:PX→PY{displaystyle exists _{f}colon {mathcal {P}}Xto {mathcal {P}}Y}
∃fS={y∈Y|∃x∈X. f(x)=y∧x∈S}{displaystyle exists _{f}S={yin Y;|;exists xin X. f(x)=yquad land quad xin S}},
those y{displaystyle y}
∀fS={y∈Y|∀x∈X. f(x)=y⟹x∈S}{displaystyle forall _{f}S={yin Y;|;forall xin X. f(x)=yquad implies quad xin S}},
those y{displaystyle y}
The more familiar form of the quantifiers as used in first-order logic is obtained by taking the function f to be the unique function !:X→1{displaystyle !:Xto 1}
- P(!):P(1)→P(X)T↦XF↦{}{displaystyle {begin{array}{rl}{mathcal {P}}(!)colon {mathcal {P}}(1)&to {mathcal {P}}(X)\T&mapsto X\F&mapsto {}end{array}}}
- ∃!S=∃x.S(x),{displaystyle exists _{!}S=exists x.S(x),}
which is true if S{displaystyle S}
- ∀!S=∀x.S(x),{displaystyle forall _{!}S=forall x.S(x),}
which is false if S is not X.
The universal and existential quantifiers given above generalize to the presheaf category.
See also
- Existential quantification
- First-order logic
List of logic symbols—for the Unicode symbol ∀
Notes
^ Further information on using domains of discourse with quantified statements can be found in the Quantification (logic) article.
References
^ The inverted "A" was used in the 19th century by Charles Sanders Peirce as a logical symbol for 'un-American' ("unamerican").
Page 320 in Randall Dipert, "Peirce's deductive logic". In Cheryl Misak, ed. The Cambridge Companion to Peirce. 2004
^ Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. .mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
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.CS1 maint: Multiple names: authors list (link) (ch. 2)
External links
The dictionary definition of every at Wiktionary
The dictionary definition of every at Wiktionary
