Help on using structural induction for set equality

189 Views Asked by At

Denote $\mathbb{Z}[x]$ the set of polynomials on one variable $x$ with integer coefficients. For example, $p(x)=x^2-3x+42$ is such a polynomial, whereas $q(x)=-1.5x^3+97x$ is not

Let's define the set $S\subseteq \mathbb{Z}[x]$ using the following rules:

$$2\in S$$ $$x\in S$$ $$\forall p(x)\in\mathbb{Z}[x], \forall q(x)\in S,\,\, p(x)q(x)\in S$$ $$\forall p(x),q(x) \in S,\,\, p(x)+q(x)\in S$$

Also define the set $T=\{2p(x)+xq(x)|p(x),q(x)\in\mathbb{Z}[x]\}$. Prove $S=T$. $$$$ I know the prove will be $S \subseteq T$ and $T \subseteq S$

For $S \subseteq T$ I want to use structural induction to show every element of $S$ satisfies the property of $T$ but I don't understand what the properties of T are so I can define a predicate that I can use.

1

There are 1 best solutions below

2
On BEST ANSWER

Show that the rules defining S hold for T.
Then since by definition, S is the smallest
set for which the rules hold, S subset T.