I am thinking about a structure (in terms of predicate logic), where we have a carrier set A and some relations over A (no functions). I am thinking about all the automorphisms for that structure.
I decided to define the binary relation $E(x,y)$ over A, such that $E(x,y)$ holds, when there exists an automorphism $f$, such that $f(x)=y$.
Is such E an equivalence relation? (to me, it seems like it is). Does such relation E have any specific mathematical name?
It also works for structures with functions. Most structures would have no automorphisms (just the identity), so E would be the equality (not interesting). But in many cases, E can create interesting equivalence classes on the carrier set (two elements of A are in the same equivalence class, when they have the same "role" within a structure).
This is called the orbit equivalence relation.
More generally, suppose we have a group $G$ acting on a set $X$. Then we get an equivalence relation on $X$ given by this action, the orbit equivalence relation, where $$x\sim y\quad\iff\quad\exists g\in G: gx=y.$$ The orbit of an element $x\in X$ with respect to this action is the set $\{gx: g\in G\}$. Obviously different groups, or even different actions by the same group, can give rise to different orbit equivalence relations.
In the particular case you describe, $X$ is the underlying set of some structure $\mathfrak{X}$ and $G$ is the group of automorphisms of $\mathfrak{X}$ acting on $X$ in the obvious way.