How many times can transitivity property be applied

Question

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

Answer 1

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.

Answer 2

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$$

Answer 3

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.