Working with uncountable structures of fixed cardinality, we investigate the complexity of certain equivalence relations and show that if, then many of them are ‐complete, in particular the isomorphism relation of dense linear orders. Then we show that it is undecidable in whether or not the isomorphism relation of a certain well behaved theory (stable, NDOP, NOTOP) is ‐complete (it is, if, but can be forced not to be).

Answering some of the main questions from [L. Motto Ros, The descriptive set-theoretical complexity of the embeddability relation on models of large size, Ann. Pure Appl. Logic164(12) (2013) 1454–1492], we show that whenever κ is a cardinal satisfying κ<κ=κ>ω, then the embeddability relation between κ-sized structures is strongly invariantly universal, and hence complete for (κ-)analytic quasi-orders. We also prove that in the above result we can further restrict our attention to various natural classes of structures, including (generalized) trees, graphs, or (...) groups. This fully generalizes to the uncountable case the main results of [A. Louveau and C. Rosendal, Complete analytic equivalence relations, Trans. Amer. Math. Soc.357(12) (2005) 4839–4866; S.-D. Friedman and L. Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symbolic Logic76(1) (2011) 243–266; J. Williams, Universal countable Borel quasi-orders, J. Symbolic Logic79(3) (2014) 928–954; F. Calderoni and L. Motto Ros, Universality of group embeddability, Proc. Amer. Math. Soc.146 (2018) 1765–1780]. (shrink)