Elementary equivalent pairs of algebras associated with sets (Q1179767)

The presented results are connected with investigations of Grätzer, Ježek, McKenzie, and Shelah. For any non-empty set \(X\) the full relation algebra on \(X\), the partition lattice on \(X\), the function monoid on \(X\), and the symmetric group on \(X\) are algebras which are naturally associated with \(X\). There arise four classes of models which are classes of structured sets. The appropriate language for these four classes is not a first-order language, but it is in a canonical way equivalent to a first-order language. Two classes of structures \({\mathfrak A}\) and \({\mathfrak B}\) with appropriate languages are bi-interpretable iff there are interpretations from \({\mathfrak A}\) into \({\mathfrak B}\) and conversely. Four pairs of bi-interpretable classes of structures are represented. The second-order equivalence of two nonzero cardinals \(\lambda\) and \(\kappa\) is necessary and sufficient to each of the first- order equivalences of the full relation algebras, the partition lattices, and the function monoids on \(\lambda\) and \(\kappa\), respectively, and each of them implies the first-order equivalence of the symmetric groups on \(\lambda\) and \(\kappa\). There are some other structures associated with sets, for instance the Boolean algebra of all subsets of \(X\), the semilattice of all order relations on \(X\), and the word semigroup on \(X\). The function monoid \({\mathcal M}_ \lambda\) is ultrauniversal in the variety of monoids, if \(\lambda\) is no less than \(\aleph_ 0\). Hence one has the result: For cardinals \(\lambda\), \(\kappa\) no less than \(\aleph_ 0\), the structures \({\mathcal Z_ \lambda}\) and \({\mathcal Z_ \kappa}\) satisfy the same universal and existential sentences, where \({\mathcal Z}\) denotes either the partition lattice, the function monoid or the symmetric group. An algebra \({\mathcal A}\) is called ultrauniversal in an elementary class or a variety \({\mathfrak C}\) iff every member of \({\mathfrak C}\) is embeddable in an ultraproduct of \({\mathcal A}\). Misprints: p. \(329_{3}\) read ``...\(i,j\in I: {\mathcal B}_ i\equiv{\mathcal L}_{\mathcal B}{\mathcal B}_ j\) implies...''; p. \(335^{1}\) read ``... implies \({\mathcal S}_ \lambda\equiv{\mathcal S}_ \kappa\)''.