Universal quantification

From Wikipedia for FEVERv2
(Redirected from Universal quantifier)
Jump to navigation Jump to search

In predicate logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". Universal quantification_sentence_0

It expresses that a propositional function can be satisfied by every member of a domain of discourse. Universal quantification_sentence_1

In other words, it is the predication of a property or relation to every member of the domain. Universal quantification_sentence_2

It asserts that a predicate within the scope of a universal quantifier is true of every value of a predicate variable. Universal quantification_sentence_3

Quantification in general is covered in the article on quantification (logic). Universal quantification_sentence_4

Symbols are encoded U+2200 ∀ FOR ALL (HTML ∀ · ∀, ∀ · as a mathematical symbol). Universal quantification_sentence_5

Basics Universal quantification_section_0

Suppose it is given that Universal quantification_sentence_6

This would seem to be a logical conjunction because of the repeated use of "and". Universal quantification_sentence_7

However, the "etc." cannot be interpreted as a conjunction in formal logic. Universal quantification_sentence_8

Instead, the statement must be rephrased: Universal quantification_sentence_9

This is a single statement using universal quantification. Universal quantification_sentence_10

This statement can be said to be more precise than the original one. Universal quantification_sentence_11

While the "etc." informally includes natural numbers, and nothing more, this was not rigorously given. Universal quantification_sentence_12

In the universal quantification, on the other hand, the natural numbers are mentioned explicitly. Universal quantification_sentence_13

This particular example is true, because any natural number could be substituted for n and the statement "2·n = n + n" would be true. Universal quantification_sentence_14

In contrast, Universal quantification_sentence_15

is false, because if n is substituted with, for instance, 1, the statement "2·1 > 2 + 1" is false. Universal quantification_sentence_16

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. Universal quantification_sentence_17

On the other hand, for all composite numbers n, 2·n > 2 + n is true, because none of the counterexamples are composite numbers. Universal quantification_sentence_18

This indicates the importance of the domain of discourse, which specifies which values n can take. Universal quantification_sentence_19

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. Universal quantification_sentence_20

For example, Universal quantification_sentence_21

is logically equivalent to Universal quantification_sentence_22

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

Notation Universal quantification_section_1

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

is the (false) statement: Universal quantification_sentence_25

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

is the (true) statement: Universal quantification_sentence_27

and since "n is composite" implies that n must already be a natural number, we can shorten this statement to the equivalent: Universal quantification_sentence_28

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

There is a special notation used only for universal quantification, which is given: Universal quantification_sentence_30

The parentheses indicate universal quantification by default. Universal quantification_sentence_31

Properties Universal quantification_section_2

Negation Universal quantification_section_3

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 Universal quantification_sentence_32

is given: Universal quantification_sentence_33

It can be seen that this is irrevocably false. Universal quantification_sentence_34

Truthfully, it is stated that Universal quantification_sentence_35

or, symbolically: Universal quantification_sentence_36

Generally, then, the negation of a propositional function's universal quantification is an existential quantification of that propositional function's negation; symbolically, Universal quantification_sentence_37

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"): Universal quantification_sentence_38

Other connectives Universal quantification_section_4

The universal (and existential) quantifier moves unchanged across the logical connectives , , , and , as long as the other operand is not affected; that is: Universal quantification_sentence_39

Conversely, for the logical connectives , , , and , the quantifiers flip: Universal quantification_sentence_40

Rules of inference Universal quantification_section_5

A rule of inference is a rule justifying a logical step from hypothesis to conclusion. Universal quantification_sentence_41

There are several rules of inference which utilize the universal quantifier. Universal quantification_sentence_42

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. Universal quantification_sentence_43

Symbolically, this is represented as Universal quantification_sentence_44

where c is a completely arbitrary element of the universe of discourse. Universal quantification_sentence_45

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

Symbolically, for an arbitrary c, Universal quantification_sentence_47

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. Universal quantification_sentence_48

The empty set Universal quantification_section_6

Universal closure Universal quantification_section_7

The universal closure of a formula φ is the formula with no free variables obtained by adding a universal quantifier for every free variable in φ. Universal quantification_sentence_49

For example, the universal closure of Universal quantification_sentence_50

is Universal quantification_sentence_51

As adjoint Universal quantification_section_8

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. Universal quantification_sentence_52

which is false if S is not X. Universal quantification_sentence_53

The universal and existential quantifiers given above generalize to the presheaf category. Universal quantification_sentence_54

See also Universal quantification_section_9

Universal quantification_unordered_list_0

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Universal quantification.