[FOM] Definable sets in ZFC

[Max Weiss]

Dear Florian & FOMers,

Thanks for the (to me anyway) interesting questions!  Here are a few
replies in the hope that somebody will improve on them.

The notion of definability seems to be relative to a model M of ZF.

1) Say that the set D in M is the set of ZF-definable sets, i.e., the
set of S in M such that for some formula F(x), we have that

ZF proves \exists!x F(x) and S satisfies F(x).

Now, if D is itself definable, there is a formula F(x) such that

ZF proves \exists!x F(x) and d satisfies F(x).

So D would belong to itself, contradicting Foundation.  (Is there an
argument that doesn't use Foundation?)

2) Every ordinal is constructible, but there are only countably many
definable sets.  So not every constructible set is definable.
Conversely, the set of countable sets is definable.  But, the question
whether or not it is constructible depends on M.

((The constructible universe results from transfinitely iterating a
definable-powerset operation.  More precisely, a set S is
definable-with-parameters-in-T if there's a formula F and sets
S1,...SK in T such that F^T(U,S1,...,Sk) holds if and only if U=S for
all sets U, where T is a class and F^T results from restricting to T
all quantifiers in A.  The set L_{\alpha} is the set of all sets
definable-with-parameters-in-UNION(L_{\beta}:\beta<\alpha).  A set is
constructible if it belongs to some L_\alpha.))

3) Doubts about extensionality: could two definable sets agree on
their definable elements? E.g. the set of constructible countable
sets, and the set of countable sets?

4) Maybe this depends on M?

5) The "least indefinable ordinal" might be worth thinking about here.

6) I don't know!

Chapter 5 of Kunen's /Set Theory/ is called "Defining definability".


Best,

Max



On 14 September 2010 17:16, Florian Rabe <f.rabe at jacobs-university.de> wrote:
> Dear FOMers,
>
> I have some questions regarding definable sets. To be precise, let me say what I mean by "definable":
>
> - Let ZF be the first-order language of set theory with the usual axioms. If the answer to any of my questions depends on the choice of axioms (e.g., with/without choice), I would be very interested in that as well.
>
> - Call a set S definable if there is a ZF-formula F(x) such that "exists^! x.F(x)" is a theorem and F(S) holds. Here exists^! is the quantifier of unique existence.
>
> Clearly, not all sets are definable because there are only countably many formulas F. Therefore, my questions:
>
> 1) What are some examples of non-definable sets?
>   I'm particularly interested in sets that
>   - can be described informally as in "the set S which ..."
>   - are relevant in mathematical practice
>
> 2) Are the definable sets the same as the ones in Gödel's constructible universe?
>   If not, what is their relation?
>
> 3) Do the definable sets form a model of ZF?
>
> 4) Is there a set containing
>   a) exactly the definable sets?
>   b) at least the definable sets?
>
> 5) Is there a ZF formula P(x) such that P(S) is true for
>   a) exactly the definable sets S?
>   b) at least the definable sets S (but not for all sets S)?
>
> 6) If an answer to 4a-5b is No, are there more expressive variants of ZF for which the answer is Yes?
>
> I'm not sure which of these questions are trivial. I'd appreciate pointers to the literature as well.
>
> Best,
> Florian
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>