MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathcal{A}$ be an admissible set, or for simplicity a model of ZF without the power set axiom. Let $X \subset \mathcal{A}$. Is there an easy way to show $X$ is $\Sigma$ on $\mathcal{A}$?

PS: $X$ is $\Sigma$ on $\mathcal{A}$ if it is definable in $\mathcal{A}$ by a $\Sigma$ formula i.e. a formula built from atomic formulas and their negations using only $\wedge,\vee, \forall x \in y, \exists x$. To be specific assume $\mathcal{A}=L_{\omega_1^{CK}}$. Also, I need to consider the specific case of $X$ being a set of (codes of) $\mathcal{L}(\omega_1,\omega)$-sentences or to be precise: $X$ is a set of $\mathcal{L}$-sentences + infinitary sentences specifying that certain quotient sets are finite. Here $\mathcal{L}$ is some first order language.

share|cite|improve this question
Does $\Sigma$ actually mean $\Sigma_1$? – Asaf Karagila Aug 15 '12 at 22:42
You need to narrow down your question. There are a lot of ways of doing this, but there is nothing we know about this $X$. Also different admissible sets admit different methods: $L_{\omega_1^{ck}}$ and $H_{\omega_1}$ are totally different beasts! We need something to work with... – François G. Dorais Aug 15 '12 at 22:52
Asaf, it's slightly different but essentially equivalent for most purposes. For $\Sigma_1$ we assume prenex form; $\Sigma$ is more general but every $\Sigma$ statement is equivalent to a $\Sigma_1$ statement because of reflection. – François G. Dorais Aug 15 '12 at 22:58
(Technically, you can use negation anywhere in the bounded part of a $\Sigma_1$ formula, but it's straightforward to eliminate those.) – François G. Dorais Aug 15 '12 at 23:32
up vote 5 down vote accepted

A frequently useful way to show that a function $F$ is $\Sigma$ definable is to give a definition of it by recursion, in the form $F(x)=G(x,F\upharpoonright H(x))$ where $G$ and $H$ are already known to be $\Sigma$-definable and $H(x)$ is the set of predecessors of $x$ in a well-founded relation $\prec$ (so that the recursion is well-defined).

It is important here that the function $H$, not just the (morally equivalent) relation $\prec$, be $\Sigma$-definable.

Although I wrote here about the special case of $\Sigma$-defining functions, such definitions often play a key role in $\Sigma$-definitions of other sorts of sets.

share|cite|improve this answer

The usual way to show that a set is $\Sigma_1$ definable, or some other particular complexity, is to exhibit a specific definition of the set having that complexity. One has a set, defined in a certain way, and one observes that the definition has a particular complexity. Typically, researchers in descriptive set theory and admissible set theory eventually gain so much experience doing this---showing that one set is $\Sigma^1_3$ and other is at worst $\Pi_5$ and so on---that eventually they don't even need actually to exhibit the specific formula providing the definition, since it is clear what the complexity is from a brief mention of the most relevant parts of it. It is not difficult to achieve this same skill with practice, and I would encourage you simply to try out the definitions in the cases with which you are confronted.

Perhaps it would be helpful to consider a specific example?

Meanwhile, it is generally a much harder task to show that a set is not $\Sigma_1$ definable or that it is not a member of a certain definability class. This amounts to showing a lower bound instead of an upper bound, and for this one often appeals to much deeper parts of the theory, whether it is some boundedness principle or universality principle, or by reducing a set that is known to be difficult to the given set.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.