| dc.contributor.author | Kfoury, A.J. | en_US |
| dc.contributor.author | Wymann-Böni, M. | en_US |
| dc.date.accessioned | 2011-09-12T14:27:46Z | |
| dc.date.available | 2011-09-12T14:27:46Z | |
| dc.date.issued | 1993-08 | |
| dc.identifier.citation | Kfoury, A.J.; Wymann-Boeni, M.. "A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders", Technical Report BUCS-1993-009, Computer Science Department, Boston University, August 1993. [Available from: http://hdl.handle.net/2144/1472] | |
| dc.identifier.uri | https://hdl.handle.net/2144/1472 | |
| dc.description.abstract | We give an explicit and easy-to-verify characterization for subsets
in finite total orders (infinitely many of them in general) to be uniformly definable by a first-order formula.
From this characterization we derive immediately that Beth's definability theorem does not hold in any class of finite total orders, as well as that McColm's first conjecture is true for all classes of finite total orders. Another consequence is a natural 0-1 law for definable subsets on finite total orders expressed as a statement about the possible densities of first-order definable subsets. | en_US |
| dc.description.sponsorship | NSF (CCR-9113196), Swiss National Science Foundation | en_US |
| dc.language.iso | en_US | |
| dc.publisher | Boston University Computer Science Department | en_US |
| dc.relation.ispartofseries | BUCS Technical Reports;BUCS-TR-1993-009 | |
| dc.title | A Characterization of First-Order Definable Subsets on Classes of Finite Total Orders | en_US |
| dc.type | Technical Report | en_US |
