Contents

Idea

In first-order logic, the universal quantifier “$\forall$” is the quantifier used to express — given a predicate $P$ with a free variable $t$ of type $T$ — the proposition denoted

which is meant to be true if and only if $P(t)$ holds true for ALL possible elements $t$ of $T$ (all terms of type $T$) — whence the notation “A” (even if upside-down) for this quantifier.

This notion is “dual” (in fact adjoint, see below) to the existential quantifier “$\exists$” which asserts that $P(t)$ holds true for some $t$.

But beware that is quite possible that $P(t)$ may be provable (in a given context) for every term $t$ of type $T$ that can actually be constructed in that context, and yet $\underset{ t \colon T } {\forall} \phi(t)$ cannot be proved: The proper internal definition of universal quantification is as a right adjoint to context extension as brought out by the definition (1) below and expanded on further below.

Definition

We work in a logic in which we are concerned with which propositions entail which other propositions (in a given context); in particular, two propositions which entail each other are considered logically equivalent, denoted by “$\Leftrightarrow$”.

Let

• $\Gamma$ be an arbitrary context,

• $T$ a dependent type in $\Gamma$,

so that

• $\Delta \coloneqq \Gamma, T$ is the context extension of $\Gamma$ by a free variable $t$ of type $T$.

We assume that we have a weakening rule that allows us to interpret any proposition $Q$ in $\Gamma$ as

• $T^\ast Q$ being a proposition in $\Delta$.

Then for

• $P$ a proposition in $\Delta$, which we think of as a predicate in $\Gamma$ with the free variable of type $T$,

its universal quantification is any proposition $\underset{T}{\forall} P$ in $\Gamma$ such that, given any proposition $Q$ in $\Gamma$, we have:

It is then a theorem that universal quantification of $P$, if it exists, is unique. The existence is typically asserted as an axiom in a particular logic, but this may be also be deduced from other principles (as in the topos-theoretic discussion below).

Often one makes the appearance of the free variable in $P$ explicit by thinking of $P$ as a propositional function and writing $P(t)$ instead. Then the rule appears as follows:

In terms of semantics (as for example topos-theoretic semantics; see below), the context extension from $Q$ to $T^\ast Q$ corresponds to pulling back along a product projection $\sigma(T) \times A \to A$, where $\sigma(T)$ is the interpretation of the type $T$, and $A$ is the interpretation of $\Gamma$. In other words, if a statement $Q$ read in context $\Gamma$ is interpreted as a subobject of $A$, then the statement $Q$ read in context $\Delta = \Gamma, t \colon T$ is interpreted by pulling back along the projection, obtaining a subobject of $\sigma(T) \times A$.

As observed by Lawvere, we are not particularly constrained to product projections; we can pull back along any map $f \colon B \to A$. (Often we have a class of display maps and require $f$ to be one of these.) Alternatively, any pullback functor $f^\ast\colon Set/A \to Set/B$ can be construed as pulling back along an object $X = (f \colon B \to A)$, i.e., along the unique map $!\colon X \to 1$ corresponding to an object $X$ in the slice $Set/A$, since we have the identification $Set/B \simeq (Set/A)/X$.

In natural deduction the inference rules for the universal quantifier are given as

Internal universal quantifier in set theory

In set theory, recall that a predicate on a set $A$ in the internal logic of set theory is represented by the preimage $i^*(a)$ of an injection $i:B \hookrightarrow A$. Because $i$ is an injection, each preimage $i^*(a)$ is a subsingleton for all $a \in A$, which represents the internal propositions of the set theory. The internal universal quantifier is represented by the Cartesian product of the family of sets $(i^*(a))_{a \in A}$:

In topos theory / in terms of adjunctions

In terms of the internal logic in some ambient topos $\mathcal{E}$,

• a type $X$ is given by an object $X \in \mathcal{E}$,

• the predicate $\phi$ is a (-1)-truncated object of the over-topos $\mathcal{E}/X$;

• a truth value is a (-1)-truncated object of $\mathcal{E}$ itself.

Universal quantification is essentially the restriction of the direct image right adjoint of a canonical étale geometric morphism $X_\ast$,

where $X^\ast$ is the functor that takes an object $A$ to the product projection $\pi \colon X \times A \to X$, where $X_! = \Sigma_X$ is the dependent sum (i.e., forgetful functor taking $f \colon A \to X$ to $A$) that is left adjoint to $X^\ast$, and where $X_\ast = \Pi_X$ is the dependent product operation that is right adjoint to $X^\ast$.

