Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I have this confusion related to a finite state machine M such that if the number of states n>=2, then there exits i
$ \overset{i}\equiv{}= {\overset{i+1}\equiv{}}$ I mean the $i^{th}$ equivalence class = ${i+1}^{th}$ equivalence class
How can I prove this?
For each $i\in\Bbb N$, $\overset{i}\equiv$ is an equivalence relation on the set of states of the machine, so its equivalence classes form a partition $\pi_i$ of the state set, and $\overset{i+1}\equiv~=~\overset{i}\equiv$ if and only if $\pi_{i+1}=\pi_i$.
If you’re defining these relations in the usual way, $s\overset{i+1}\equiv t$ implies $s\overset{i}\equiv t$, so the partition $\pi_{i+1}$ refines the partition $\pi_i$. That is, each member of $\pi_{i+1}$ is a union of members of $\pi_i$. Thus, if $\pi_{i+1}\ne\pi_i$, then $|\pi_{i+1}|>|\pi_i|$: $\pi_{i+1}$ breaks up the state set into more parts than $\pi_i$ does. But a partition of the state set can have at most $n$ parts, one for each state, so the number of parts can increase at most $n-1$ times, from $1$ to $n$. Thus, it must be the case that $\overset{n+1}\equiv~=~\overset{n}\equiv$.
