# The intersection of (two) inductively defined sets

I first want to proof that the intersection of two inductively defined sets is again inductive. We have $A$ which is a set of elementary elements and a set of functions $F$ where each function has arity $k \geq 1$. The set $S$ is the smallest set inductively defined through $A$ and $F$ for which the follwing is true:
(1) $A \subseteq S$
(2) $f \in F$ and $f$ has arity $k$ and $s_1,...,s_k$ are elements of $S$. Then $f(s_1,...,s_k)$ is also in $S$.

Assume that $S_1$ and $S_2$ are both sets for which (1) and (2) are true. I want to show that the rules (1) and (2) are also true for the intersection $S_1 \cap S_2 = S$.
I am not even sure where to start. What does it even mean that $S_1$ and $S_2$ are sets for which both (1) and (2) are true? Do I know that $A_1 \subseteq S_1$ and $A_2 \subseteq S_2$ or do I know that $A \subseteq S_1$ and $A \subseteq S_2$ or is it irrelevant in this situation?
Let's assume that $A \subseteq S_1$ and $A \subseteq S_2$. Therefore we also know that $A \subseteq S$ by definition of the intersection. So (1) is true for $S$.
Is this even correct until now? I think if I wanted to show that (2) is true for $S$, I would take an arbitrary function $f$ with arity $k \geq 1$ and $s_1,...,s_k$ elements and show that $f(s_1,...,s_k) \in S$.

## 1 Answer

Intuitively, you can view $A$ as the set of "building blocks" that you begin with, and $F$ the operations that let you construct new blocks from these.

Example: let $A=\{a,b\}$ — the elements we start with — and $f: x,y \mapsto xy$, e.g. $f(a,b) = ab$, $f(aba,bb)= ababb$ and so forth. Then the set $S$ inductively generated from $A$ and $f$ in this case is the set of all strings that you can form starting from $a$ and $b$ by applying $f$ zero or more times, e.g. $ab;bbbb;abab;babaa$ are all in $S$.

I took it that you needed an informal explanation, you can see how to proceed from here? — it should be easy I guess. BTW, no requirement of unique readability, right?

• I haven't heard of unique readability, so I guess no and yes this has helped me a bit but I am still not sure how to proceed from here. For example, do sets $S_1$ and $S_2$ have the same set of building blocks or can they be different? What is the set of building blocks for the intersection? Is it the intersection of building blocks of set $S_1$ and $S_2$? I feel like I am lost on this proof even though I shouldn't be. – Rard Dec 6 '16 at 16:19
• Don't worry, you're on the right path here. "Do $S_{1}$ and $S_{2}$ have the same building blocks?" What you can do is examine the different situations that can arise here individually, e.g. suppose they have no building blocks in common. Then what would their intersection look like? – wet Dec 6 '16 at 16:31
• Let's say I have $S_1$ with $A_1=\{0\}$ and $S_2$ with $A_2=\{1\}$ and the function $f$ with $f(x) = x + 1$. They have no building blocks in common but the intersection of $S_1$ and $S_2$ would definitely not be empty. I could also have $f(x) = x * 2$ and then the intersection of $S_1$ and $S_2$ would be empty. – Rard Dec 6 '16 at 16:50
• Yes, that is correct. Now recall what we are trying to show here: that the intersection is inductive. Note that we can take the empty set to be vacuously inductive. Now, look at the example you gave with the $x\mapsto x+1$ function on the building blocks $\{0\},\{1\}$ . You noticed the intersection is nonempty. Is it inductive? Why? Can you find a set of building blocks that generates it? Assuming every inductive $S$ has $A\subseteq S, F$ that generate it, can you come up with a way of, given two inductive sets $S_{1}, S_{2}$ and their generators, find the generators of $S_{1}\cap S_{2}$? – wet Dec 6 '16 at 17:51
• The intersection is inductive. We would have $A={1}$ and $x \mapsto x + 1$. Not sure how I would proof this, but I would say that $A = (A_1 \cup A_2) \cap S1 \cap S2$. So every building block from $A_1 \cup A_2$ that is also in the intersection $S_1 \cap S_2$. – Rard Dec 6 '16 at 18:30