Premium
Random unary predicates: Almost sure theories and countable models
Author(s) -
Spencer Joel H.,
St. John Katherine
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199810/12)13:3/4<229::aid-rsa3>3.0.co;2-x
Subject(s) - unary operation , countable set , mathematics , predicate (mathematical logic) , discrete mathematics , combinatorics , order (exchange) , computer science , finance , economics , programming language
Let U n , p be the random unary predicate and T k be the almost sure first‐order theory of U n , p under the linear ordering, where k is a positive integer and n −1/ k ≪ p ( n )≪ n −1/( k +1) . For each k , we give an axiomatization for the theory T k . We find a model ℳ k of T k of order type roughly that of Z k and show that no other models of T k exist of smaller size. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 229–248, 1998