2

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?

D. Thomine
  • 10,870
  • @amWhy: The translation in the question looks fine to me (assuming AC, blah blah). Which difference do you see? – hmakholm left over Monica Dec 24 '13 at 15:50
  • @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. – amWhy Dec 24 '13 at 15:53

1 Answers1

2

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.

Andreas Blass
  • 71,833