Investigation of binary spectra by explicit polynomial transformations of graphs (Q1318703): Difference between revisions

Let \(L\) be a first-order language with identity whose specific symbols are only binary predicate symbols \(P_ 1,\dots,P_ n\) \((n\in N)\). For any \(L\)-sentence \(\alpha\), \(S(\alpha)\) denotes the set of cardinalities of finite models of \(\alpha\). It is proved that for any \(L\)-sentence \(\alpha\) and any polynomial \(f\) of \(Z[x]\) asymptotically greater than or equal to the identity function on \(N\), there exists an \(L\)-sentence \(\beta\) such that \(S(\beta)= f(S(\alpha))\), and that if \(f\) is of degree \(k\) and \(P_ n\) not contained in \(\alpha\) for \(n\geq q+1\), then \(P_ n\) is not contained in \(\beta\) for \(n\geq 2q+ k\) if \(k<3\) and for \(n\geq q+ k+1\) if \(k\geq 3\).