Given a quasi-ordered set $(X,\lesssim)$, we can define that for $a,b \in X$ we have $$a \sim b \;\Leftrightarrow\; a \lesssim b \;\wedge\; b \lesssim a.$$
and thereby obtain a partially ordered set $Y$ with underlying set $X / \!\sim$ and order relation defined in the obvious way. Call $Y$ the skeleton of $X$. Say that two quasi-ordered sets are equivalent iff their skeletons are isomorphic.
Is it true that for any two quasi-ordered sets $X$ and $Y$ such that $X$ and $Y$ are equivalent, we have that for every sentence $\phi$ of first-order logic (without equality) in the language of $\lesssim$ only (so in particular, equality is disallowed), $X$ satisfies $\phi$ iff $Y$ satisfies $\phi$?
If so, how do we generally go about proving this sort of thing?
First of all note that we only have to check that each quasi order, $X$, is elementary equivalent to its skeleton $X / \sim$. It follows by the transitivity of elementary equivalence that equivalent quasi orders are elementary equivalent.
Let $\pi : X \rightarrow X / \sim$ be the projection map. For each formula $\phi$ in the language of quasi orders with parameters from $X$, let $\phi^\pi$ be the formula obtained by replacing each parameter $x$ by $\pi(x)$ (so $\phi^\pi$ is a formula with parameters from $X / \sim$). We show by induction on formulas that $X \models \phi$ if and only if $X / \sim \; \models \phi^\pi$. Note that we only need to check closed formulas that have been constructed from atomics, conjunction, negation and universal quantification since every formula is equivalent to one of this form.
First suppose that $\phi$ is atomic. Then it is of the form $x \lesssim y$ for $x, y \in X$. However, this is clearly true if and only if $\pi(x) \lesssim \pi(y)$ by the definition of $X / \sim$.
Next suppose that $\phi$ is of the form $\forall u \; \psi(u)$. Suppose further that $X \models \forall u \; \psi(u)$. Now, since $\pi$ is a surjection we know that any element of $X / \sim$ is of the form $\pi(x)$ for some $x \in X$. By induction we can assume that $X \models \psi(x)$ if and only if $X / \sim \; \models \psi^\pi(\pi(x))$. But this means we can deduce $X / \sim \; \models \forall u \; \psi^\pi(u)$, ie $X / \sim \; \models \phi^\pi$.
Conversely, suppose that $X / \sim \; \models \forall u \; \psi^\pi(u)$. Now let $x \in X$. Then $X / \sim \; \models \phi^\pi(\pi(x))$. By induction we may deduce that $X \models \phi(x)$, and hence conclude that $X \models \forall u \; \psi(u)$.
Next suppose that $\phi$ is of the form $\neg \psi$. By induction we may assume that $X \models \psi$ if and only if $X / \sim \; \models \psi^\pi$, but it easily follows that $X \models \neg \psi$ if and only if $X / \sim \; \models \neg \psi^\pi$.
We can similarly deal with the case where $\phi$ is the conjunction of two formulas.
However, we can now put these together by induction to deduce that $X$ is elementary equivalent to $X / \sim$ as required.