2
$\begingroup$

Bounded quantifiers in set theory are represented as $(\forall x \in S)$ or $(\exists x \in S)$. But since the modifier "bounded" brings up an association with "bounded variable", I prefer the term "restricted quantifier" used in Kit Fine. Relatively unrestricted quantification where "four broad grounds upon which the intelligibility of quantification over absolutely everything has been questioned".

My view upon the axiomatization of a theory of multiverses is that a multiverse is a multitude of universes (like Grothendieck universes or the von Neumann universe), and restricted quantifiers are needed to quantify the variables running within each universe, while the unrestricted quantifiers are needed to quantify the variables running within this multitude. But the last ones can be presented as quantifiers restricted by the "multitude" which can be treated as a universe (of universes). Thus, to my mind, this area of research must strongly employ restricted quantifiers.

This is a wide area of research, but my questions refer to a more restricted area:

  1. Are there results on axiomatizing with restricted quantifiers only, in concrete set theories - ZF, NGB, NF (New Foundations), NFU (New Foundations with urelements) or other?
  2. Is there any correlation between decidability of a fragment of set theory and restricted quantification?

The question 2 is motivated by the link

http://en.wikipedia.org/wiki/Decidable_sublanguages_of_set_theory

which refers to a link about a result which sounds to me strange:

http://turing.dipmat.unict.it/~cantone/p40-97/restrQuant.ps.gz

but this last link does not work for me, so that I can check what the author meant.

$\endgroup$
  • 2
    $\begingroup$ What language are you thinking of? ZF is often written in a purely relational language (with no constant symbols), so there won't be any closed formulas in which all quantifiers are bounded. It seems to me you need at least the constant $\omega$. Which function symbols do you want to allow? Power set? Smallest your favorite cardinal above $\alpha$? $\endgroup$ – Goldstern Aug 17 '14 at 21:48
  • $\begingroup$ The tag "set theory" indicates to me that you might be interested in a theory that includes a version of the axiom of infinity. But the references in the wikipedia article seem to deal with computations with hereditarily finite sets only. $\endgroup$ – Goldstern Aug 17 '14 at 21:54
  • 1
    $\begingroup$ Occurrences of variables that are not free are bound rather than bounded, so this doesn’t clash with the standard term “bounded quantifier”. $\endgroup$ – Emil Jeřábek supports Monica Aug 17 '14 at 22:24
  • $\begingroup$ Really, there is no clash of two terms - thanks. But since many authors use the term "restricted quantifier" I would prefer it. $\endgroup$ – Ioachim Drugus Aug 18 '14 at 1:42
  • $\begingroup$ @Goldstern, I am not sure how the constants in the language of a set theory correlate with whether there is an axiomatization with bounded quantifiers only, of the set theory or of a fragment of it - probably, I am missing something. Also, I am not interested in a set theory of hereditarily finite sets (I don't know how you figured out those links are about such sets - those which I access don't mention hereditarily finite sets). But ZF (with infinitary axiom), NBG, or even Generalized Set Theory of Boolos, are good for this question. $\endgroup$ – Ioachim Drugus Aug 18 '14 at 2:06
6
$\begingroup$

There are a few things to say.

First, as Goldstern notes in the comments, there are strictly speaking no sentences in the language of set theory having only bounded quantifiers (a sentence is a well-formed formula having no free variables), since the bound $y$ in the outermost bounded quantifier $\exists x\in y$ in any assertion will itself be a free variable in the assertion. That is, you just can't even form a sentence in the language of set theory at all using only bounded quantifiers, since if there are any quantifiers, then there will be at least one free variable (and if there are no quantifiers, there will also be a free variable). Since an axiomatization of a theory is customarily understood to consist of sentences, we therefore will find no axiomatization purely in the language of set theory consisting of assertions in which all quantifiers are bounded. (This was why he mentioned having constants in the language, which could serve as bounds and thereby enable one to form sentences with only bounded quantifiers.)

Second, it seems to me that the interest in bounded quantifiers is related to an interest in restricting the complexity of the assertions appearing in an axiomatization (of ZF, GB or whatever). But in this case, the answer is that there is no such axiomatization. Specifically, it is an immediate consequence of the Lévy–Montague reflection theorem that ZF proves the consistency of any $\Sigma_n$ fragment of ZFC, and so if ZF is consistent, then any axiomatization of ZF must use formulas of unbounded complexity.

