Warning: my background is mostly in probability and analysis, and not in logic.

When reading or writing a complex proposition, with long chains of "for all... there exists... for all...", I tend to understand the structure of the sentence of quantifiers as a a way to describe how some parameters depend on other parameters. For instance, Poincaré's inequality in $\mathbb{R}^n$ reads:

For all $p \in [1, +\infty]$, for all piecewise Lipschitz bounded open subset $\Omega$, there exists a constant $C>0$ such that, for all $u \in > W^{1, p} (\Omega)$,

$$\|u - \mathbb{E} (u)\|_{\mathbb{L}^p (\Omega)} \leq C \|\nabla u\|_{\mathbb{L}^p (\Omega)}.$$

Let me denote by $A$ the set of piecewise Lipschitz bounded open subsets of $\mathbb{R}^n$. The same proposition can be understood as:

There exists a function $C : [1, +\infty] \times A \to \mathbb{R}_+^*$ such that, for all $p \in [1, +\infty]$, for all piecewise Lipschitz bounded open subset $\Omega$, for all $u \in W^{1, p} (\Omega)$,

$$\|u - \mathbb{E} (u)\|_{\mathbb{L}^p (\Omega)} \leq C_{p, \Omega} \|\nabla u\|_{\mathbb{L}^p (\Omega)}.$$

So, in some sense, the order of the quantifiers encode the parameters some functions are allowed to depend on.

This becomes unwieldy when the sets of parameters the functions can depend on are not well ordered by inclusion. Let $A$, $B$, $C$ and $D$ be four sets and $P$ be a proposition of three free variables in $D$. We could imagine something like:

There exists functions $f : A \times B \to D$, $g : B \times C \to D$, $h : C \times A \to D$ such that, for all $a \in A$, for all $b \in B$, for all $c \in C$,

$$P (f(a, b), g(b, c), h(c, a)).$$

Is there a nice way to encode such a dependence on parameters into the way the proposition is built, as can be done e.g. for Poincaré's inequality?

  • $\begingroup$ @amWhy: The translation in the question looks fine to me (assuming AC, blah blah). Which difference do you see? $\endgroup$ – Henning Makholm Dec 24 '13 at 15:50
  • $\begingroup$ @Henning Perhaps I didn't read it carefully...I immediately saw existence preceding "for all" when originally, existence followed universal quantifiers...without reading the change in the quantified variables. I deleted my comment accordingly. $\endgroup$ – Namaste Dec 24 '13 at 15:53

Nonlinear dependences between parameters can be represented by nonlinear arrangements of quantifiers. There is considerable literature on these so-called Henkin quantifiers or branching quantifiers. You might start by looking at http://en.wikipedia.org/wiki/Branching_quantifier but Google will also give you more sources.

  • $\begingroup$ By the way, this is not propositional logic but first-order logic. In fact, many Henkin quantifiers turn out to go beyond first-order, a little way into second-order logic. $\endgroup$ – Andreas Blass Dec 24 '13 at 15:57
  • $\begingroup$ That's what I was looking for. Thank you! $\endgroup$ – D. Thomine Dec 24 '13 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.