# Functional and relational inductive set

Before we get into the actual problem we would like to first look at some background of the problem:

• First we are given a set $$U$$ and an initial set $$B\subseteq U$$,
• and a class $$\mathcal{F}$$ of functions containing just two members $$f:U\times U\to U$$ and $$g:U\to U$$.
• Say a subset $$S$$ of $$U$$ is closed under $$f$$ and $$g$$ iff whenever elements $$x$$ and $$y$$ belongs to $$S$$, then so also do $$f(x,y)$$ and $$g(x)$$.
• Say that $$S$$ is inductive iff $$B\subseteq S$$ and $$S$$ is closed under $$f$$ and $$g$$.
• Let $$C^*$$ be the intersection of all the inductive subsets of $$U$$.
• Define a construction sequence to be a finite sequence $$(x_1,...,x_n)$$ of elements of $$U$$ such that for each $$i\leq n$$ we have at least one of $$x_i\in B$$ $$x_i=f(x_j,x_k)\text{ for some }j $$x_i=g(x_j)\text{ for some }j
• Let $$C_*$$ be the set of all points $$x$$ such that some construction sequence ends with $$x$$.
• Then one can show that $$C^*=C_*$$.

Now, the problem:

We can generalize the discussion by requiring of $$\mathcal{F}$$ only that it be a class of relations on $$U$$. $$C_*$$ is defined as before except that $$(x_0,x_1,...,x_n)$$ is now a construction sequence provided that for each $$i\leq n$$ we have either $$x_i\in B$$ or $$(x_{j_1},...,x_{j_k},x_i)\in R$$ for some $$R\in\mathcal{F}$$ and some $$j_1,...,j_k$$ all less than $$i$$. Give the correct definition of $$C^*$$ and show that $$C^*=C_*$$.

My approach:

• Say a relation $$R$$ is $$i+1$$-valued if $$R\subseteq U^{i+1}$$.
• Say a subset $$S$$ of $$U$$ is closed under relations $$R_i$$'s in $$\mathcal{F}$$ iff for any $$x_1,...,x_j\in S$$ and $$j+1$$-valued $$R_j\in \mathcal{F}$$, if $$x\in U$$ such that $$(x_1,...,x_j,x)\in R_j$$, then $$x\in S$$.
• Say that $$S$$ is $$R$$-inductive iff $$B\subset S$$ and $$S$$ is closed under $$R_i$$'s.
• Let $$C^*$$ be the intersection of all the $$R$$-inductive subsets of $$U$$.

Now, I wonder whether my definition is correct or not... Also I want to show that $$C_*$$ is $$R$$-inductive so that $$C^*\subseteq C_*$$. Can any one help me on this please?

• FYI, I changed the definition of closedness under relations a little bit.
– kkkk
Nov 6, 2020 at 2:49

I think my definition of $$C^*$$ is correct because I can show $$C^*=C_*$$ as follows:
First, to show $$C^*\subseteq C_*$$, we just need to show that $$C_*$$ is $$R$$-inductive. First, since $$(x)$$ with $$x\in B$$ is a construction sequence that ends with $$x$$, $$B\subseteq C_*$$. And suppose that $$x_1,...,x_i\in C_*$$, that $$R_i\in\mathcal{F}$$ is an $$i+1$$-valued relation, and that $$x\in U$$ such that $$(x_1,...,x_i,x)\in R_i$$. we can concatenate the construction sequences of $$x_j$$'s and $$(x_1,...,x_i,x)$$ to obtain the construction sequence that ends with $$x$$. So $$x\in C_*$$ showing $$C_*$$ is closed under $$R_i$$'s and hence is $$R$$-inductive.
To show $$C_*\subseteq C^*$$, take $$x\in C_*$$ and let $$(x_1,...,x_n,x)$$ be a construction sequence that ends with $$x$$. Note that $$x_1\in B\subseteq C^*$$. And by ordinary induction on $$j$$, we can see that $$x_j\in C^*$$ because of the fact that $$C^*$$ is closed under the $$R_i$$'s.