Existential quantification

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

"∃" redirects here. Existential quantification_sentence_0

It is not to be confused with Ǝ or . Existential quantification_sentence_1

In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". Existential quantification_sentence_2

It is usually denoted by the logical operator symbol ∃, which, when used together with a predicate variable, is called an existential quantifier ("∃x" or "∃(x)"). Existential quantification_sentence_3

Existential quantification is distinct from universal quantification ("for all"), which asserts that the property or relation holds for all members of the domain. Existential quantification_sentence_4

Some sources use the term existentialization to refer to existential quantification. Existential quantification_sentence_5

Basics Existential quantification_section_0

Consider a formula that states that some natural number multiplied by itself is 25. Existential quantification_sentence_6

Existential quantification_description_list_0

  • 0·0 = 25, or 1·1 = 25, or 2·2 = 25, or 3·3 = 25, and so on.Existential quantification_item_0_0

This would seem to be a logical disjunction because of the repeated use of "or". Existential quantification_sentence_7

However, the "and so on" makes this impossible to integrate and to interpret it as a disjunction in formal logic. Existential quantification_sentence_8

Instead, the statement could be rephrased more formally as Existential quantification_sentence_9

Existential quantification_description_list_1

  • For some natural number n, n·n = 25.Existential quantification_item_1_1

This is a single statement using existential quantification. Existential quantification_sentence_10

This statement is more precise than the original one, since the phrase "and so on" does not necessarily include all natural numbers and exclude everything else. Existential quantification_sentence_11

And since the domain was not stated explicitly, the phrase could not be interpreted formally. Existential quantification_sentence_12

In the quantified statement, however, the natural numbers are mentioned explicitly. Existential quantification_sentence_13

This particular example is true, because 5 is a natural number, and when we substitute 5 for n, we produce "5·5 = 25", which is true. Existential quantification_sentence_14

It does not matter that "n·n = 25" is only true for a single natural number, 5; even the existence of a single solution is enough to prove this existential quantification as being true. Existential quantification_sentence_15

In contrast, "For some even number n, n·n = 25" is false, because there are no even solutions. Existential quantification_sentence_16

The domain of discourse, which specifies the values the variable n is allowed to take, is therefore critical to a statement's trueness or falseness. Existential quantification_sentence_17

Logical conjunctions are used to restrict the domain of discourse to fulfill a given predicate. Existential quantification_sentence_18

For example: Existential quantification_sentence_19

Existential quantification_description_list_2

  • For some positive odd number n, n·n = 25Existential quantification_item_2_2

is logically equivalent to Existential quantification_sentence_20

Existential quantification_description_list_3

  • For some natural number n, n is odd and n·n = 25.Existential quantification_item_3_3

Here, "and" is the logical conjunction. Existential quantification_sentence_21

is the (true) statement Existential quantification_sentence_22

Existential quantification_description_list_4

  • For some natural number n, n·n = 25.Existential quantification_item_4_4

Similarly, if Q(n) is the predicate "n is even", then Existential quantification_sentence_23

is the (false) statement Existential quantification_sentence_24

Existential quantification_description_list_5

  • For some natural number n, n is even and n·n = 25.Existential quantification_item_5_5

In mathematics, the proof of a "some" statement may be achieved either by a constructive proof, which exhibits an object satisfying the "some" statement, or by a nonconstructive proof, which shows that there must be such an object but without exhibiting one. Existential quantification_sentence_25

Properties Existential quantification_section_1

Negation Existential quantification_section_2

For example, if P(x) is the propositional function "x is greater than 0 and less than 1", then, for a domain of discourse X of all natural numbers, the existential quantification "There exists a natural number x which is greater than 0 and less than 1" can be symbolically stated as: Existential quantification_sentence_26

This can be demonstrated to be false. Existential quantification_sentence_27

Truthfully, it must be said, "It is not the case that there is a natural number x that is greater than 0 and less than 1", or, symbolically: Existential quantification_sentence_28

If there is no element of the domain of discourse for which the statement is true, then it must be false for all of those elements. Existential quantification_sentence_29

That is, the negation of Existential quantification_sentence_30

is logically equivalent to "For any natural number x, x is not greater than 0 and less than 1", or: Existential quantification_sentence_31

Generally, then, the negation of a propositional function's existential quantification is a universal quantification of that propositional function's negation; symbolically, Existential quantification_sentence_32

(This is a generalization of De Morgan's laws to predicate logic.) Existential quantification_sentence_33

A common error is stating "all persons are not married" (i.e., "there exists no person who is married"), when "not all persons are married" (i.e., "there exists a person who is not married") is intended: Existential quantification_sentence_34

Negation is also expressible through a statement of "for no", as opposed to "for some": Existential quantification_sentence_35

Unlike the universal quantifier, the existential quantifier distributes over logical disjunctions: Existential quantification_sentence_36

Rules of Inference Existential quantification_section_3

A rule of inference is a rule justifying a logical step from hypothesis to conclusion. Existential quantification_sentence_37

There are several rules of inference which utilize the existential quantifier. Existential quantification_sentence_38

Existential introduction (∃I) concludes that, if the propositional function is known to be true for a particular element of the domain of discourse, then it must be true that there exists an element for which the proposition function is true. Existential quantification_sentence_39

Symbolically, Existential quantification_sentence_40

Existential elimination, when conducted in a Fitch style deduction, proceeds by entering a new sub-derivation while substituting an existentially quantified variable for a subject—which does not appear within any active sub-derivation. Existential quantification_sentence_41

If a conclusion can be reached within this sub-derivation in which the substituted subject does not appear, then one can exit that sub-derivation with that conclusion. Existential quantification_sentence_42

The reasoning behind existential elimination (∃E) is as follows: If it is given that there exists an element for which the proposition function is true, and if a conclusion can be reached by giving that element an arbitrary name, that conclusion is necessarily true, as long as it does not contain the name. Existential quantification_sentence_43

Symbolically, for an arbitrary c and for a proposition Q in which c does not appear: Existential quantification_sentence_44

The empty set Existential quantification_section_4

As adjoint Existential quantification_section_5

Main article: Universal quantification § As adjoint Existential quantification_sentence_45

In category theory and the theory of elementary topoi, the existential quantifier can be understood as the left adjoint of a functor between power sets, the inverse image functor of a function between sets; likewise, the universal quantifier is the right adjoint. Existential quantification_sentence_46

HTML encoding of existential quantifiers Existential quantification_section_6

Symbols are encoded U+2203 ∃ THERE EXISTS (HTML ∃ · ∃, ∃ · as a mathematical symbol) and U+2204 ∄ THERE DOES NOT EXIST (HTML ∄ · ∄, ∄, ∄). Existential quantification_sentence_47

See also Existential quantification_section_7

Existential quantification_unordered_list_6

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