2
$\begingroup$

$\begin{align}x \text { is predicatively} &\text{ definable } \iff \exists x_1,..,x_n \exists \varphi:\\ & \rho(x_1) < \rho(x) ,.., \rho(x_n) < \rho(x) \ \land \\&\forall y \, (y \in x \iff V_{\rho(x)} \models \varphi(y,x_1,..,x_n))\end{align} $

Where $\rho(x)$, the rank of $x$, is defined as the ordinal index of the first stage $V_\alpha$ of which $x$ is a subset.

Now, let $\sf HPD$ be the class of all hereditarily predicatively definable sets.

What is the maximal fragment of $\sf ZFC$ satisfied by $\sf HPD$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Considering that there is no reflective principles between $V_{\rho(x)}$ and $V$, I would imagine that not a lot, even ignoring the restriction on the parameters $\endgroup$
    – Holo
    Commented Feb 14, 2023 at 20:32
  • 4
    $\begingroup$ This is not going to satisfy a whole lot of ZF since only arithmetic reals will belong to HPD yet for any $x\subseteq \omega$, $x\cup \{\omega\}$ will belong to HPD. $\endgroup$
    – Gabe Goldberg
    Commented Feb 14, 2023 at 20:43

1 Answer 1

Reset to default
2
$\begingroup$

HPD satisfy extensionality and regularity trivially.

It satisfy Pairing, as if $x,y\in HPD$ we can explicitly write down the definition of $(x,y)$ using only $x,y$ as parameters (and they have strictly smaller rank).

It satisfy infinity (it has all of the Ordinals and it computes Ordinals correctly).

It has powerset, $V_{\alpha+2}$ calculate $HPD\cap V_{\alpha+1}$ correctly.

It doesn't have $\Delta_0$ separation even when restricted to formulaes without parameters:

Note that $HPD(\omega)$.

Externally we know that $(2^{|\omega|})^{HPD}$ is countable

I claim that $HPD$ also see that, this is because $V_{\omega+2}$ has a canonical well-ordering for $(\mathcal P(\omega))^{HPD}$ of ordertype $\omega$ (it is even without parameters), simply by intertwining Ackermann coding for parameters with Godel encoding for formulaes (and noting that every $HPD$ subset of $\omega$ must be seen from $V_{\omega+1}$), so $HPD\models |\omega|=|\mathcal P(\omega)|$

Like @GabeGoldberg stated, for every $X\subseteq \omega$ we have $X'=X\cup\{\omega\}\in HPD$, but most such $X=\{a\in X'\mid a\ne\omega\}\notin HPD$, and $\omega$ is definable without parameters so we don't have $\Delta_0$-separation w/o parameters.

I'm not quite sure about choice and union, but I would imagine that union fails in a strong sense (at every infinite successor level, note that the union of HPD sets with limit rank are closed under union, but at successor ranks we can use parameters from one rank bellow, which causes a problem)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Does it satisfy second order arithmetic? $\endgroup$
    – Zuhair Al-Johar
    Commented Feb 15, 2023 at 10:52
  • $\begingroup$ @ZuhairAl-Johar what exactly do you mean in this context? $\endgroup$
    – Holo
    Commented Feb 15, 2023 at 11:53
  • $\begingroup$ I mean its consistency strength, can it interpret second order arithmetic or is it weaker? Can it interpret PA? $\endgroup$
    – Zuhair Al-Johar
    Commented Feb 15, 2023 at 13:29
  • 1
    $\begingroup$ @ZuhairAl-Johar $(\omega,+1,<)\in HPD$ and $HPD$ sees that $+1$ is injective, $0$ is not in the image and that $\omega$ is closed under $+1$ and that $<$ is well ordering, so yes (but anything after $Z_2$ pretty much falls flat). But note that we don't know whether $Th(HPD)$ is recursively axiomatible, so consistency strength doesn't mean much for now $\endgroup$
    – Holo
    Commented Feb 15, 2023 at 14:07
  • $\begingroup$ OK! So the maximal fragment of $\sf ZFC$ that $\sf HPD$ can capture (this is recursively axiomatizable) can interpret $\sf Z_2$, but not more. So, according to reverse mathematics, almost all of traditional mathematics can be captured in $\sf HPD$. $\endgroup$
    – Zuhair Al-Johar
    Commented Feb 15, 2023 at 14:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .