A note on the expressive power of linear orders

DOI10.2168/LMCS-7(4:7)2011zbMATH Open1237.03006arXiv1111.5901MaRDI QIDQ3224697FDOQ3224697

Authors: Nicole Schweikardt, Thomas Schwentick 

Publication date: 2 April 2012

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

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).

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

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

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)

Cited In (4)

• The expressive power of bijections over weakly arithmetized structures
• Title not available (Why is that?)
• ON COHESIVE POWERS OF LINEAR ORDERS
• On effective linearly ordered sets of comparison functions

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)