2

Can transitivity property be applied for infinite number of times for a certain problem??

girl101
  • 333
  • 1
    Not without other assumptions. Transitivity is a binary relation, and so can be done any finite number of times by induction. – Adam Hughes Jul 28 '14 at 16:40
  • http://math.stackexchange.com/questions/880681/since-2n-o2n-1-does-the-transitivity-of-o-imply-2n-o1 this is the problem, can transitivity be applied for infinite number of times in this case? – girl101 Jul 28 '14 at 16:41
  • 1
    Proofs are finite, so you can't really apply it infinitely many times... – Zhen Lin Jul 28 '14 at 16:44

3 Answers3

3

Not in general. There are a few problems. First, equivalence relations are generally defined in sets, and we in general won't have any structure there capable of dealing with "infinite applications". We might have the idea of a sequence $a_1,a_2,...,a_k,...$ of points such that $a_k \sim a_{k+1}$. Immediately, without any structure, we know thatif $\sim$ was an equivalence relation then $a_1 \sim a_k$ for every $k$. Perhaps if we worked in some topological scenario we might ask whether, if $\lim\limits_{k \to\infty} a_k = a$ exists then $a_1 \sim a$. But this s false in general, even for equivalence relations defined in terms of the topology. Example, we might say $x \sim y$ if there is a path connecting them, this gives an equivalence relation. But, the topologist's sine curve gives an example where we can find a sequence of points $a_k \to a$ (here let $a$ be the origin) where we can connect each to the next by a path, but there is no path to the limit.

In the example given in your above post, there are also a few problems: (1) You're looking at the sequence of functions $f_k(n) = 2^{n-k}$ where, for each function, $k$ is fixed, and $n$ varies. You observe that $f_k = O(f_{k+1})$ as $$f_k(n) \leq 2f_{k+1}(n)$$

But we have some trouble here. What do you mean by a limiting case? Pointwise convergence? well sure, then $f_k \to 0$ pointwise. But this doesn't preserve the $O$ structure. , because at each step we need to add in an extra factor of two, so any finite number of steps there is still a finite constant, so $f_0 = O(f_k)$ for every $k$. But as we go to the limit, the constant from the $O$ gets bigger, such that no finite constant works in the limit.

jxnh
  • 5,228
1

Transitivity can be applied an arbitrary, but finite number of times.

If $R$ is a transitive relation on a set $X$ and you have $\{x_i\}_{i\in \mathbb N}\subset X$ so that $x_nRx_{n+1}$ for any $n$, then you know that all the $x_i$ are in relation $R$

$$\forall i,j \qquad x_iRx_j$$

This is basically induction.

Now, the problem you linked is different. There you have a notion of "limit". Indeed you had a sequence of functions $f_k(x)=2^{x-k}$. Any two of them are in the same big-O class, but their pointwise limit as $k\to\infty$, which is the constant function zero, is not in the class.

In conclusion, if you want to use a transitive relation mixed with limits, you must require an additional property on $R$, say

$$\forall i,j\ \ x_jRx_i\text{ AND } \lim x_i=x_\infty\qquad\Rightarrow \qquad x_iRx_\infty$$

Adam Hughes
  • 36,777
user126154
  • 7,551
  • 3
    I would object to this being "infinite". There's a fairly common misconception about induction that it allows one to travel to the limit. Induction doesn't allow us to do things infinitely many times. It allows us to do them arbitrarily finitely many times. – jxnh Jul 28 '14 at 17:04
  • 1
    an example of such use is the usual order relation on $\mathbb R$. If $x_1\leq x_2\leq x_3\dots$ and $\lim x_i=x$ then forall $i$ you have $x_i\leq x$ – user126154 Jul 28 '14 at 17:05
  • @JHance ok, this could not be an infinite use, but then the Zhen Lin comment applies as "proofs are finite" – user126154 Jul 28 '14 at 17:07
  • 1
    I personally dislike the edit that changed my answer from "infinitely" to "arbitrary but finite". If we want to be burbakist, we should note that transitivity is a property of a relation, not something that can be applied. This viewpoint probably make evreybody happy. I won't edit the answer because I don't want to encourage a debat which, in my opinion, is not the core of the OP. – user126154 Jul 30 '14 at 10:20
0

No

Take $1\sim (0,1)$ but $1>0$

You have $1\sim 1/2\sim 1/2^2\sim 1/2^3\sim...$

But at the limit, $1>0$.

To have "infinite transitivity", I think you at least need the $\sim$ to be a closed set.

dodo
  • 766