Projective sets and determinacy
We say that $\Gamma$ is a pointclass if it is a collection of subsets of a Polish space. The lightface and bolface projective hierarchies are hierarchies of pointclasses of some Polish space $X$ defined by repeated applications of projections and complementations from either recursively enumerable or closed sets respectively.
Most results in this article can be found in [1] and [2] unless indicated otherwise.
Contents
Definitions
The following definitions are made by taking $X=\omega^\omega$, the Baire space, i.e. the set of all functions $f:\mathbb{N}\to\mathbb{N}$. We will identify its members with the corresponding real numbers under some fixed bijection between $\mathbb{R}$ and $\omega^\omega$. The definitions presented here can be easily extended to other Polish spaces than the Baire space.
Let $\mathbf{\Sigma}^0_1$ be the pointclass that contains all open subsets of the Polish space $\omega^\omega$. Let $\mathbf{\Pi}^0_1$ be the pointclass containing the complements of the $\mathbf{\Sigma}^0_1$ sets.
We define the boldface projective pointclasses $\mathbf{\Sigma}^1_n$, $\mathbf{\Pi}^1_n$ and $\mathbf{\Delta}^1_n$ the following way:
- $\mathbf{\Sigma}^1_1$ contains all the images of $\mathbf{\Pi}^0_1$ sets by continuous functions; its members are called the analytic sets.
- Now, for all $n$, define $\mathbf{\Pi}^1_n$ to be the set of the complements of the $\mathbf{\Sigma}^1_n$ sets; the members of $\mathbf{\Pi}^1_1$ are called the coanalytic sets.
- For all $n$, define $\mathbf{\Sigma}^1_{n+1}$ to be the set of the images of $\mathbf{\Pi}^1_n$ sets by continuous functions.
- Finally, let $\mathbf{\Delta}^1_n=\mathbf{\Sigma}^1_n\cap\mathbf{\Pi}^1_n$. The members of $\mathbf{\Delta}^1_1$ are the Borel sets.
The relativized lightface projective pointclasses $\Sigma^1_n(a)$, $\Pi^1_n(a)$ and $\Delta^1_n(a)$ (for $a\in\omega^\omega$) are defined similarly except that $\Sigma^1_1(a)$ is defined as the set of all $A\subseteq\omega^\omega$ such that $A=\{x\in\omega^\omega:\exists y\in\omega^\omega$ $\exists n\in\omega$ $R(x\restriction n,y\restriction n,a\restriction n)\}$, that is, $A$ is recursively definable by a formula with only existential quantifiers ranging on members of $\omega^\omega$ or on $\omega$ and whose only parameter is $a$.
The (non-relativized) lightface projective classes, also known as analytical pointclasses, are the special cases $\Sigma^1_n$, $\Pi^1_n$ and $\Delta^1_n$ of relativized lightface projective pointclasses where $a=\empty$. Let $\Sigma^0_1$ be the pointclass of all recursively enumerable sets, i.e. the sets $A$ such there exists a recursive relation $R$ such that $A=\{x\in\omega^\omega:\exists n\in\omega$ $R(x\restriction n)\}$, and $\Pi^0_1$ contain the completements of $\Sigma^0_1$ sets. Then the $\Sigma^1_1$ sets are precisely the projections of $\Pi^0_1$ sets.
Given an arbitrary pointclass $\Gamma$, define $\neg\Gamma$ as the set of the complements of $\Gamma$'s elements, for example $\Pi^1_n(a)=\neg\Sigma^1_n(a)$. Also let $\Delta_\Gamma=\Gamma\cap\neg\Gamma$, for example $\Delta^1_n(a)=\Delta_{\Pi^1_n(a)}=\Delta_{\Sigma^1_n(a)}$.
Properties
Every $\mathbf{\Sigma}^1_n$ set is $\Sigma^1_n(a)$ for some $a\in\omega^\omega$, in fact $\mathbf{\Sigma}^1_n=\bigcup_{a\in\omega^\omega}\Sigma^1_n(a)$. A similar statement holds for $\mathbf{\Pi}^1_n$ sets and $\mathbf{\Delta}^1_n$ sets. This means the boldface projective sets are precisely the set definable using only real and arithmetical quantifiers and real parameters.
The following statements also holds when replacing relativized lightface pointclasses by their boldface counterparts:
- If $A$ and $B$ are $\Sigma^1_n(a)$ relations, then so are $\exists x\in\omega^\omega$ $A$, $A\land B$, $A\lor B$, $\exists n\in\omega$ $A$ and $\forall n\in\omega$ $A$.
- If $A$ and $B$ are $\Pi^1_n(a)$ relations, then so are $\forall x\in\omega^\omega$ $A$, $A\land B$, $A\lor B$, $\exists n\in\omega$ $A$ and $\forall n\in\omega$ $A$.
- If $A$ is a $\Sigma^1_n(a)$ relation then $\neg A$ is a $\Pi^1_n(a)$ relation. If $A$ is $\Pi^1_n(a)$ then $\neg A$ is $\Sigma^1_n(a)$.
- If $A$ is a $\Sigma^1_n(a)$ relation and $B$ is a $\Pi^1_n(a)$ relation, then $A\Rightarrow B$ is a $\Pi^1_n(a)$ relation.
- If $A$ is a $\Pi^1_n(a)$ relation and $B$ is a $\Sigma^1_n(a)$ relation, then $A\Rightarrow B$ is a $\Sigma^1_n(a)$ relation.
- If $A$ and $B$ are $\Delta^1_n(a)$, then so are $\neg A$, $A\land B$, $A\lor B$, $A\Rightarrow B$, $A\Leftrightarrow B$, $\exists n\in\omega$ $A$, $\forall n\in\omega$ $A$.
- $\Delta^1_n(a)\subsetneq\Sigma^1_n(a)\subsetneq\Delta^1_{n+1}(a)$
- $\Delta^1_n(a)\subsetneq\Pi^1_n(a)\subsetneq\Delta^1_{n+1}(a)$
Sierpinski showed that every $\mathbf{\Sigma}^1_2$ set of reals is the union of $\aleph_1$ Borel (=$\mathbf{\Delta}^1_1$) sets. It follows that every $\mathbf{\Sigma}^1_2$ set of reals is either (at most) countable or has the cardinality of the continuum.
Shoenfield’s absoluteness theorem is the statement that every $\Sigma^1_2(a)$ or $\Pi^1_2(a)$ relation is absolute for every inner model of $ZF+DC$ that contains $a$ (as an element). It follows that $\mathbf{\Sigma}^1_2$ and $\mathbf{\Pi}^1_2$ relations are absolute for $L$, and also that every $\Sigma^1_2(a)$ real (by taking $X=\omega$) is in $L[a]$, in particular every $\Sigma^1_2$ (or $\Pi^1_2$) real is constructible. The set of all constructible reals is $\Sigma^1_2$, and so is the canonical well-ordering $<_L$ of $L$. For $U$ a nonprincipal $\kappa$-complete ultrafilter on some measurable cardinal $\kappa$, then the collection of all sets of reals in $L[U]$ is $\Sigma^1_3$, and so is the canonical well-ordering $<_{L[U]}$ of $L[U]$.
If $0^\#$ exists then it is a $\Sigma^1_3$ real and the singleton $\{0^\#\}$ is a $\Pi^1_2$ set of reals. If for every real $a\in\omega^\omega$, the sharp $a^\#$ exists then every $\Sigma^1_3$ set of reals is the union of $\aleph_2$ Borel sets.
Regularity properties
Let $A\subseteq(\omega^\omega)^k$ be a k-dimensional set of reals. We say that $A$ is null if it has outer measure 0. We say that $A$ is nowhere dense if its complement contains an open dense set, and that $A$ is meagre (or of first category) if it is a countable union of nowhere dense set. Finally we say that $A$ is perfect if it has no isolated point.
Then, we define the following regularity properties:
- $A$ is Lebesgue measurable if there exists a Borel set $B$ such that $A\Delta B$ is null.
- $A$ has the Baire property if there exists an open set $B$ such that $A\Delta B$ is meagre.
- $A$ has the perfect set property if it is either countable or has a perfect subset.
Where $A\Delta B=(A\setminus B)\cup(B\setminus A)$ denotes symmetric difference. In $ZFC$ there exists Lebesgue non-measurable sets without the Baire property nor the perfect set property, but it is interesting to see which projective sets have those regularity properties.
In $L$ there is a $\Delta^1_2$ set of reals that is not Lebesgue measurable and has no perfect subset. Also there is a $\Pi^1_1$ set of reals without the perfect set property.
If every $\Sigma^1_3$ set of reals is Lebesgue measurable then $\aleph_1$ is inaccessible in $L$.
If $A$ is a $\Sigma^1_2(a)$ set of reals and contains a real that is not in $L[a]$ then $A$ has the perfect set property. Note that every uncountable set with the perfect set property has the cardinality of the continuum.
The following statements are equivalent:
- For every real $a$, $\aleph_1^{L[a]}$ is countable.
- Every $\mathbf{\Pi}^1_1$ set has the perfect set property.
- Every $\mathbf{\Sigma}^1_2$ set has the perfect set property.
If $E$ is a $\mathbf{\Pi}^1_1$ equivalence relation on $\omega^\omega$ then either $E$ has at most $\aleph_0$ equivalence classes or there exists a perfect set of mutually inequivalent reals. If $E$ is a $\mathbf{\Sigma}^1_1$ equivalence relation on $\omega^\omega$ then either $E$ has at most $\aleph_1$ equivalence classes or there exists a perfect set of mutually inequivalent reals.
Prewellordering, scale and uniformization properties
A norm on a set $A$ is a function $\varphi:A\to Ord$ from $A$ to the ordinals. A prewellordering is a relation $\preceq$ that is like a well-ordering except we do not require it to be reflexive or antisymmetric. If $\preceq$ is a prewellordering then the $a\equiv b\iff(a\preceq b\land b\preceq a)$ is an equivalence relation, and $\preceq$ is a well-ordering of the equivalence classes of $\equiv$. If $\varphi$ is a norm then $a\preceq_\varphi b\iff\varphi(a)\leq\varphi(b)$ is a prewellordering.
A pointclass $\Gamma$ has the prewellordering property if every set $A$ in $\Gamma$ has a $\Gamma$-norm: a norm $\varphi:A\to Ord$, a $\Gamma$ relation $P(x,y)$ and a $\neg\Gamma$ relation $Q(x,y)$ such that for every $y\in A$ and all $x$: $x\in A\land\varphi(x)\leq\varphi(y)\iff P(x,y)\iff Q(x,y)$. The pointclasses $\Sigma^1_2$ and, for all $a\in\omega^\omega$, $\Pi^1_1(a)$ have the prewellordering property.
A scale on $A$ is a sequence of norms $\{\varphi_n:n\in\omega\}$ such that for every sequence of points $\{x_i:i\in\omega\}$, if for every $n$ the sequence $\{\varphi_n(x_i):n\in\omega\}$ is eventually constant with value $\alpha_n$, then $(lim_{i\to\omega}$ $x_i)\in A$ and for every $n$, $\varphi_n(lim_{i\to\omega}$ $x_i)\leq\alpha_n$. A pointclass $\Gamma$ has the scale property if for every set $A$ in $\Gamma$, there exists a $\Gamma$-scale for $A$: a scale $\{\varphi_n:n\in\omega\}$, a $\Gamma$ relation $P(n,x,y)$ and a $\neg\Gamma$ relation $Q(x,y)$ such that for every $n$, every $y\in A$ and all $x$: $x\in A\land\varphi_n(x)\leq\varphi_n(y)\iff P(n,x,y)\iff Q(n,x,y)$. Again, the pointclasses $\Sigma^1_2$ and, for all $a\in\omega^\omega$, $\Pi^1_1(a)$ have the scale property.
A set $A\subseteq\omega^\omega\times\omega^\omega$ is uniformized by a function $F$ if $dom(F)=\{x\in\omega^\omega:\exists y\in\omega^\omega$ $(x,y)\in A\}$ and $(x,F(x))\in A$ for all $x\in dom(F)$. A pointclass $\Gamma$ has the uniformization property if every set in $\Gamma$ can be uniformized by a function in $\Gamma$. The pointclasses $\Sigma^1_2$ and, for all $a\in\omega^\omega$, $\Pi^1_1(a)$ have the uniformization property.
Reduction and separation properties
For any four sets $A$, $B$, $A'$ and $B'$, $(A',B')$ reduces $(A,B)$ if $A'\subseteq A$, $B'\subseteq B$, $A'\cup B'=A\cup B$, but $A'\cap B'=\empty$. Thus $A'$ and $B'$ partition $A\cup B$. A pointclass $\Gamma$ has the reduction property if for every $A$, $B$ in $\Gamma$ there exists $A'$, $B'$ in $\Gamma$ such that $(A',B')$ reduces $(A,B)$. $\Pi^1_1(a)$ has the reduction property for every $a\in\omega^\omega$.
A pointclass $\Gamma$ has the separation property if for any disjoint subsets $A$, $B$ of $(\omega^\omega)^k$ for some $k$, if $A$ and $B$ are in $\Gamma$ then there is a $C$ in $\Delta_\Gamma$ such that $A\subseteq C$ and $B\cap C=\empty$. $\Sigma^1_1(a)$ has the separation property for every $a\in\omega^\omega$.
If $\Gamma$ has the reduction property, then $\neg\Gamma$ has the separation property but not the reduction property. It is impossible for $\Gamma$ to have both the reduction and the separation properties. Every pointclass with the prewellordering property has the reduction property. Thus it is impossible for both a pointclass and its complement to have the prewellordering or scale properties.
Projective determinacy
See also: axiom of determinacy
Determinacy is a kind of regularity property. For every set of reals $A$, the game $G_A$ is the infinite game of perfect information of length $\omega$ where both players constructs a sequence (i.e. a real) by playing elements of $\omega$, one after the other, such that the first player's goal is to have the constructed real be in $A$, and the second player's goal is to have the constructed real be in $A$'s complement. $A$ is determined if the game $G_A$ is determined, i.e. one of the two players have a winning strategy for $G_A$.
Given a pointclass $\Gamma$, $\Gamma$-determinacy is the statement "every $A\in\Gamma$ is determined". $\Gamma$-determinacy and $\neg\Gamma$-determinacy are always equivalent. $\omega^\omega$-determinacy is the axiom of determinacy and is implied false by the axiom of choice. The axiom of projective determinacy ($PD$) is precisely $(\bigcup_{n\in\omega}\mathbf{\Sigma}^1_n)$-determinacy. Given some class $M$ (e.g. $OD$, $L(\mathbb{R})$, ...), $M$-determinacy is an abbreviation for $(M\cap\mathcal{P}(\omega^\omega))$-determinacy. $L(\mathbb{R})$-determinacy notably follows from large cardinal axioms, in particular the existence of infinitely many Woodin cardinals with a measurable above them all.
Martin showed that $ZFC$ alone is sufficient to prove Borel determinacy (i.e. $\mathbf{\Delta}^1_1$-determinacy). However, for every $a\in\omega^\omega$, $\Sigma^1_1(a)$-determinacy is equivalent to "the sharp $a^\#$ exists", thus Borel determinacy is the best result possible in $ZFC$ alone. Analytic (i.e. $\mathbf{\Sigma^1_1}$) determinacy follows from the existence of a measurable cardinal, or even just of a Ramsey cardinal. Stronger forms of projective determinacies requires considerably stronger large cardinal axioms: for every $n$, $\mathbf{\Delta}^1_{n+1}$-determinacy implies the existence of an inner model with $n$ Woodin cardinals.
Note that for every $n$, $\mathbf{\Sigma}^1_n$-determinacy is equivalent to $\mathbf{\Pi}^1_n$-determinacy. Furthertmore, under $DC$ (the axiom of dependent choice) for every $n\in\omega$, $\mathbf{\Delta}^1_{2n}$-determinacy is equivalent to $\mathbf{\Sigma}^1_{2n}$-determinacy ($\mathbf{\Pi}^1_{2n}$-determinacy)
Assume $\mathbf{\Sigma}^1_n$ (or $\mathbf{\Pi}^1_n$) determinacy and that the axiom of choice holds for countable sets of reals (which follows from $DC$). Then every $\mathbf{\Sigma}^1_{n+1}$ set of reals is Lebesgue measurable, has the Baire property and has the perfect set property.
Assume projective determinacy; then the following pointclasses have the reduction, prewellordering, scale and uniformization properties, for every $a\in\omega^\omega$: $\Pi^1_1(a), \Sigma^1_2(a), \Pi^1_3(a), ..., \Pi^1_{2n+1}(a), \Sigma^1_{2n+2}(a), ...$ This is known as the periodicity theorem. On the other hand, if $L[U]$ contains every real for some nonprincipal $\kappa$-complete ultrafilter $U$ on a measurable cardinal $\kappa$, then every $\Sigma^1_n(a)$ has the reduction and prewellordering properties for $n\geq 2$ and every $a\in\omega^\omega$.
Projective ordinals
For every pointclass $\Gamma$, define $\delta_\Gamma$ as the supremum of the length of $\Gamma$ prewellorderings of $\omega^\omega$. We then define the projective ordinals to be $\delta^1_n=\delta_{\mathbf{\Sigma}^1_n}=\delta_{\mathbf{\Pi}^1_n}$. It can be shown without $AD$ that $\delta^1_1=\omega_1$ and that $\delta^1_2\leq\omega_2$. Under $AD$, each projective ordinal is a regular cardinal and the sequence $\{\delta^1_n:n\in\omega\}$ is a strictly increasing sequence of measurable cardinals, also $\delta^1_2=\omega_2$, $\delta^1_3=\omega_{\omega+1}$ and $\delta^1_4=\omega_{\omega+2}$. In general, $\delta^1_{2n+2}\leq(\delta^1_{2n+1})^{+}$. Under $DC$ this becomes an equality, also every $\delta^1_{2n+1}$ is the successor of a cardinal of cofinality $\omega$.
Define $E:\omega\to\omega_1$ by recursion the following way: $E(0)=1$, $E(n+1)=\omega^{E(n)}$ (ordinal exponentiation). Then, under $AD+DC$, one have $\delta^1_{2n+3}=\omega_{E(2n+1)+1}$, also every $\delta^1_{2n+3}$ has the strong partition property $\delta^1_{2n+3}\to(\delta^1_{2n+3})^{\delta^1_{2n+3}}_\alpha$ for every $\alpha<\delta^1_{2n+3}$.
Let's say a set of reals $A$ is $\gamma$-Borel (for a cardinal $\gamma$) if it is in the smallest collection of sets containing all closed sets of $(\omega^\omega)^k$ that is closed under complementations and unions of less than $\gamma$ sets. If $\gamma$ is not a cardinal then $A$ is $\gamma$-Borel if it is $\gamma^{+}$-Borel where $\gamma^{+}$ is the smallest cardinal >$\gamma$. Note that a set is Borel if and only if it is $\aleph_1$-Borel.
Assume $\mathbf{\Delta}^1_{2n}$-determinacy; then a set of reals $A$ is $\mathbf{\Delta}^1_{2n+1}$ if and only if it is $\delta^1_{2n+1}$-Borel. Now, assume $AD+DC$; then a set $A$ is $\mathbf{\Sigma}^1_{2n+2}$ if and only if it is the union of $\delta^1_{2n+1}$-many sets that are $\mathbf{\Delta}^1_{2n+1}$.
Projective determinacy from large cardinals
Woodin showed that $\mathbf{\Pi}^1_{n+1}$-determinacy follows from the existence of $n$ Woodin cardinals with a measurable above them all, and projective determinacy thus follows from the existence of infinitely many Woodin cardinals. He also showed that $\mathbf{\Pi}^1_2$-determinacy is equivalent to "for all $x\in\mathbb{R}$, there is a countable ordinal $\delta$ such that $\delta$ is a Woodin cardinal in some inner model of $ZFC$ containing $x$, and that $\mathbf{\Delta}^1_2$-determinacy is equivalent to "for every $x\in\mathbb{R}$, there is an inner model M such that $x\in M$ and $M\models ZFC+$"there is a Woodin cardinal". [3]
$ZFC+$ (lightface) $\Delta^1_2$-determinacy implies that there many $x$ such that $HOD^{L[x]}\models ZFC+$"$\omega_2^{L[x]}$ is a Woodin cardinal". $Z_2+\Delta^1_2$-determinacy is conjectured to be equiconsistent with $ZFC+$"Ord is Woodin", where "Ord is Woodin" is expressed as an axiom scheme and $Z_2$ is second-order arithmetic. $Z_3+\Delta^1_2$-determinacy is provably equiconsistent with $NBG+$"Ord is Woodin" where $NBG$ is Von Neumann–Bernays–Gödel set theory and $Z_3$ is third-order arithmetic.
Gitik and Schindler showed that, in $ZF$, if $\aleph_\omega$ is a strong limit cardinal and $2^{\aleph_\omega}>\aleph_{\omega_1}$, then the axiom of projective determinacy holds. Also, if there is a singular cardinal of uncountable cofinality such that the sets of the cardinals below it such that the $GCH$ holds is both stationary and costationary, then again the axiom of projective determinacy holds. It is not known whether these two results extends to $L(\mathbb{R})$-determinacy. [4]
Foreman, Magidor and Schindler showed that if there exists infinitely many cardinals $\delta$ above the continuum such that both $\delta$ and $\delta^{+}$ have the tree property, then the axiom of projective determinacy holds. This hypothesis was shown to be consistent relative to the existence of infinitely many supercompact cardinals by James Cummings and Foreman. [4]
References
- Jech, Thomas J. Set Theory. Third, Springer-Verlag, Berlin, 2003. (The third millennium edition, revised and expanded) www bibtex
- Kanamori, Akihiro. The higher infinite. Second, Springer-Verlag, Berlin, 2009. (Large cardinals in set theory from their beginnings, Paperback reprint of the 2003 edition) www bibtex
- Koellner, Peter and Woodin, W Hugh. Chapter 23: Large cardinals from Determinacy. Handbook of Set Theory , 2010. www bibtex
- Larson, Paul B. A brief history of determinacy. , 2013. www bibtex