1

Let $S$ be a recursively defined set of expressions.

Base case, $v\in S$

Constructor Case: if $x\in S$ and $y\in S$, then $(x+y)\in S$ and $(x * y)\in S$

Prove by stuctural induction that for every $n \in S$, there exists $a,b\in\Bbb N$ such that $e \le a(v^b)$ I'm not sure how to proceed forward on this.

My thoughts so far: We know $x * y < x+y$ for anything greater than $2$

If we assume the inductive hypothesis, do we show $a_1(v^c)*a_2(v^d)\le a(v^b)$ for some $a$ and $b$? if so how do we show that?

Brian M. Scott
  • 616,228
user65065
  • 23
  • Please check that I interpreted your semi-$\LaTeX$ correctly. What is $e$? Are these expressions being interpreted as arithmetic of natural numbers? What is the connection between the symbol strings in $S$ and the arithmetic implies by your use of $\Bbb N$ and inequalities? – Brian M. Scott Mar 05 '13 at 21:22
  • Is $S\subseteq\Bbb R$ or something? If not, what is $e$? Do we know anything about $v$? – Berci Mar 05 '13 at 21:24
  • That part is a little confusing to me as well. V is a variable, we can assume that its a number. V is also an expression because v+0 = v. I'm guess we can assume all elements in S evaluate to a natural number, and we need to prove the inequality with these in mind. – user65065 Mar 05 '13 at 21:27
  • Why should we show something for all $n$ that is not depending on $n$? What prevents $v=0$? – Hagen von Eitzen Mar 05 '13 at 21:29
  • If v is 0, then every other expression will evaluvate to 0 as its built from v. v is just one base expression the rest of the set is built from, – user65065 Mar 05 '13 at 21:31
  • e is an expression built from v. so the first e can be (v+v), e' can be e * v which is (v+v)*v – user65065 Mar 05 '13 at 21:40
  • how do we know "x*y < x+y"? –  Mar 05 '13 at 21:50
  • Yes, that should be the other way around: $x*y>x+y$ for $x,y>2$. – Berci Mar 05 '13 at 22:52

1 Answers1

0

I supposed that you wanted to prove the $\forall e\in S,\exists a,b\in \mathbb{N},s.t. e\leq a(v^b)$. Is that the correct question?

I also supposed here that $v\geq 1$, if that not the case you should adapt the proof for the other cases.

This is an induction proof so you should check for the base case: $e=v\leq v=1*v^1$ ok

For the constructor case: two different cases: either (1) $e=(x+y)$ or (2) $e=(x*y)$. By induction hypothesis we know that there are $a_x,a_y,b_x,b_y\in \mathbb{N},s.t. x\leq a_x(v^{b_x})$ and $y\leq a_y(v^{b_y})$.

Case (1): $e=(x+y)\leq a_x(v^{b_x})+ a_y(v^{b_y})\leq (a_x+a_y)(v^{max(b_x,b_y)})$

Case (2): $e=(x*y)\leq a_x(v^{b_x})* a_y(v^{b_y})= (a_x*a_y)(v^{b_x+b_y})$

That is, there is a simpler solution taking $b=0$ then the proof is easier ....

Hope it helped

wece
  • 2,732