A note on the expressive power of linear orders

DOI10.2168/LMCS-7(4:7)2011MaRDI QIDQ3224697zbMATHFDO

Authors Nicole Schweikardt, Thomas Schwentick

Publication date 2 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.5901

zbMATH Keywords

first-order logiclinear ordersexpressivenessBit predicateCrane-Beach property

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classical first-order logic (03B10) Total orders (06A05) Descriptive complexity and finite models (68Q19)

Abstract: This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order logic with a linear order and this permutation is as expressive as FO(Bit).

Recommendations

• The expressive power of Malitz quantifiers for linear orderings
• An axiomatic characterization of linear orders
• Some observations on intuitionistically elementary properties of linear orderings
• Linearization of definable order relations
• On quantifier-rank equivalence between linear orders
• On the representability degrees of linear orders
• On the Linearity of Order-isomorphisms
• ON COHESIVE POWERS OF LINEAR ORDERS
• scientific article; zbMATH DE number 6704685
• The intrinsic enumerability of linear orders

Cited in

(5)

• The expressive power of bijections over weakly arithmetized structures
• On effective linearly ordered sets of comparison functions
• scientific article; zbMATH DE number 68156 (Why is no real title available?)
• ON COHESIVE POWERS OF LINEAR ORDERS
• Two first-order logics of permutations

This page was built for publication: A note on the expressive power of linear orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3224697)