So if the theory is consistent, there can be no axiomatization of ZF or ZFC that consists of sentences having some bounded level of complexity.

$\endgroup$
  • $\begingroup$ I was missing that at least one constant is needed to have other quantifiers restricted. Now, it is clear that the answer to my question in title is "No". The reflection theorem strongly supports the negative answer by the fact that complexity of the ZF or ZFC cannot be restricted, but leaves room for a naive hope to still have the quantifiers bounded iff the interest is different from restricting complexity. My interest is really different as I will shortly explain in my comment to @Goldstern's answer. $\endgroup$ – Ioachim Drugus Aug 19 '14 at 13:03
4
$\begingroup$

One sentence in your questions suggests that you want to have a "restricted quantifier over the variables in one universe". Here is one (rather silly) way to do it.

The following is a theory ZFU which is very closely related to ZF; all axioms of ZFU use bounded quantification only.

The language of ZFU uses equality, the binary relation $\in$, and a constant symbol $U$. For each formula $\varphi$ in the language of ZF let $\varphi^U$ be the formula obtained by bounding all quantifiers with $U$ (i.e., replacing $\forall x$ by $\forall x\in U$, similarly for $\exists$). Let ZFU be the set of all axioms $\varphi^U$, with $\varphi$ an axiom of ZF. (Note that the U-version of the foundation axiom implies $U\notin U$.) For clarity it might be better to also add the requirement that elements of elements of $U$ are again elements of $U$.

The model-theoretic relation between ZF and ZFU is the following:

  • For any model $\mathcal M=(M,E,U)$ of ZFU, let $V_{\mathcal M}:=\{m\in M: (m,U)\in E\}$. Then $(V,E\upharpoonright V)$ is a model of ZF.
  • Conversely, let $(V,e)$ be a model of ZF. Let $U\notin V$, and let $M$ be any superset of $V\cup \{U\}$. Let $E$ be any relation on $M$ satisfying $E\upharpoonright V=e$ and $M=\{x\in V: (x,U)\in E\}$. Then $\mathcal M=(M,E,U)$ is a model of ZFU, and $V$ can be obtained from $\mathcal M$ as above.

This means that in some sense ZFU is a conservative extension of ZF.

$\endgroup$
  • $\begingroup$ This is very similar in spirit to Ackermann Set Theory. $\endgroup$ – François G. Dorais Aug 19 '14 at 1:45
  • $\begingroup$ @FrançoisG.Dorais I must confess that I don't see much similarity between this answer and Ackermann set theory. In particular, important features of Ackermann's class of all sets are that it's not definable unsing only $\in$ and it's a member of various higher classes. Martin's $U$ might well be the only non-set in some model, so it might be definable and might not be a member of anything else. $\endgroup$ – Andreas Blass Aug 19 '14 at 8:18
  • $\begingroup$ Now I see why constants are needed in restricted quantification, and the constant $U$ of ZFU sounds as one of most needed for what I have in mind - this is to develop a set theory with only one binary operation (rather than membership relationship). Boolos called "adjunction" the operation denoted with semicolon here: $(x;\ y) = x \cup \ ${$y$}. In applications to natural languages, I called it "qualification" and read $(x;\ y)$ as "$x$ as qualifier of $y$". Notice, $(x;\ y)= x$ iff $x \in y$. My goal is also to present restricted quantification as qualification by certain constants. $\endgroup$ – Ioachim Drugus Aug 19 '14 at 14:29
  • 1
    $\begingroup$ @IoachimDrugus: if you are interested in working with infinite sets, adjunction won't get you very far. There is a good reason why we need a union axiom, an infinity axiom (in your theory that could be done by a constant) and (usually) a power set axiom (that could be a unary operation). (Btw, you meant $(x;y)=x$ iff $y\in x$, not if $x\in y$.) $\endgroup$ – Goldstern Aug 19 '14 at 20:19
  • 2
    $\begingroup$ This was my 100th answer. Where are the fireworks? $\endgroup$ – Goldstern Aug 19 '14 at 20:20

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.