Notes

Description: Kanovei [1979] studies the relationships between \(AC(K)\)  and \(DC(K)\)

Content:

Kanovei [1979] studies the relationships between \(AC(K)\)  and \(DC(K)\) where \(K\) is either in the analytic or projective hierarchy.  We give definitions and summarize some of the results from Kanovei [1979]}.

\(AC(K)\) is:  For any \(P \subseteq\omega\times{}^{\omega} \omega\) with domain \(\omega\), if \(P\in K\), then there is a sequence \(\langle x_{k} : k \in\omega\rangle\) of elements of \({}^{\omega}\omega\) with \(\langle k,x_{k}\rangle\in P\) for all \(k\in\omega\). And

\(DC(K)\) is:  For every \(P \subseteq  {}^{\omega }\omega \times {}^{\omega }\omega \) with domain \({}^{\omega }\omega \), if \(P \in  K\) then for any \(y \in  {}^{\omega }\omega \) there is a sequence \(\langle x_{k} : k\in\omega\rangle \) with \(x_{0} = y\) and for all \(k\in \omega\), \(\langle x_{k},x_{k+1}\rangle \in P\). The sets  in  the analytic hierarchy \((\varSigma ^{1}_{n},\ \varPi ^{1}_{n}\) and \(\varDelta ^{1}_{n}\) for \(n\in\omega)\) and the sets in the projective hierarchy \((\boldsymbol{\Sigma}^{1}_{n},\ \boldsymbol{\Pi}^{1}_{n}\) and \(\boldsymbol{\Delta}^{1}_{n}\) for \(n\in\omega\)) are defined as follows: For purposes of these definitions \({}^{k,\ell }\omega \) is \({}^{k} \omega\times  {}^{\ell }({}^{\omega } \omega )\) and a relation \(R \subseteq {}^{k,\ell }\omega \) is of rank \((k,\ell)\).

  1. \(R\) of rank \((k,\ell)\) is arithmetic if for all \({\bf m} \in {}^k \omega \) and all \(\boldsymbol{\alpha} \in {}^{\ell}({}^{\omega} \omega)\), \(R({\bf m},\boldsymbol{\alpha})\) iff \(Q_{1}x_{1}\ldots Q_{r}x_{r}P({\bf x},{\bf m},\boldsymbol{\alpha },)\) where \(P \subseteq {}^{r+k,\ell }\omega \) is recursive, and each \(Q_{i}\) is either \(\exists \) or \(\forall \).
  2. \(R\) of rank \((k,\ell)\) is analytic if \(R({\bf m}, \boldsymbol{\alpha})\) iff \(Q_{1}\beta_{1}\ldots Q_{r}\beta_{r} P({\bf m},\boldsymbol{\alpha},\beta _{1},\ldots ,\beta _{r})\) where \(P\)  is  of  rank \((k,\ell +r)\)  and  is arithmetic.
  3. (The analytic hierarchy)
    1. \(\varSigma ^{1}_{0} = \varPi ^{1}_{0}\) = the arithmetic relations.
    2. \(\varSigma ^{1}_{r+1} = \{ \exists  \beta P({\bf m},\beta ,\boldsymbol{\alpha}) : P \in  \varSigma ^{1}_{r} \wedge  P\hbox{ has rank }(k,\ell +1) \}\)
    3. \(\varPi ^{1}_{n+1} = \{ \forall  \beta  P({\bf m},\beta ,\boldsymbol{\alpha }) : P \in  \varSigma ^{1}_{r} \wedge P\hbox{ has rank }(k,\ell +1) \}\)
    4. \(\varDelta ^{1}_{r} = \varSigma ^{1}_{r} \cap  \varPi ^{1}_{r}.\)
  4. \(R\) of rank \((k,\ell)\) is recursive in \(\boldsymbol{\beta}\) iff the  characteristic function \(K_{R}({\bf m},\boldsymbol{\alpha})\) of \(R\) is \(G({\bf m},\boldsymbol{\alpha},\boldsymbol{\beta})\) for some partial recursive \(G\).
  5. Assume \(\boldsymbol{\beta}\) has rank \((0,\ell )\) then \(\varSigma ^{1}_{r}[\boldsymbol{\beta }]\) and \(\varPi ^{1}_{r}[\boldsymbol{\beta }]\) are defined by \(R \in  \varSigma ^{1}_{r}[\boldsymbol{\beta}]\) iff \(R({\bf m}, \boldsymbol{\alpha}) \leftrightarrow  S{\bf m}, \boldsymbol{\alpha},\boldsymbol{\beta})\)for some \(S\in\varSigma^{1}_{r}.\) \(\varPi ^{1}_{r}[\boldsymbol{\beta }]\)  is defined similarly.
  6.  (The projective hierarchy)
    1. \(\boldsymbol{\Sigma } ^{1}_{r} = \bigcup  \{ \varSigma ^{1}_{r}[\beta ] : b \in {}^{\omega }\omega  \}\)
    2. \(\boldsymbol{\Pi}^{1}_{r} = \bigcup  \{ \varPi ^{1}_{r}[\beta ] : b \in  {}^{\omega }\omega  \}\)
    3. \(\boldsymbol{\Delta}^{1}_{r} = \boldsymbol{\Sigma}^{1}_{r} \cap \boldsymbol{\Pi}{1}_{r}.\)

In Kanovei [1979] it is shown for any \(n\ge 2\) that, \(AC(\varPi^1_{n+1})\) does not follow, in ZF from \(DC(\boldsymbol\Pi^1_n)\), that \(DC(\boldsymbol\Pi^1_n)\) implies \(AC(\varPi^1_n)\) and that \(AC(\varPi^1_n)\) does not imply \(DC(\boldsymbol\Pi^1_n)\). Kanovei [1979] has further results on \(AC\) and the projective hierarchy.  See forms [0 X], Form 194 and Form 199.

Howard-Rubin number: 61

Type: Definitions and summaries

Back