Subsequence conditions

[littlemathquark]

Homework Statement

Let $a_n$ be a sequence with $(a_n)=(1,0,1,0,1,...)$ . İf $n=2k-1$ then $a_n=1$, $n=2k$ then $a_n=0$ so any subsequence consists of $0$ or $1$ element can be a subsequence of $(a_n)$ sequence?

Relevant Equations

None

For example $(0,0,1,0,0,0,0,1,1,1,..)$ is a subsequence? I think it is not a subsequence and a rule must be given? İs it true? Thank you.

 

[pasmith]

Homework Statement: Let $a_n$ be a sequence with $(a_n)=(1,0,1,0,1,...)$ . İf $n=2k-1$ then $a_n=1$, $n=2k$ then $a_n=0$ so any subsequence consists of $0$ or $1$ element can be a subsequence of $(a_n)$ sequence?
Relevant Equations: None

For example $(0,0,1,0,0,0,0,1,1,1,..)$ is a subsequence? I think it is not a subsequence and a rule must be given? İs it true? Thank you.

Is an arbitrary sequence of 1 and 0 a subsequence? Yes: There is no largest odd number and there is no largest even number, so you can always take the next odd index if you want a 1 and the next even index if you want a 0.

 

[nuuskur]

For example $(0,0,1,0,0,0,0,1,1,1,..)$ is a subsequence? I think it is not a subsequence and a rule must be given? İs it true? Thank you.

This is a subsequence by definition. Sure you can specify by some rule how you obtained it, but the original sequence contains both $1$ and $0$ infinitely often. So any binary sequence is a subsequence.

If the initial sequence contained only finitely many of $1$, say, then a binary sequence with infinitely many of $1$ could not be a subsequence.

 

[FactChecker]

I think it is not a subsequence and a rule must be given? İs it true?

That's a good question. Having a rule is convenient, but not necessary for either a sequence or subsequence. A sequence can be anything in order, even a bunch of nonsense symbols, and any part of that in the same order (allowing skips) is a subsequence of it.

 

[WWGD]

Look at the sequence as a set( indexed by the Natural numbers) . A subsequence is just a subset . As pointed out, given you have infinitely many 1s, infinitely many 0's, any subset of 1s and 0s would be a subsequence.

 

[nuuskur]

For the record, a sequence $(b_n)$ is a subsequence of $(a_n)$ if
$$(\forall n\in\mathbb N)(\exists m\in\mathbb N)(m\geqslant n\quad\mbox{and}\quad b_n = a_m).$$
edit: nope, this is false

