Uniqueness quantification

Short description: Logical quantifier

"Unique (mathematics)" redirects here. For other uses, see Unique (disambiguation).

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Uniqueness quantification" – news · newspapers · books · scholar · JSTOR (November 2024) (Learn how and when to remove this template message)

|

In mathematics and logic, the term "uniqueness" refers to the property of being the one and only object satisfying a certain condition.[1] This sort of quantification is known as uniqueness quantification or unique existential quantification, and is often denoted with the symbols "∃!"[2] or "∃=1". It is defined to mean there exists an object with the given property, and all objects with this property are equal.

For example, the formal statement

∃!n∈ℕ(n−2=4)

may be read as "there is exactly one natural number n such that n−2=4".

## Contents

* 1 Proving uniqueness
* 2 Reduction to ordinary existential and universal quantification
* 3 Generalizations
* 4 See also
* 5 References
* 6 Bibliography

## Proving uniqueness

The most common technique to prove the unique existence of an object is to first prove the existence of the entity with the desired condition, and then to prove that any two such entities (say, a and b) must be equal to each other (i.e. a=b).

For example, to show that the equation x+2=5 has exactly one solution, one would first start by establishing that at least one solution exists, namely 3; the proof of this part is simply the verification that the equation below holds:

3+2=5.

To establish the uniqueness of the solution, one would proceed by assuming that there are two solutions, namely a and b, satisfying x+2=5. That is,

a+2=5 and b+2=5.

Then since equality is a transitive relation,

a+2=b+2.

Subtracting 2 from both sides then yields

a=b,

which completes the proof that 3 is the unique solution of x+2=5.

In general, both existence (there exists at least one object) and uniqueness (there exists at most one object) must be proven, in order to conclude that there exists exactly one object satisfying a said condition.

An alternative way to prove uniqueness is to prove that there exists an object a satisfying the condition, and then to prove that every object satisfying the condition must be equal to a.

## Reduction to ordinary existential and universal quantification

Uniqueness quantification can be expressed in terms of the existential and universal quantifiers of predicate logic, by defining the formula ∃!x(P(x)) to mean[3]

∃x(P(x)∧¬∃y(P(y)∧y≠x)),

which is logically equivalent to

∃x(P(x)∧∀y(P(y)->y=x)).

An equivalent definition that separates the notions of existence and uniqueness into two clauses, at the expense of brevity, is

∃xP(x)∧∀y∀z[(P(y)∧P(z))->y=z].

Another equivalent definition, which has the advantage of brevity, is

∃x∀y(P(y)↔y=x).

## Generalizations

The uniqueness quantification can be generalized into counting quantification (or numerical quantification[4]). This includes both quantification of the form "exactly k objects exist such that ..." as well as "infinitely many objects exist such that ..." and "only finitely many objects exist such that ...". The first of these forms is expressible using ordinary quantifiers, but the latter two cannot be expressed in ordinary first-order logic.[5]

Uniqueness depends on a notion of equality. Loosening this to a coarser equivalence relation yields quantification of uniqueness up to that equivalence (under this framework, regular uniqueness is "uniqueness up to equality"). This is called essentially unique. For example, many concepts in category theory are defined to be unique up to isomorphism.

The exclamation mark ! can be also used as a separate quantification symbol, so (∃!x.P(x))↔((∃x.P(x))∧(!x.P(x))), where (!x.P(x)):=(∀a∀b.P(a)∧P(b)->a=b). For example, it can be safely used in the replacement axiom, instead of ∃!.

## See also

* Essentially unique
* Extension by definition
* One-hot
* Singleton (mathematics)
* Uniqueness theorem

## References

1. ↑ Weisstein, Eric W.. "Uniqueness Theorem" (in en). http://mathworld.wolfram.com/UniquenessTheorem.html.
2. ↑ "2.5 Uniqueness Arguments". https://www.whitman.edu/mathematics/higher_math_online/section02.05.html.
3. ↑ Kleene, Stephen Cole (1967). Mathematical logic. New York: Wiley. pp. 154. ISBN 978-0-471-49033-3. https://archive.org/details/mathematicallogi0000klee/page/154.
4. ↑ Helman, Glen (August 1, 2013). "Numerical quantification". http://persweb.wabash.edu/facstaff/helmang/phi270-1314F/phi270PDF/phi270text/phi270txt8/phi270txt83/phi270txt83(4up).pdf.
5. ↑ This is a consequence of the compactness theorem.

## Bibliography

* Kleene, Stephen (1952). Introduction to Metamathematics. Ishi Press International. p. 199.
* Andrews, Peter B. (2002). An introduction to mathematical logic and type theory to truth through proof (2nd ed.). Dordrecht: Kluwer Acad. Publ.. pp. 233. ISBN 1-4020-0763-9.

* 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/Uniqueness quantification. Read more

|

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