# Mathematical logic and the induction principle

Question:

Let UU be the set of all sequences of positive integers, let B={⟨1,2,3,…⟩}B = \{\langle1,2,3,…\rangle\}, let S(⟨s1+1,s2,…⟩)=⟨1,s1,s2,…⟩ S (\langle s_1 + 1,s_2,…\rangle) = \langle 1, s_1, s_2,…\rangle, and let I(⟨s1,s2,…⟩)=⟨s1+1,s2,…⟩I(\langle s_1,s_2,…\rangle) = \langle s_1 +1,s2,…\rangle. Let CC be the set generated from BB by SS and II.

(a) Use the induction principle to prove that for every ⟨s1,s2,…⟩∈C\langle s_1,s_2, …\rangle \in C there exists an integer n0≥2n_0 \ge 2 such that sn0+n=n+2s_{n_0 +n} =n+2 for all n≥0n \ge 0.

(b) Does the converse to (a) hold? That is, if such an n0n_0 exists, is ⟨s1,s2,…⟩\langle s_1, s_2, …\rangle necessarily in CC?

(c) Is CC freely generated from BB by SS and II? Justify your answer.

My attempt:

For part (c) I am fairly certain that it is freely generated since S∩B=∅S \cap B = \varnothing. Like wise it seems apparent the S∩I=∅S \cap I = \varnothing, and I∩B=∅I \cap B = \varnothing Also SS and II are injective. I won’t give the argument for pairwise disjoint unless I am challenged and I think the injectivity is pretty obvious.

My real difficulties are with parts (a) and (b). I think for part (a) I need to use some composition of SS and II but I ‘m not having much luck with it.

Any advice will be appreciative. Thank you.

=================

– DanielV
2 days ago

@DanielV II is a function that maps UU into UU by the rule in the question.
– Mike
2 days ago

=================

2

=================

HINT: For (b) I suggest proving that if σ=⟨sn:n∈Z+⟩\sigma=\langle s_n:n\in\Bbb Z^+\rangle, then there is an m∈Z+m\in\Bbb Z^+ such that sn≤ns_n\le n for each n≥mn\ge m. You can do this by structural induction of the kind that Mees de Vries suggests for (a); Iâ€™ll do this one and leave that one for you. First, though, Iâ€™ll try to explain the intuition behind this approach.

Let σ=⟨sn:n∈Z+⟩∈U\sigma=\langle s_n:n\in\Bbb Z^+\rangle\in U. The operation II affects only s1s_1. The operation SS is a little more complicated, but the important thing right now is that it pushes each term except the first one place further along in the sequence, so that sns_n becomes the (n+1)(n+1)-st term of S(σ)S(\sigma) for n≥2n\ge 2. That is, if S(σ)=⟨tn:n∈Z+⟩S(\sigma)=\langle t_n:n\in\Bbb Z^+\rangle, then tn=sn−1t_n=s_{n-1} for n≥3n\ge 3. This means that if there is an m∈Z+m\in\Bbb Z^+ such that sn≤sn+1s_n\le s_{n+1} for n≥mn\ge m, then tn=sn−1≤snt_n=s_{n-1}\le s_n for n≥m+1n\ge m+1, and tn≤tn+1t_n\le t_{n+1} for n≥m+1n\ge m+1. In other words, if σ\sigma is eventually increasing, so is S(σ)S(\sigma), and from some point on the nn-th term of S(σ)S(\sigma) is less than or equal to the nn-th term of σ\sigma.

Since the initial sequence ⟨n:n∈Z+⟩\langle n:n\in\Bbb Z^+\rangle is increasing, this means that any sequence ⟨sn:n∈Z+⟩\langle s_n:n\in\Bbb Z^+\rangle that we can get from it by applying II and SS some finite number of times should have a tail that is at or below the corresponding tail of the initial sequence: there should be an m∈Z+m\in\Bbb Z^+ such that sn≤ns_n\le n for each n≥mn\ge m.

This is certainly the case for the initial sequence: it has sn=ns_n=n for each n∈Z+n\in\Bbb Z^+. Suppose that σ=⟨sn:n∈Z+⟩\sigma=\langle s_n:n\in\Bbb Z^+\rangle has this property, and let m∈Z+m\in\Bbb Z^+ be such that sn≤ns_n\le n for each n≥mn\ge m.

Let I(σ)=⟨tn:n∈Z+⟩=⟨s1+1,s2,s3,…⟩;I(\sigma)=\langle t_n:n\in\Bbb Z^+\rangle=\langle s_1+1,s_2,s_3,\ldots\rangle\;; then tn=snt_n=s_n for n≥2n\ge 2, so tn≤nt_n\le n for n≥max{2,m}n\ge\max\{2,m\}.
Now suppose that s_1>1s_1>1, and let S(\sigma)=\langle t_n:n\in\Bbb Z^+\rangle=\langle 1,s_1-1,s_2,s_3,\ldots\rangle\;;S(\sigma)=\langle t_n:n\in\Bbb Z^+\rangle=\langle 1,s_1-1,s_2,s_3,\ldots\rangle\;; then t_n=s_{n-1}t_n=s_{n-1} for n\ge 3n\ge 3, and s_{n-1}\le n-1s_{n-1}\le n-1 for n-1\ge mn-1\ge m, so t_n\le nt_n\le n for n\ge\max\{3,m+1\}n\ge\max\{3,m+1\}.

It follows by induction that every sequence in CC has this property.

Now find a sequence \langle s_n:n\in\Bbb Z^+\rangle\in U\langle s_n:n\in\Bbb Z^+\rangle\in U such that there is an integer n_0\ge 2n_0\ge 2 such that s_{n_0+n}=n+2s_{n_0+n}=n+2 for all n\ge 0n\ge 0, but there is no m\in\Bbb Z^+m\in\Bbb Z^+ such that s_n\le ns_n\le n for all n\ge mn\ge m. There is at least one very simple example that Iâ€™ve left in the spoiler-protected box below in case you get completely stuck.

\langle 2,3,4,\ldots\rangle\langle 2,3,4,\ldots\rangle

Thank you everyone, I was able to solve it. It turned out that it wasn’t as hard as I thought, just took a bit to digest the notations. I’ll leave it up in case it helps someone else out.
– Mike
22 hours ago

@Mike: You’re welcome. (That was pretty much my reaction, too: it took a little while to see what was going on, but then it wasn’t bad.)
– Brian M. Scott
20 hours ago

Hint for (a): To apply induction here, you must show that the unique element b \in Bb \in B has the described property; and then, if some sequence cc has the property, so do S(c)S(c) and I(c)I(c).

Hint for (b): Try constructing the sequence \langle s_1,\ldots\rangle\langle s_1,\ldots\rangle from bb using only SS and II. Can you do it?