I was thinking about this question:
Is this the right notion of "relatively arithmetical"?
and I was wondering what would happen if we took 2 properties, one $\Pi^0_n$ and one $\Sigma^0_m$, and identified classes of structures in the following way: you have one situation checking for the first property and then the second, while, separately, you check for the second and then the first.
According to the answer, assuming we use the information from each oracle positively and negatively, we get a $\Sigma^0_{m+n}$-complete set in the first situation, but a $\Pi^0_{m+n}$-complete set in the second situation.
This seems intuitively troubling. How could checking for the same 2 properties in different orders yield different complexities?
EDIT: It is not true that “According to the answer...” one gets what i claimed, but it is interesting to wonder nonetheless.