Recursively constructed set definition

Question

Let $\Sigma$ be some finite set of elements. A function $f$ is a mapping: $f: \Sigma\rightarrow\Sigma$. Let also define that elements of $\Sigma$ has some boolean property $c(x)\in\{T,F\}$.

Consider the set $X$ which is constructed recursively, using disjunction of two conditions: or $c(x)=T$ or $f(x)\in X$. The latter condition means that inclusion of some element $x$ depends on the current state of $X$.

Will it be mathematically correct to describe this set in the following form?

$X=\{x\in\Sigma | c(x)=T\text{ or }f(x)\in X\}$

I doubt that it is rigorous definition. For instance, it is probably needed to define an order in which elements of $\Sigma$ are considered for adding into $X$. Will it be enough strict in this case or it should be defined in some different way?

Answer 1

In this particular case you can probably get away with defining your set as $$ X = \{ x\in\Sigma \mid \exists n\ge 0: c(f^n(x)) = T \} $$ But that works only because your recursive definition has a very particular form.

For general recursive definitions of this kind, I can say with some certainty that there isn't a generally understood way to write them that is as short and convenient as set builder notation. I did a PhD and 3 years of post-doc work in an area of computer science where such definitions are our bread-and-butter and I never saw one. What we would usually do was write an inference system:

$$ \frac{}{x\in X}\; c(X)=T \qquad \qquad \qquad \frac{f(x)\in X}{x\in X} $$

and expect the reader to know how to interpret that rigorously. This can usually be assumed when you write for computer scientists, but not with a general mathematical audience.

You can say

$X$ is the smallest subset of $\Sigma$ that satisfies $$ X = \{ x\in \Sigma \mid c(x)=T \lor f(x)\in X \} $$

where what you wrote is now presented as a condition rather than a definition. However, this depends on the reader being able to convince himself on his own that there is indeed a smallest subset of $\Sigma$ that satisfies the condition.

If that won't fly with your audience you'll need start by defining a helper function $\Phi:\mathcal P(\Sigma)\to\mathcal P(\Sigma)$:

$$ \Phi(A) = \{ x\in\Sigma \mid c(x)=T \lor f(x)\in A \} $$

and then explicitly iterate it:

$$ X = \bigcup_{n=0}^{\infty} \Phi^n(\varnothing) $$

Answer 2

You cannot define $X$ with a definition that refers to itself. You want to use comprehension to show $X$ exists but in order for the defining formula to be valid we already need $X$ to be a set.

You might be able to come up with a way that $X$ is a fixed point of some iterative process, and then you could have a way to rigorously define it.

Answer 3

For this material in a mathematical context, I would suggest the first four chapters of "Elementary Induction on Abstract Structures" by Moschovakis. You can find a more explicit construction with regard to set theory in Chapter 2, Section 3 of "Set Theory: An Introduction to Large Cardinals" by Drake. In particular, you will find that Definition 3.4 describes how formulas with at least two free variables are converted to operations, provided that one has a target (the empty set) for formulas which would not otherwise yield a singular image. You can find a similar definition in "Natural models of set theories" by Montague and Vaught when they describe "iota theories".

For a relationship of this material to inference systems, look at Aczel's contribution, "An introduction to inductive definitions" from "Handbook of Mathematical Logic", edited by Barwise.

As explained most clearly in Moschovakis, these are second-order constructions whose expansion to a syntax involving a closure ordinal makes them seem more constructive. A simple way to see how advocates of first-order logic as mathematical logic would object to such definitions is to realize that taking the "smallest set" satisfying the definition constitutes a quantification over models.