Skip to content
The Lumenary

Practice · Advanced undergraduate

Completeness, compactness and Löwenheim–Skolem

Completeness, compactness and Löwenheim–Skolem

Warm-upHuman

Which statement is Gödel's completeness theorem (as opposed to soundness, or to the incompleteness theorem)?

Choose one

Completeness, compactness and Löwenheim–Skolem

CoreHuman

Which of these classes of structures are first-order axiomatisable (by a possibly infinite set of sentences)? Select all.

Choose all that apply

Completeness, compactness and Löwenheim–Skolem

Warm-upHuman

Colour the numbers 0,1,…,90, 1, \dots, 9 with 33 colours so that numbers differing by 11 or by 22 get different colours. How many such colourings are there?

Completeness, compactness and Löwenheim–Skolem

CoreHuman

In the Henkin proof, why do we add a witness constant cφc_\varphi and the axiom ∃x φ(x)→φ(cφ)\exists x\, \varphi(x) \to \varphi(c_\varphi) for every formula φ\varphi?

Choose one

Completeness, compactness and Löwenheim–Skolem

CoreHuman

Suppose TT axiomatised the torsion groups, and let Γ=T∪{cn≠e∣n≥1}\Gamma = T \cup \{c^n \neq e \mid n \ge 1\}. Why is every finite subset of Γ\Gamma satisfiable?

Choose one

Completeness, compactness and Löwenheim–Skolem

StretchHuman

Let M≡(N,0,1,+,×,<)M \equiv (\N, 0, 1, +, \times, <) contain an element cc larger than every numeral. Which statements are true? Select all.

Choose all that apply

Completeness, compactness and Löwenheim–Skolem

CoreHuman

A countable model (M,E)(M, E) of ZFC contains an element pp that MM believes is P(ω)\mathcal P(\omega), and M⊨M \models "pp is uncountable". Yet pp has only countably many EE-members. What is the correct resolution?

Choose one

Completeness, compactness and Löwenheim–Skolem

CoreFormal

Mathlib defines T.IsFinitelySatisfiable as ∀ T0 : Finset L.Sentence, ↑T0 ⊆ T → (↑T0 : L.Theory).IsSatisfiable. Which Lean statement is the compactness theorem?

Choose one

Completeness, compactness and Löwenheim–Skolem

StretchComputational

Numbers i,ji, j are joined when ∣i−j∣∈D|i - j| \in D. Write first_empty_level(k, D, max_n) returning the least n≤n \le max_n such that {0,…,n−1}\{0, \dots, n - 1\} has no proper kk-colouring, or None if every n≤n \le max_n has one. (Build the colourings level by level: each proper colouring of {0,…,n−1}\{0, \dots, n - 1\} is extended by a colour for nn that differs from the colours of n−dn - d, d∈Dd \in D.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.