0
$\begingroup$

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<i,k<i$$ $$x_i=g(x_j)\text{ for some }j<i.$$
  • 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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .