# Proof related to a finite state machine

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?

• I don't understand your notation, if it is not standard please add details [I may not know this matirial though] Oct 6, 2012 at 2:04

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