2
$\begingroup$

Lets call a definable property $\phi(y,z_1,..,z_n)$ as terminating over a set $A$ if and only if recursive successive additions of every set $\{y \in A| \phi(y,z_1,..,z_n)\}$ from parameters $z_1,..,z_n \subseteq A $ belonging to the prior stage (starting from the set of all singleton subsets of $A$), terminates in steps $< |A|^+$, i.e. further additions of subsets of $A$ definable after that formula won't result in new sets.

To clarify what I mean, the definition of the stages is as follows:

$$\rho_0(A) = \{\{x\}| x \in A\}$$

$$\rho_{i+1}(A)= \rho_i(A) \cup \{\{y \in A|\phi(y,z_1,..,z_n)\}|z_1,..,z_n \in \rho_i(A) \} $$

$$\rho_i(A)= \bigcup_{j<i} (\rho_j(A)), \text{ if } i \text{ is a limit ordinal}$$

Now $\phi(y,z_1,..,z_n)$ would be said to be terminating over set $A$ if and only if for some ordinal $\kappa <|A|^+$ we have: $\rho_{\kappa+1}(A)=\rho_{\kappa}(A)$

$\text {Define:-}$ Properties $\phi(y,z_1,..,zn), \psi(y,w_1,..,w_m)$ are said to be jointly terminating over $A$, iff successive recursive additions of subsets of $A$ defined after both of them terminate. i.e. we have the same definitions above of the base stage and the limit stages, but we change the definition of successor stages to be:

$$\rho_{i+1}(A)= \rho_i(A) \cup \{\{y \in A|\phi(y,z_1,..,z_n)\}|z_1,..,z_n \in \rho_i(A) \} \cup \{\{y \in A|\psi(y,w_1,..,w_m)\}|w_1,..,w_m \in \rho_i(A) \} $$

For example, complements defined as $\{y \in A| y \not \in z\}$ would terminate at 1, while Boolean union defined as $\{y| y \in z_1 \lor y \in z_2\}$ would terinate at $\omega_0$, and both would jointly terminate at $\omega_0$.

Questions:

  1. Is there any general way to know if a property is terminating over a set in the above sense?

  2. If $\phi$ and $\psi$ are terminating over $A$, then would they be jointly terminating over $A$ as defined above?

  3. Is the set of all definable subsets of $A$ by terminating properties, equal in cardinality to $A$? Formally speaking: is $ |\{\{x \in A|\phi\}| \phi \text { is terminating over } A\}| = |A|$?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.