Set closed under a collection of functions Suppose $\mathcal F$ is a family of functions from $A$ to $A$, and $B\subseteq A$. Prove that the closure of $B$ under $\mathcal F$ exists.
Attempt: I defined a set $$\bigcup_{n \in \mathbb N}B_n$$
where $B_1=B$ and for all $n \ge 1$, $$B_{n+1}=\{f(x)\mid f \in \mathcal F \,\text{and x $\in$ $B_n$}\}$$
I am not sure with my answer above, can anyone please check and explain if my answer is wrong? Thanks in advance.
 A: Write $\mathcal F = (f_i)_{i \in \mathbb{N}}$. Define $C_0 := B$ and $C_{i+1} := \cup_{j \in \mathbb{N}} f_j(C_i)$ for $i \in \mathbb{N}^+$.
Case 1: $C_1 \subseteq B$
Obviously $C_{i+1} \subseteq C_{i}$ for all $i \geq 1$. On the other hand, $|C_i| \geq 1$ for every $i$ by the definition of a function. So $(C_i)_{i \in \mathbb{N}}$ is a monotonically decreasing bounded sequence, and therefore its limit exists.
Case 2: $C_1 \supseteq B$
Analogous reasoning with $C_{i+1} \supseteq C_{i}$ for all $i \geq 1$, $|C_i| \leq |A|$ for every $i$, and monotonically increasing sequences.
Let $L$ denote the limit set above.
The closure you are searching for then is $L \cup B$.
A: This answer is motivated by Enderton's "A Mathematical Introduction to Logic".
The closure of $B\subset A$ under family of functions $\mathcal{F}$ is defined as follows.
I will generalize to the case that $f\in \mathcal{F}$ has $f:\times^m A \to A$ for any $m\in \mathbb{N}$.
$C\subset A$ is said to be a closure of $B\subset A$ under $\mathcal{F}$ if $B\subset C$ and for all $f\in\mathcal{F}$, with $f:\times^m A \to A$ if $c_1,\ldots, c_m\in C$ then $f(c_1,\ldots,c_m)\in C$.
We prove that such a set exists.
Let $C_0 = B$.
Let $[n] = \{m\in\mathbb{N}: m < n\} = \{0, 1, \ldots, n-1\}$. Recall that a finite sequence on $A$ is a function $x: [n] \to A$. We use $x_m$ to denote $x(m)$. We say a sequence $x$ on $A$ is a construction sequence if for each $0\le i < n$ we have either

*

*$x_i \in C_0$

*There exists $f\in \mathcal{F}$ with $f:\times^m A\to A$ and there exists $j_1,\ldots, j_m < i$ such that $f(x_{j_1},\ldots, x_{j_m}) = x_i$
Now let
$$
C_n = \{c \in A: \text{There is a construction sequence } x:[n]\to A \text{ and } x_{n-1}=c\}
$$
That is $C_n$ is the collection of final elements of length-$n$ finite construction sequences.
Now let
$$
C = \bigcup_{i\in\mathbb{N}} C_i
$$
We now prove that $C$ is the closure of $B\subset A$ under $\mathcal{F}$.
Clearly $B=C_0 \subset C$.
Now consider $f\in \mathcal{F}$ with $f:\times^m A \to A$. Let $c_1, \ldots, c_m\in C$.
We must prove $f(c_1,\ldots, c_m)\in C$.
Since $c_i\in C$ that means there is some $n_i$ such that $x^i:[n_i]\to A$ with $x^i$ a construction sequence and $x^i_{n_i-1} = c_i$.
We can define a new sequence $x$ which is the concatenation of $x^1, \ldots, x^m$.
Without getting into the details of the definition of a concatenation of sequences, it is the case that $x$ is a construction sequence which includes all of $c_1, \ldots, c_m$.
We now append $f(c_1, \ldots, c_m)$ to $x$ to make a new construction sequence $x^+$.
Since $x^+$ is a construction sequence ending in $f(c_1, \ldots, c_m)$ we have that $f(c_1, \ldots, c_m)\in C$.
A: I'll add another answer using another approach. Let $B\subset A$ and $\mathcal{F}$ a family functions where $f\in \mathcal{F}$ means there exists $n\in \mathbb{N}$ such that $f:A^n \to A$.
A set $C$ is said to be $(A, B, \mathcal{F})$-inductive if
\begin{align*}
&B \subset C\\
&\text{and}\\
&\forall f \in \mathcal{F}(\forall n \in \mathbb{N}(f:U^n \to U \implies \forall \tilde{c}\in C^n(f(\tilde{c})\in C)))
\end{align*}
If we restrict $\mathcal{F}$ to contain functions $f:A\to A$ the second condition can be simplified as
$$
\forall f \in \mathcal{F}(\forall c\in C(f(c)\in C))
$$
Define
$$
\mathcal{C} = \{C\in \mathcal{P}(A): C \text{ is } (A, B, \mathcal{F})\text{-inductive}\}
$$
We define the closure of $B$ under $\mathcal{F}$ to be
$$
\mathbb{N}_{(A, B, \mathcal{F})} = \bigcap \mathcal{C}
$$
We have that $A\in \mathcal{C}$ so $\mathcal{C}$ is non-empty so there are no worries with taking the intersection.
We can prove that $\mathbb{N}_{(A, B, \mathcal{F})}$ is $(A, B, \mathcal{F})$-inductive. This is because for every $C\in \mathcal{C}$ we have $B\subset C$ so we must have $B\subset \mathbb{N}_{(A, B, \mathcal{F})}$. For the second condition, consider $f\in \mathcal{F}$ with $f:A^n \to A$. Let $\tilde{c}\in \mathbb{N}_{(A, B, \mathcal{F})}^n$. This means that $\tilde{c}\in C$ for each $C\in \mathcal{C}$. Because $C$ is $(A, B, \mathcal{F})$-inductive, this means $f(\tilde{c}) \in C$ for each $C\in \mathcal{C}$. But this means that $f(\tilde{c})$ is also in $\mathbb{N}_{(A, B, \mathcal{F})}$.
These two conditions mean $\mathbb{N}_{(A, B, \mathcal{F})}$ is $(A, B, \mathcal{F})$-inductive.
All of this proves the existence and inductiveness of $\mathbb{N}_{(A, B, \mathcal{F})}$. From these definitions we can prove both induction theorems and the recursion theorem for $\mathbb{N}_{(A, B, \mathcal{F})}$ as generalizations of the induction and recursion theorems over the natural numbers $\mathbb{N}$.
