Premium
Random sparse unary predicates
Author(s) -
Shelah Saharon,
Spencer Joel
Publication year - 1994
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/rsa.3240050302
Subject(s) - unary operation , limit (mathematics) , zero (linguistics) , mathematics , combinatorics , discrete mathematics , order (exchange) , linguistics , philosophy , mathematical analysis , finance , economics
Random unary predicates U on [ n ] holding with probability p are examined with respect to sentences A in a first‐order language containing U and “less than.” When p = p(n) satisfies n k +1 ≪ 1 ≪ np k it is shown that Pr[ A ] approaches a limit dependent only on k and A . In a similar circular model the limit is shown to be zero or one. © 1994 John Wiley & Sons, Inc.