The dependent product operation restricts to propositions by pre- and postcomposition with the truncation adjunctions

to give universal quantification over the domain (or context) $X$:

Dually, the extra left adjoint $\exists_X$, obtained from the dependent sum $X_!$ by pre- and post-composition with the truncation adjunctions, expresses the existential quantifier. (The situation with the universal quantifier is somewhat simpler than for the existential one, since the dependent product automatically preserves $(-1)$-truncated objects (= subterminal objects), whereas the dependent sum does not.)

The same makes sense, verbatim, also in the (∞,1)-logic of any (∞,1)-topos.

This interpretation of universal quantification as the right adjoint to context extension is also used in the notion of hyperdoctrine.

In dependent type theory

In dependent type theory, the universal quantifier is the propositional truncation of the dependent product type of a family of h-propositions:

The axiom of function extensionality or weak function extensionality implies that the dependent product type of a family of h-propositions is always an h-proposition.

One doesn’t need all dependent product types to define universal quantifiers. The isProp types are definable without all dependent product types, by use of center of contraction, which are also definable without all dependent product types.

Formation rules for the universal quantifier:

Introduction rules for the universal quantifier:

Elimination rules for the universal quantifier:

Computation rules for the universal quantifier:

Uniqueness rules for the universal quantifier:

Closure of universal quantifiers under h-propositions rule:

This means that one could define the type-theoretic internal logic of a Heyting category or Boolean category which are not locally cartesian closed, for strongly predicative mathematics.

Examples

Let $\mathcal{E} =$ Set, let $X = \mathbb{N}$ be the set of natural numbers and let $\phi \coloneqq 2\mathbb{N} \hookrightarrow \mathbb{N}$ be the subset of even natural numbers. This expresses the proposition $\phi(x) \coloneqq IsEven(x)$.

Then the dependent product

is the set of sections of the bundle $2 \mathbb{N} \hookrightarrow \mathbb{N}$. But since over odd numbers the fiber of this bundle is the empty set, there is no possible value of such a section and hence the set of sections is itself the empty set, so the statement “all natural numbers are even” is, indeed, false.

Related concepts

• necessity, example

• existential quantifier

• generalized quantifier

References

The observation that substitution forms an adjoint pair/adjoint triple with the existential/universal quantifiers is due to

• William Lawvere, Adjointness in Foundations, (tac:16), Dialectica 23 (1969), 281-296

• William Lawvere, Quantifiers and sheaves, Actes, Congrès intern, math., 1970. Tome 1, p. 329 à 334 (pdf)

and further developed in

• William Lawvere, Equality in hyperdoctrines and

  comprehension schema as an adjoint functor_, Proceedings of the AMS Symposium on Pure Mathematics XVII (1970), 1-14.

甲状腺炎吃什么药好	a型血的人容易得什么病	六月初三是什么日子	指甲变厚是什么原因	荷字五行属什么
辛属什么五行	血象高是什么意思	aqi是什么	项羽为什么会失败	特斯拉用的是什么电池
什么意思啊	农历7月是什么星座	代销商是什么意思	什么茶降火	oh什么意思
唾液酸苷酶阳性什么意思	日光浴是什么意思	淮山和山药有什么区别	为什么会做梦中梦	莘莘学子什么意思

接触性皮炎用什么药hcv8jop9ns9r.cn	吃东西感觉口苦是什么原因hcv8jop5ns4r.cn	狗和什么属相最配hcv9jop6ns7r.cn	爱什么分明hcv8jop1ns0r.cn	早上起床口苦吃什么药hcv9jop8ns0r.cn
没晨勃说明什么问题hcv8jop8ns8r.cn	心虚吃什么补最快hcv8jop6ns8r.cn	石榴木命是什么意思hcv8jop8ns2r.cn	孕妇肚子疼是什么原因jasonfriends.com	洋葱与什么食物相克hcv8jop1ns1r.cn
汗斑用什么药膏好hcv9jop8ns3r.cn	前列腺肥大是什么症状hcv8jop3ns1r.cn	副主任医师是什么级别hcv8jop3ns5r.cn	csv文件用什么打开hcv8jop2ns7r.cn	为什么小鸟站在电线上不会触电hcv8jop3ns6r.cn
宫寒是什么hcv8jop4ns1r.cn	山狸是什么动物hcv7jop6ns1r.cn	秋字五行属什么hcv8jop6ns5r.cn	什么床垫好hcv8jop9ns1r.cn	孕妇什么时候做ntwzqsfys.com