Homework in logics for Computer Science : Prove that the groups are equal

Question

$A$ is a group and $B_1,B_2\subseteq A$. $F_1,F_2$ groups of functions so each $f\in F_1\cup F_2$ : $f:A^{n}\to A$. We call $S_1= X_{B_1,F_1}$, (this notation means the group that contains B1 members and the new members that we get by applying the function F1 on B1 members, and on the new members as well)

$S_2= X_{B_2,F_2}$. Assume: $S_1=S_2$.

Prove: $S_1= X_{B_1\cup B_2, F_1\cup F_2}$

I succeeded to prove that every member in $S_1$ is in $X_{B_1\cup B_2, F_1\cup F_2}$. I have difficulties proving the other direction. I'd really really appreciate if you could help. Thank you!

Answer 1

I'm going to assume that you mean "set" everywhere you've written "group". Then the exercise is both meaningful and computer-sciency.

Your description of $X_{B,F}$ is a bit informal -- in order to do proofs you need to work with something more concrete than that. A CS-flavored semi-formal understanding would be something like

Definition A. $X_{B,F}$ is the set of values of all expressions that can be written using elements of $B$ as constants and elements of $F$ as operators.

A crisper definition, usually favored by mathematicians would be

Definition B. $X_{B,F}$ is the smallest subset of $A$ that contains $B$ and is closed under each element of $F$.
(Such a smallest subset exists, because the property is preserved by taking intersections, and there's at least one such subset, namely $A$, so $X_{B,F}$ is the intersection of all subsets of $A$ that satisfy the condition.)

Computer science texts often prefer a more constructive, but also more laborious, definition along the lines of

Definition C. Given $B$ and $F$, define $\Phi:\mathcal P(A)\to\mathcal P(A)$ by $$ \Phi(X) = B \cup \{ f(x_1,\ldots,x_n) \mid f\in F, x_1,\ldots,x_n\in X\} $$ Then $X_{B,F}$ is the smallest fixed point of $\Phi$, namely $$ X_{B,F} = \bigcup_{k\in \mathbb N} \Phi^k(\varnothing) $$

These three definitions are all equivalent, and in order to become a good theoretical scientist you'll need to understand intuitively that they are equivalent, and switch between them at will.

---

You need to prove that $X_{B_1\cup B_2,F_1\cup F_2}\subseteq X_{B_1,F_1}$, assuming that $X_{B_1,F_1}=X_{B_2,F_2}$

Discovering a proof is easiest (for me, at least) working from Definition A. In that case what we have to prove is that for every $B_1,B_2,F_1,F_2$-expression there is a $B_1,F_1$-expression with the same value. This turns out to be pretty easy by structural induction on the $B_1,B_2,F_1,F_2$-expression.

The case where the top operator in the expression is from $F_1$ is immediate. We get $B_1,F_1$-expressions for the operands from the induction hypothesis, and just plugging those into the same top operator gives a $B_1,F_1$-expression for the entire thing.

When the top operator is from $F_2$, the induction hypothesis gives us $B_1,F_1$-expressions for the operands. Convert each of those to a $B_2,F_2$-expression (which you can do because $S_1=S_2$). Plugging them into the top operator gives a $B_2,F_2$-expression for the entire thing, and you can convert that back to a $B_1,F_1$-expression because $S_1=S_2$ again.

---

If you have to work with Definition C instead, the structural induction proof can be rephrased as a proof by strong mathematical induction on the $k$ in $\Phi^k(\varnothing)$. There will be slightly more notation to keep track of, but the basic idea is the same.

---

Finally, for Definition B, the natural idea for proving that $X_{B_1,B_2,F_1,F_2}$ is a subset of something is to show the something contains $B_1,B_2$ and is closed under $F_1,F_2$. Since by definition $X_{B_1,B_2,F_1,F_2}$ is the smallest set with that property, it is a subset of everything else that has it.

So we need to prove that $S_1=X_{B_1,F_1}$ contains $B_1$ and $B_2$ and is closed under $F_1$ and $F_2$. Of these $B_1$ and $F_1$ hold by definition. For $F_2$ we can repeat the induction step from the structural induction proof -- but when we try to write down nicely, we find that what's really going on is that by definition $B_2$ and $F_2$ hold for $X_{B_2,F_2}$, but that is assumed to be equal to $S_1$, so all the closure properties do indeed hold for $S_1$, and we're done.

This final proof under Definition B is very slick and compact. Personally I find it more intuitive to discover the proof thinking about Definition A, and then convert it to an argument that works with Definition B. Your mileage may well vary here, though.