index.md (1986B)
1 +++ 2 template = 'page-math.html' 3 title = 'Definability and Undefinability results' 4 +++ 5 # Definability and Undefinability results 6 expressible frame properties in predicate/modal logic: 7 8  9 10 ## for model cardinality 11 model cardinality: 12 13  14 15 16 for all models M and all n ≥ 2 it holds that: 17 * M ⊨ Φn ⇔ A has at least n elements 18 * M ⊨ ψn ⇔ A has at most n elements 19 * M ⊨ Φn ∧ ψn ⇔ A has precisely n elements 20 21 model infiniteness is definable by a set of formulas Δ: 22 * M ⊨ Δ ⇔ M has an infinite domain 23 24 model finiteness is undefinable (single formula): 25 * there's no sentence ψ such that 26 * all M: M ⊨ ψ ⇔ M has a finite domain 27 28 model finiteness is undefinable (set of formulas): 29 * there's no set of formulas Γ such that 30 * all M: M ⊨ Γ ⇔ M has a finite domain 31 32 mode infiniteness is undefinable (single formula) 33 * there's no sentence ψ such that 34 * all M: M ⊨ ψ ⇔ M has infinite domain 35 36 ## for reachability 37 "v is reachable via R from u". thinking of R as arrows, it means that there's a path from v to u. 38 39 search for formulas χn that express reachability in n steps: 40 41 Reachable in n steps: 42 1. u = v 43 2. R(u,v) 44 3. ∃x₁ (RU, x₁) ∧ R(x₁, v)) 45 4. ∃x₁ ∃x₂ (R(u, x₁) ∧ R(x₁, x₂) ∧ R(x₂, v)) 46 5. .... 47 48 shorthand: χ₂(c,d) denotes formula ∃x₁ (R(c, x₁) ∧ R(x₁, d)) 49 50  51 52 reachability is undefinable: 53 54  55 56 57 Let R be a binary relation symbol. 58 1. In predicate logic, reachability by R-steps is 59 * not definable by a sentence 60 * not definable by a set of sentences 61 2. In predicate logic, unreachability by R-steps is 62 * not definable by a single sentence 63 * definable by a set of sentences 64 65 ## General overview 66  67