GetWiki
Universal quantification
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
Universal quantification
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{Short description|Mathematical use of "for all"}}- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
factoids | |
---|---|
Basics
Suppose it is given that2·0 = 0 + 0, and 2·1 = 1 + 1, and {{nowrap|1=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, 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 + nis 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 + nis 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.Further information on using domains of discourse with quantified statements can be found in the Quantification (logic) article. 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 + nis logically equivalent toFor 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 forall (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 exists (turned E) notation for existential quantification and the later use of Peano's notation by Bertrand Russell.WEB, Earliest Uses of Symbols of Set Theory and Logic,weblink Earliest Uses of Various Mathematical Symbols, Jeff, Miller, For example, if P(n) is the predicate "2·n > 2 + n" and N is the set of natural numbers, then
forall n!in!mathbb{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
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 {{nowrap|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,
lnot forall x; P(x)quadtext {is equivalent to}quad exists x;lnot P(x)
where lnot denotes negation.For example, if {{math|P(x)}} is the propositional function "{{math|x}} is married", then, for the set {{mvar|X}} of all living human beings, the universal quantificationGiven any living person {{math|x}}, that person is marriedis written
forall x in X, P(x)
This statement is false. Truthfully, it is stated thatIt is not the case that, given any living person {{mvar|x}}, that person is marriedor, symbolically:
lnot forall x in X, P(x).
If the function {{math|P(x)}} is not true for every element of {{mvar|X}}, 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 person {{math|x}} 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) notequiv lnot forall xin X, P(x) equiv exists x in 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:
begin{align}
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 emptysetend{align}Conversely, for the logical connectives â, â, â, and â, the quantifiers flip:
begin{align}
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{align}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
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) 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 forall{x}{in}emptyset , 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) land exists x Q(x,z)
is
forall y forall z ( P(y) land exists x Q(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.Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. {{isbn|0-387-97710-4}} See page 58For a set X, let mathcal{P}X denote its powerset. For any function f:Xto Y between sets X and Y, there is an inverse image functor f^*:mathcal{P}Yto mathcal{P}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 exists_f and the right adjoint is the universal quantifier forall_f.That is, exists_fcolon mathcal{P}Xto 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 ={ yin Y ;|; exists xin X. f(x)=y quadlandquad xin S },
those y in the image of S under f. Similarly, the universal quantifier forall_fcolon mathcal{P}Xto 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 ={ yin Y ;|; forall xin X. f(x)=y quadimpliesquad xin 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 to 1 so that mathcal{P}(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
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 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 the presheaf category.See also
- Existential quantification
- First-order logic
- List of logic symbolsâfor the Unicode symbol â
Notes
References
{{Reflist}}- BOOK, Hinman, P., Fundamentals of Mathematical Logic, A K Peters, 2005, 1-56881-262-0,
- BOOK, James Franklin (philosopher), Franklin, J. and Daoud, A., Proof in Mathematics: An Introduction,weblink Kew Books, 2011, 978-0-646-54509-7, (ch. 2)
External links
- {{Wiktionary-inline|every}}
- content above as imported from Wikipedia
- "Universal quantification" does not exist on GetWiki (yet)
- time: 5:25pm EDT - Wed, May 01 2024
- "Universal quantification" does not exist on GetWiki (yet)
- time: 5:25pm EDT - Wed, May 01 2024
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 23 MAY 2022
The Illusion of Choice
Culture
Culture
GETWIKI 09 JUL 2019
Eastern Philosophy
History of Philosophy
History of Philosophy
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
© 2024 M.R.M. PARROTT | ALL RIGHTS RESERVED