1

Let $\Sigma$ be an alphabet and $\Sigma^*$ its Kleene closure (the set of all possible finite strings over the alphabet). Also, define the set of prefixes of $x \in \Sigma^*$ by $$ \mathrm{pre}(x) = \{x[1:i] \mid i \in \{1, \ldots, |x|\}\}, $$ where the left associative subslice operator $[m:n]$ indexes into $x$, producing the substring between the indices $m$ and $n$ of the letters in $x$.

Show by constructive induction, that for all $x, y \in \Sigma^*$, if $x \in \mathrm{pre}(y)$, then then the length of the string $|x| \leq |y|$.

An attempt

The base case is easy. The empty string $\epsilon \in \mathrm{pre}(x)$ for all $x \in \Sigma^*$, and $|\epsilon| = 0 \leq |x|$ for all strings $x \in \Sigma^*$. Therefore our base case is valid.

Assume then, that $x, y \in \Sigma^*$, so that $|x| \leq |y|$. But then what? What am I actually supposed to induce? Should I vary the lengths of both $x$ and $y$ in the induction step or what?

I guess I'm asking, what is constructive induction really, and how is it different from weak induction? In weak induction we try to show that if the claim holds for a previous element, then it holds for the following element. In strong induction we assume that the claim holds for all previous elements and deduce that it has to hold for the next element.

But what is the inductve hypothesies in the case of constructive induction?

Edit

The question also has a second part: prove $|xy| + |x| + |y|$. I guess this is where I'm actually supposed to use induction. It's just the question was presented in a way that made me think induction was necessary even in the first part.

Still, my question is still unanswered. What is the inductive hypothesis (in general) when dealing with constructive induction?

sesodesa
  • 701
  • This seems to be a consequence of the definitions rather than of any kind of induction: for each $x \in \Sigma^*$ and each $i \in {1,...,|x|}$ we have $$|x[1:i]| = i \le |x|$$ – Lee Mosher Mar 11 '20 at 17:14
  • @LeeMosher That's my beef, exactly. I mean I guess I could let $x_n, x_{n+1}, y\in \Sigma^*$, where $|x_n| = n$ and $|x_{n+1}| = n+1$, and assume that then $|x_n|\leq |y|$. Now by definition $x_{n+1}[1:n] = x_n$, whose lenght is known to be less or equal to the lenght of $y$. But why would do all this? – sesodesa Mar 11 '20 at 17:30
  • Well, I guess this really comes down to how the natural numbers themselves are axiomatized. One could prove a theorem of the natural numbers which says that if $a,b$ are natural numbers then exactly one of the following is true: $a=b$; or there exists $c$ such that $a+c=b$ (and we say $a<b$); or there exists $c$ such that $a=b+c$ (and we say $b<a$). – Lee Mosher Mar 11 '20 at 17:34
  • Sigh. Well, the question did have a second part (prove $|xy| = |x| + |y|$), where I guess I'm actually supposed to use constructive induction and the result of this first part to my advantage. The way the question was worded led me to believe I needed to use induction even in the first part. But my original question still remains unanswered. What is (in general) the inductive hypothesis in the case of constructive induction. – sesodesa Mar 11 '20 at 18:04
  • The way I'd tend to interpret "constructive induction", I would expect the prefix set to be given an inductive definition such as: $pre : \Sigma^* \to P(\Sigma^*)$ is the minimal function such that $\varepsilon \in pre(x)$ for all words $x$; and for all letters $a$ and words $x$ and $p$, if $p \in pre(x)$, then $ap \in pre(ax)$. Then under constructive induction, what you would need to prove is: $|\varepsilon| \le |x|$ for all $x$; and if $|p| \le |x|$ then $|ap| \le |ax|$. – Daniel Schepler Mar 11 '20 at 18:25
  • Maybe I should have come up with that definition myself, but that is out of my zone of proximal development. – sesodesa Mar 11 '20 at 19:01
  • @DanielSchepler By the way, what is a minimal function? Google didn't give me an answer among the first few links. – sesodesa Mar 11 '20 at 19:09
  • It means that if $f$ is another function satisfying the conditions, then $pre(x) \subseteq f(x)$ for all $x \in \Sigma^*$. – Daniel Schepler Mar 11 '20 at 19:11

0 Answers0