Constructible hierarchy: Difference between revisions

Say a subset \(X\) of \(Y\) is definable if there are some \(z_0, z_1, \cdots, z_n \in Y\) and some formula \(\varphi\) in the language of set theory so that the elements of \(X\) are precisely the \(x\) so that \(Y\) satisfies \(\varphi(x, z_0, z_1, \cdots, z_n)\). For example, under the von Neumann definition of ordinal, the set of even numbers, the set of odd numbers, the set of prime numbers, the set of perfect squares greater than 17, and so on, are all definable. Using elementary cardinal arithmetic, you can note that there \(\max(\aleph_0, |Y|) = |Y|\) definable subsets of an infinite set \(Y\), and thus "almost all" subsets of an infinite set are not definable. The parameters \(\vec{z}\) aren't of importance in the context of definable subsets of the natural numbers, since all elements of the natural numbers are definable, but they will be if \(Y\) is uncountable, because no uncountable be pointwise definable, and ensure that there aren't just always \(\aleph_0\) definable subsets of a set.