Universal quantification

Short description: Mathematical use of "for all"

For "for every" in computing, see Foreach loop.

"For all" redirects here. For the Italian political party, see For All (Aosta Valley).

Universal quantificationType| Quantifier

|

Field| Mathematical logic
Statement| ∀xP(x) is true when P(x) is true for all values of x.

In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any", "for all", "for every", or "given an arbitrary element". It expresses that a predicate 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). The universal quantifier is encoded as U+2200 ∀ FOR ALL in Unicode, and as `\forall` in LaTeX and related formula editors.

## 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, ..., and 2 · 100 = 100 + 100, and ..., etc.

This would seem to be an infinite 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, 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 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, one has 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, one has 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, one has 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 ∀ (a turned "A" in a sans-serif font, Unicode U+2200) is used to indicate universal quantification. It was first used in this way by Gerhard Gentzen in 1935, by analogy with Giuseppe Peano's ∃ (turned E) notation for existential quantification and the later use of Peano's notation by Bertrand Russell.[1]

For example, if P(n) is the predicate "2·n > 2 + n" and N is the set of natural numbers, then

∀n∈ℕP(n)

is the (false) statement

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

Similarly, if Q(n) is the predicate "n is composite", then

∀n∈ℕ(Q(n)->P(n))

is the (true) statement

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

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

## Properties

### Negation

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

¬∀xP(x)is equivalent to∃x¬P(x)

where ¬ denotes negation.

For example, if P(x) is the propositional function "x is married", then, for the set X of all living human beings, the universal quantification

> Given any living person x, that person is married

is written

∀x∈XP(x)

This statement is 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).

If the function P(x) is not true for every element of X, then there must be at least one element for which the statement is false. That is, the negation of ∀x∈XP(x) is logically equivalent to "There exists a living person x who is not married", or:

∃x∈X¬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"):

¬ ∃x∈XP(x)≡ ∀x∈X¬P(x)≢ ¬ ∀x∈XP(x)≡ ∃x∈X¬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;[2] that is:

P(x)∧(∃y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)∧Q(y))P(x)∨(∃y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)∨Q(y)),provided that 𝐘≠∅P(x)->(∃y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)->Q(y)),provided that 𝐘≠∅P(x)↚(∃y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)↚Q(y))P(x)∧(∀y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)∧Q(y)),provided that 𝐘≠∅P(x)∨(∀y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)∨Q(y))P(x)->(∀y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)->Q(y))P(x)↚(∀y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)↚Q(y)),provided that 𝐘≠∅

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

P(x)↑(∃y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)↑Q(y))P(x)↓(∃y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)↓Q(y)),provided that 𝐘≠∅P(x)↛(∃y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)↛Q(y)),provided that 𝐘≠∅P(x)<-(∃y∈𝐘Q(y))≡ ∀y∈𝐘(P(x)<-Q(y))P(x)↑(∀y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)↑Q(y)),provided that 𝐘≠∅P(x)↓(∀y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)↓Q(y))P(x)↛(∀y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)↛Q(y))P(x)<-(∀y∈𝐘Q(y))≡ ∃y∈𝐘(P(x)<-Q(y)),provided that 𝐘≠∅

### 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∈𝐗P(x)->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∈𝐗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) is always true, regardless of the formula P(x); see vacuous truth.

## 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)

∀y∀z(P(y)∧∃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.[3]

For a set X, let 𝒫X denote its powerset. For any function f:X->Y between sets X and Y, there is an inverse image functor f*:𝒫Y->𝒫X between powersets, that takes subsets of the codomain of f back to subsets of its domain. The left adjoint of this functor is the existential quantifier ∃f and the right adjoint is the universal quantifier ∀f.

That is, ∃f:𝒫X->𝒫Y is a functor that, for each subset S⊂X, gives the subset ∃fS⊂Y given by

∃fS={y∈Y|∃x∈X. f(x)=y∧x∈S},

those y in the image of S under f. Similarly, the universal quantifier ∀f:𝒫X->𝒫Y is a functor that, for each subset S⊂X, gives the subset ∀fS⊂Y given by

∀fS={y∈Y|∀x∈X. f(x)=y⟹x∈S},

those y whose preimage under f is contained in S.

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 so that 𝒫(1)={T,F} is the two-element set holding the values true and false, a subset S is that subset for which the predicate S(x) holds, and

𝒫(!):𝒫(1)->𝒫(X)T↦XF↦{}
∃!S=∃x.S(x),

which is true if S is not empty, and

∀!S=∀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

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

## References

1. ↑ Miller, Jeff. "Earliest Uses of Symbols of Set Theory and Logic". Earliest Uses of Various Mathematical Symbols. http://jeff560.tripod.com/set.html.
2. ↑ that is, if the variable y does not occur free in the formula P(x) in the equivalences below
3. ↑ 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. http://www.maths.unsw.edu.au/~jim/proofs.html. (ch. 2)

## External links

* v
* t
* e

Common logical symbols

∧ or &

and

¬ or ~

not

implies

implies,
superset

iff

nand

universal
quantification

existential
quantification

tautology

false,
contradiction

entails,
proves

entails,
therefore

therefore

because

|
|
|
|
|
|
|
|
|
|
|
|
|
|

* v
* t
* e

Mathematical logic

General|

* Formal language
* Formation rule
* Formal proof
* Formal semantics
* Well-formed formula
* Set
* Element
* Class
* Classical logic
* Axiom
* Rule of inference
* Relation
* Theorem
* Logical consequence
* Type theory
* Symbol
* Syntax
* Theory

Systems|

* Formal system
* Deductive system
* Axiomatic system
* Hilbert style systems
* Natural deduction
* Sequent calculus

Traditional logic|

* Proposition
* Inference
* Argument
* Validity
* Cogency
* Syllogism
* Square of opposition
* Venn diagram

Propositional calculus
and Boolean logic

* Boolean functions
* Propositional calculus
* Propositional formula
* Logical connectives
* Truth tables
* Many-valued logic

Predicate logic|

* First-order
* Quantifiers
* Predicate
* Second-order
* Monadic predicate calculus

Naive set theory|

* Set
* Empty set
* Element
* Enumeration
* Extensionality
* Finite set
* Infinite set
* Subset
* Power set
* Countable set
* Uncountable set
* Recursive set
* Domain
* Codomain
* Image
* Map
* Function
* Relation
* Ordered pair

Set theory|

* Foundations of mathematics
* Zermelo–Fraenkel set theory
* Axiom of choice
* General set theory
* Kripke–Platek set theory
* Von Neumann–Bernays–Gödel set theory
* Morse–Kelley set theory
* Tarski–Grothendieck set theory

Model theory|

* Model
* Interpretation
* Non-standard model
* Finite model theory
* Truth value
* Validity

Proof theory|

* Formal proof
* Deductive system
* Formal system
* Theorem
* Logical consequence
* Rule of inference
* Syntax

Computability
theory|

* Recursion
* Recursive set
* Recursively enumerable set
* Decision problem
* Church–Turing thesis
* Computable function
* Primitive recursive function

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Universal quantification. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Universal_quantification&oldid=4298115"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template