# Recursively constructed set definition

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?

• To help make the question more illuminating it might be useful to specify the set of numbers from which you are choosing as the Pell Numbers. The infinite set of Pell Numbers can be specified using a recurrence relation $p_n=2p_{n-1}+p_{n-2};p_1=0,p_2=1$, in the form of a object constructor (as you would find in an object oriented computer programming language) To access the 'infinite' set for arbitrary $p_n$ can be via the recurrence relation directly or via the output of a solver algorithm e.g. equivalent of mathematica's RSolve. – James Arathoon Aug 12 '17 at 13:39

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)$$

• Brilliant answer. Very appreciated. – Andremoniy Aug 12 '17 at 11:47
• Dear @HenningMakholm, could you give me a clue, when can I read more about the inference systems? – Andremoniy Aug 12 '17 at 12:03
• @Andremoniy: Hmm, good question. I'll admit I don't really have a reference ready. I learned the basics from photocopied notes back as a graduate student, and it seems to be used all over the theoretical computer science literature. – hmakholm left over Monica Aug 12 '17 at 12:12

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.

• I am appreciated for your answer, but it would be more full and more useful, if you would be so kind give me an example for the case described above of the rigorous definition (this is an absolutely theoretic example). – Andremoniy Aug 12 '17 at 11:31
• "You cannot define $X$ with a definition that refers to itself." Like this one from Wikipedia en.wikipedia.org/wiki/Rational_number "In mathematics, a rational number is any number that can be expressed as the quotient or fraction $p/q$ of two integers, a numerator $p$ and a non-zero denominator $q$." But since the set of rationals already includes the integers and a rational is also formed from the ratio of any two rationals wouldn't it be better to just admit the underlying circularity and make the definition recursive – James Arathoon Aug 12 '17 at 12:37
• @JamesArathoon this is not an example of a self referential definition. The rationale are defined as the set of classes of an equivalence relation on a subset of the square if the integers. It has a subset that is isomorphic to the integers. – Henno Brandsma Aug 12 '17 at 13:27
• @HennoBrandsma: I agree the set of all integers must be created before the set of all rational numbers. The set of positive integers can be created with a recurrence relation say $p_n=p_{n-1}+1;p_1=0$ and is an ordered set, element 1 being zero, element 2 being one etc. It seems to me that the set of rationals cannot be constructed in the same way and certainly not as an ordered set. In elementary terms we need some way to construct a candidate rational and then implement a test or series of tests based on the defining axioms of the set construct to make sure that it is indeed a rational. – James Arathoon Aug 12 '17 at 15:11
• continued... These tests against the defining axioms of the of the set construct can be circumvented if we prove that the method we use to construct the candidate rational will always give us a number which passes the tests. – James Arathoon Aug 12 '17 at 15:16

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.