There need not be any pattern to picking the elements from the initial sequence. We could pick a subsequence at prime indices. Nobody knows what this subsequence looks like in general (in this case it's just $0,1,1,1,\ldots$), but it is nonetheless a subsequence.

 

[littlemathquark]

Look at the sequence as a set( indexed by the Natural numbers) . A subsequence is just a subset . As pointed out, given you have infinitely many 1s, infinitely many 0's, any subset of 1s and 0s would be a subsequence.

I don't agree that "a subsequence is just a subset". For instance $a_n=(1/n)$ and let $b_n=(1,1/3,1/2,1/4,/1/5,...)$. $b_n$ is a subset of $a_n$ but not a subsequence of $a_n$.

 

[nuuskur]

You are correct, but in his defense, he didn't say any subset is a subsequence.

"A subset is a subsequence" and "A subsequence is a subset" are not equivalent statements.

It is helpful to think of sequences of real numbers as functions $\mathbb N\to\mathbb R$.

 

[FactChecker]

For the record, a sequence $(b_n)$ is a subsequence of $(a_n)$ if
$$(\forall n\in\mathbb N)(\exists m\in\mathbb N)(m\geqslant n\quad\mbox{and}\quad b_n = a_m).$$
There need not be any pattern to picking the elements from the initial sequence. We could pick a subsequence at prime indices. Nobody knows what this subsequence looks like in general (in this case it's just $0,1,1,1,\ldots$), but it is nonetheless a subsequence.

I don't see that this specifies that the ordering of the subsequence is compatible with the ordering of the original sequence. Isn't that necessary? Also, IMO the nature of the equality is not clear when several of the elements of the sequence are equal, but I can not think of an example where this is an obvious problem.

 

[nuuskur]

Indeed, you are right, #6 is not quite correct. Thanks! $(b_n)$ is a subsequence of $(a_n)$ if there exists a strictly increasing sequence $(k_n)$ of natural numbers such that $b_n = a_{k_n}$ for every $n\in\mathbb N$.

 

[littlemathquark]

For the record, a sequence $(b_n)$ is a subsequence of $(a_n)$ if
$$(\forall n\in\mathbb N)(\exists m\in\mathbb N)(m\geqslant n\quad\mbox{and}\quad b_n = a_m).$$
edit: nope, this is false

There need not be any pattern to picking the elements from the initial sequence. We could pick a subsequence at prime indices. Nobody knows what this subsequence looks like in general (in this case it's just $0,1,1,1,\ldots$), but it is nonetheless a subsequence.

Thank you, I got it. You mean there are functions that we can't write its invers functions but indeed there is an inverse function. For instance closed functions like $f(x)=x^5+x+1$ and we can't write inverse function of it or we can give inverse trigonometric functions as an another example. İs it related with axiom of choice? I mean there is a choice function but we can't know its rule.

 

[WWGD]

I believe a subsequence of an infinite sequence may be finite. You may represent it

I don't agree that "a subsequence is just a subset". For instance $a_n=(1/n)$ and let $b_n=(1,1/3,1/2,1/4,/1/5,...)$. $b_n$ is a subset of $a_n$ but not a subsequence of $a_n$.

Well, it's a sequence and a subset. Saying it's a subset is correct. This doesn't imply _ any_ subset is a sequence. It must also preserve the order.Sequences are infinite; indexed by the Naturals. Yes, I should have been more precise in a Math subforum. Still, you, @PeroK draw the conclusion.

 

[WWGD]

For the record, a sequence $(b_n)$ is a subsequence of $(a_n)$ if
$$(\forall n\in\mathbb N)(\exists m\in\mathbb N)(m\geqslant n\quad\mbox{and}\quad b_n = a_m).$$
edit: nope, this is false

There need not be any pattern to picking the elements from the initial sequence. We could pick a subsequence at prime indices. Nobody knows what this subsequence looks like in general (in this case it's just $0,1,1,1,\ldots$), but it is nonetheless a subsequence.

Well, as long as the ordering is preserved, though, which I think you meant and is obvious to some from the context. In our case it's not necessary to specify.

 

[PeroK]

I don't agree that "a subsequence is just a subset". For instance $a_n=(1/n)$ and let $b_n=(1,1/3,1/2,1/4,/1/5,...)$. $b_n$ is a subset of $a_n$ but not a subsequence of $a_n$.

You're correct. A sequence is a function from the natural numbers to some range. Usually the real numbers. The sequence is then a subset of the Cartesian product of the domain and the range. That is, a subset of $\mathbb N \times \mathbb R$. The condition for a sequence (or for any function) is that there is precisely one member of the set for every natural number ( in general, for every member of the domain).

A subsequence is then a subset of this product set.

 

[PeroK]

Look at the sequence as a set( indexed by the Natural numbers) . A subsequence is just a subset . As pointed out, given you have infinitely many 1s, infinitely many 0's, any subset of 1s and 0s would be a subsequence.

This is simply wrong. Sets cannot have the same element twice. The set $\{1,1, 1,\dots \}$ is equal to the singleton set $\{1\}$.

 

[SSequence]

I was thinking about the logical definition of sub-sequence using quantification on $\mathbb{N}$ alone. We are given sequences $\{a_m\}$ and $\{b_n\}$ and we want to determine whether the sequence $\{b_n\}$ is a sub-sequence of $\{a_m\}$ or not.

Yesterday I was thinking about it and came up with an expression for it. However, I realized before posting that the expression was clearly not right.

Today I thought about another expression. This expression does look better than one I thought yesterday. And it looks sort of right to me , but I have to admit that I am not really that certain. The expression is [quantification on $\mathbb{N}$ is assumed over all occurrences of quantifiers]:
$\forall n \exists m [\,\, b_n=a_m \, \land \, \forall j<n \, \exists i<m \, [\, b_j=a_i \,] \,]$

I would like to know others' thoughts on it. Also, if someone finds a concrete example showing that the expression is [or may be] incorrect please do post it.


Brief Note:
Re-call the following [quantification on $\mathbb{N}$ assumed]:
$\forall i<100 \,[\,P(i)\,]$ can be written in an equivalent way as $\forall i \in \mathbb{N} \,[\,(i<100) \rightarrow P(i)\,]$
$\exists i<100 \,[\,P(i)\,]$ can be written in an equivalent way as $\exists i \in \mathbb{N} \,[\,(i<100) \land P(i)\,]$

 

[PeroK]

I was thinking about the logical definition of sub-sequence using quantification on $\mathbb{N}$ alone. We are given sequences $\{a_m\}$ and $\{b_n\}$ and we want to determine whether the sequence $\{b_n\}$ is a sub-sequence of $\{a_m\}$ or not.

One approach is to use the concept of a subsequence of $\mathbb N$, i.e. a strictly increasing sequence of natural numbers. Then $\{b_n\}$ is a subsequence of $\{a_m\}$ iff there exists a subsequence of $\mathbb N$, which we can denote as $\{n_k\}$, such that:
$$\forall k \in \mathbb N: a_{n_k} = b_k$$

 

[SSequence]

Yeah you are right about that. This is the natural precise definition when one is using semi-formal prose as commonly used in math texts. Post#10 also mentioned this definition. I was just thinking about extra restriction of not using a sequence such as $\{n_k\}$ directly and then only relying on $\mathbb{N}$ quantification.

Extra Note:
I think perhaps (if I haven't missed something here) you meant to write $\{n_k\}$ as sub-sequence of the function $I:\mathbb{N} \rightarrow \mathbb{R}$ [instead of $\mathbb{N}$ that is]. Here we have:
$I(x)=x$ for all $x \in \mathbb{N}$
That's because if we think of set of sequences (in $\mathbb{R}$) as synonymous to functions from $\mathbb{N}$ to $\mathbb{R}$ [which you also mentioned already before] then it might be better to phrase it this way.

 

[Gavran]

One approach is to use the concept of a subsequence of $\mathbb N$, i.e. a strictly increasing sequence of natural numbers. Then $\{b_n\}$ is a subsequence of $\{a_m\}$ iff there exists a subsequence of $\mathbb N$, which we can denote as $\{n_k\}$, such that:
$$\forall k \in \mathbb N: a_{n_k} = b_k$$

$\mathbb{N}$ is a set and it is okay to say “a subset of $\mathbb{N}$” but to say “a subsequence of $\mathbb{N}$” can be confusing. A more appropriate phrase is “a subsequence in $\mathbb{N}$”. Even in the case of the phrase “a subsequence in $\mathbb{N}$” it does not mean that there is a strictly increasing sequence of natural numbers. So in your definition I would rather use only the phrase “a strictly increasing sequence of natural numbers”. See the post #10.