Data structure for equivalence classes
The best you can do is keep track of all currently known equivalences using a Union-Find data structure.  Initially, each element is in own group.  Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.