I am trying to solve the exercise problem in Marker's model theory. Here is a problem:
Consider the language $\mathcal{L} = \{R\}$, where $R$ is a binary relation symbol. For each $f\in{}^{\omega\times\omega}2$ define $$R_f = f^{-1}(\{1\}) = \{(a,b): f(a,b)=1\}.$$ Then $(\mathbb{N}, R_f)$ is a $\mathcal{L}$-structure. We can act a symmetric group of $\mathbb{N}$ to ${}^{\omega\times\omega}2$ by letting $\sigma(f)(a,b) = f(\sigma(a),\sigma(b))$ for $f\in{}^{\omega\times\omega}2$. We say a subset $X$ of ${}^{\omega\times\omega}2$ is invariant if $$f\in X \iff \sigma(f)\in X.$$
Show that every invariant Borel subset of ${}^{\omega\times\omega}2$ is of the form $X_\phi = \{f\in {}^{\omega\times\omega}2 : (\mathbb{N},R_f)\models \phi\}$ for some $\mathcal{L}_{\omega_1,\omega}$-sentence $\phi$.
I have tried to show it by proving more general statement: I guess that every Borel subset is of the form $X_{\phi(\vec{a})}$ for some formula $\phi$ with a parameter $\vec{a}\in\mathbb{N}^{<\omega}$. However I am stuck in the countable union. According to the definition of $\mathcal{L}_{\omega_1,\omega}$-formula, I can't use the infinite variables in a single formula, but it needs for countable union in my attempt.
Is there an idea to evade the problem? I would appreciate your help.