Two questions regarding definability of equicardinality.

Two sets are said to be equicardinal iff there is a bijection between them. I want to know whether equicardinality is definable in first-order logic. More precisely, suppose we are working in the language of two unary predicates $P$ and $Q$. I want to know whether there is a first-order formula in that language that holds precisely when the cardinality of the set of $x$'s such that $P(x)$ is the same as the cardinality of the set of $x$'s such that $Q(x)$. My second question is, what happens if we restrict our attention to finite models? That is, is there a first-order formula in that language such that, when we restrict our attention to finite models, holds precisely when $P$ and $Q$ are equicardinal?

Pure first-order logic can't count very well at all:

In the language consisting of two unary predicates $P,Q$, there is no first-order sentence $\varphi$ whose finite models are exactly those finite $\{P,Q\}$-structures $\mathcal{A}$ satisfying $\vert P^\mathcal{A}\vert=\vert Q^\mathcal{A}\vert$ (and we can replace "$=$" with "$<$" or similar and get the same result).

One way to prove this is with the compactness theorem. The argument is essentially the same as the proof that there is no sentence in the empty language whose finite models are exactly the structures of even cardinality:

Let $\mathcal{X}_n$ be a finite structure with $2n+1$ elements in which $P$ and $Q$ name disjoint sets of respective cardinality $n$ and $n+1$, and let $\mathcal{Y}_n$ be a finite structure with $2n$ elements in which $P$ and $Q$ name disjoint sets of respective cardinality $n$ and $n$.

Now let $\mathcal{X}$ be a countable elementary substructure of any nonprincipal ultraproduct of the $\mathcal{X}_n$s, and let $\mathcal{Y}$ be a countable elementary substructure of any nonprincipal ultraproduct of the $\mathcal{Y}_n$s. It's easy to check that $\mathcal{X}\cong\mathcal{Y}$ (just figure out what each is up to isomorphism). But this means that there is no sentence true in all the $\mathcal{X}_n$s but false in all the $\mathcal{Y}_n$s.

(Note the utility of infinite models even in the study of finite structures!)

Now in a sense the above is actually a pretty bad argument: it uses both Los' theorem and downward Lowenheim-Skolem, so per Lindstrom's theorem doesn't have a good shot at generalizing past first-order logic. To prove that even some stronger logics "can't count in the finite," we need to do more work. It's at this point that techniques from finite model theory come into play, but this is a bit outside my sphere of competence so I'll stop here.

When you consider infinite sets, then not only one sentence, but an entire first-order theory won't tell you that two sets have the same cardinality.

For instance, if you consider models $M$ such that $P$ and $Q$ are disjoint, infinite and every element satisfies either $P$ or $Q$, then all of them are elementarily equivalent, but for some $M$ you have $\lvert P(M)\rvert = \lvert Q(M)\rvert$, while for others you have $\lvert P(M)\rvert \neq \lvert Q(M)\rvert$.

Thus, cardinality is definitely not a first order property, not even in the weak sense. The correct property to consider (when we have a fixed first-order theory) is perhaps the definable cardinality: the relation that holds between two sets when there is a definable bijection between them.

Now, it is easy to see that if $P$, $Q$ are definable sets with the same definable cardinality, then for any model $M$, the sets $P(M)$ and $Q(M)$ also have the same cardinality.

I would like to say that this is a characterisation, but that is not true, unfortunately. For example, you can have a 2-to-1 definable surjection $P\to Q$ or $Q\to P$ for some infinite $Q$ without having any definable bijection, and then it will still be true that $P(M)$ and $Q(M)$ have the same cardinality for all $M$.

For example, if you consider an algebraically closed field with an extra predicate $P$ for an infinite algebraically independent set, then the set $Q$ of square roots of elements of $P$ always has the same cardinality as $P$, even though there is no definable (or even invariant) surjection $P\to Q$.

Worse still, the set $Q$ always has the same cardinality as the set $R$ of all cube roots of elements of $P$, even though one can show that every definable function $Q\to R$ or $R\to Q$ must necessarily have finite range. There is however a natural definable 2-to-3 correspondence between $Q$ and $R$.

There are also examples where there is not even that. For example, suppose $P,P_0,Q,Q_0$ are predicates such that $P_0\subseteq P, Q_0\subseteq P$, both with infinite complements, and we have symbols for bijections $P_0\to Q$ and $Q_0\to Q$. Then by Cantor-Bernstein, for every $M$, the sets $P(M)$ and $Q(M)$ have the same cardinality, but there is no definable finite-to-finite (surjective on both sides) relation between $P$ and $Q$.

In all, cardinality for infinite sets seems to be, in general, hopelessly undefinable.