Description
ASSIGNMENT: DO 3 EXERCISES CHOSEN FROM GROUP 1 AND 3 EXERCISES CHOSEN FROM
GROUP 2.
DEADLINE: 29 MARCH 2021.
EVALUATION: THIS IS A PASS OR FAIL EXAM. YOU WILL GET FULL MARKS IF YOU SUBMIT YOUR
SOLUTIONS, WHETHER WRONG OR RIGHT.
1. Group 1
Exercise 1 Let R be a predicate symbol of arity 1. Show that ∃x(R(x) → ∀yR(y)) is logically valid.
Exercise 2 Show that the following sentence is unsatisfiable, where S is any formula with two free
variables: ∃x∀y(S(x, y) ↔ ¬S(y, y)).
Exercise 3 Prove or disprove: for any formulas G and F,
F |= G if and only if |= (F → G).
Exercise 4 Is the following formula logically valid for any formula F and any term t?
∀xF(x) → F(t).
If not, give an example of a formula F, a structure A and an assignment α witnessing this fact.
Exercise 5 Is the following implication true for any choice of formulas? Is it true for sentences?
If
If |= G then |= F,
then
|= (G → F).
Recall that for a formula G, |= G means that for all structures A, for all assignments α in A, A |= G[α].
Exercise 6 Let F be a formula with no quantifiers, function symbols, or constants. Prove the following
two statements.
(1) A closed formula of the form ∀x1 . . . ∀xn∃y1 . . . ∃ymF with m ≥ 0 and n ≥ 1 is valid if and only if it
is true in every non-empty structure with ≤ n elements.
(2) A closed formula (a sentence) of the form ∃y1 . . . ∃ymF is valid if and only if it is true in every
structure with 1 element.
Can we draw some conclusion about the decidability of the validity of formulas in item (1)?
Exercise 7 Let A and B be two structures for the same predicative language with no constant or function
symbols. Prove that if f is a bijection from A to B such that, for all atomic formulas G the following holds
A |= G(x1, . . . , xn)
x1, . . . , xn
a1, . . . , an
if and only if B |= G(x1, . . . , xn)
x1, . . . , xn
f(a1), . . . , f(an)
,
then A and B satisfy the same sentences.
(Hint: Induction of sentences is not a viable option (subformulas of a sentence may not be sentences).
So typically one proves a result about formulas. In this case one would prove by induction on formulas the
following: For any formula F(x1, . . . , xn), for any (a1, . . . , an) ∈ An, A |= F(x1, . . . , xn)[a1, . . . , an] if and
only if B |= F(x1, . . . , xn)[f(a1), . . . , f(an)]. The result for sentences then follows.)
1
Exercise 8 Consider the empty language (only logical symbols, including =, but no further relation,
function or constant symbols).
Can you write a sentence that is true only in finite models? Can you write a sentence that is true only in
infinite models? Can you write a set of sentences X such that all models satisfying X are infinite?
Does any of the answers change if you use the language {<} (one binary relation symbol)?
Exercise 9 In the language L = {<} of DLO, write a sentence that distinguishes (N, <) from (Q, <) i.e.,
that is true in one structure but not in the other.
Exercise 10 Assume that the validity of a sentence in a fixed finite model can be algorithmically decided
(this is indeed the case). Consider the set V of logically valid sentences (in a fixed first-order language)
and the set U of all unsatisfiable sentences. Is there a decision algorithm (i.e. a deterministic 0,1 valued
procedure) that separates V from U in the following sense: V is a subset of the inputs on which the algorithm
A returns 1 and U is a subset of the inputs on which the algorithm A returns 0?
(If your answer is yes, describe (informally) an algorithm that separates the two sets; else if your answer
is no give an informal proof.)
Exercise 11 Let T be a theory (i.e., a set of sentences) in some relational language L. Let F(x) be a
formula in the language L. Let c be a constant symbol not present in the language L. Let L
0 be the language
L ∪ {c}. Show that
T |= ∀xF(x) if and only if T |= F(c).
Note that in the left-hand side we are dealing with structures adequate for L while on the right-hand side
we are dealing with structures adequate for L
0
.
2. Group 2
Definition B is a substructure of A if: B ⊆ A; for every constant symbol c, c
A = c
B, every relation
RB (resp. function f
B) is the restriction of RA (resp. f
A) to B.
Exercise 1 Prove the following two points.
(1) If B is a substructure of A, then for any atomic formula F(x1, . . . , xn), for all b1, . . . , bn in B,
B |= F[b1, . . . , bn] iff A |= F[b1, . . . , bn].
(2) Let T be a set of purely universal sentences (i.e. sentences starting with universal quantifiers followed
by an atomic formula). If B is a substructure of A and A |= T then also B |= T.
Definition B substructure of A is called elementary if for all formulas F(x1, . . . , xn) for all b1, . . . , bn
in B, A |= F[b1, . . . , bn] iff B |= F[b1, . . . , bn]. That is, A and B agree on elements of B.
Exercise 2 Let A1 = (N, +, 0) and A2 = (2N, +, 0) be two structures for the language L = {f, c} where
f is a function symbol of arity 2 and c is a constant symbol and 2N denotes the set of even natural numbers.
A1 and A2 interpret f as the sum on their domains and c as 0. Indicate whether the following are true or
false, giving a short justification of your answer.
(1) A2 is a substructure ofA1.
(2) A1 e A2 are isomorphic.
(3) A1 e A2 satisfy the same sentences in L.
(4) If A1 |= ∃xF(x)[α] for an assignment α in A2, then there exists a ∈ A2 such that A2 |= F(x)[α
x
a
].
(5) If E is a sentence of the form ∀xF(x) with F(x) a quantifier-free formula then:
If A1 |= E then A2 |= E.
(6) If E is a sentence of the form ∃xF(x) with F(x) a quantifier-free formula then:
If A1 |= E then A2 |= E.
Exercise 3 Is the structure Q = (Q, +, ×, 0, 1) a substructure of the structure R = (R, +, ×, 0, 1)? is it
an elementary substructure?
Exercise 4 Prove that the following structures are not isomorphic:
(1) (N, +, ×, 0, 1, <) and (Q, +, ×, 0, 1, <)
(2) (N, <) and (Z, <)
(3) (Q, <) and (R, <).
(Hint: in some case you can use the fact that if A and B are isomorphic then they satisfy the same
sentences).
Exercise 5 A theory T has property M if the following holds: For A and B models of T, if A is
a substructure of B then A is also an elementary substructure of B. Prove that if a theory T admits
Quantifier Elimination (i.e., every formula is T-equivalent to a quantifier-free formula with no extra free
variables) then the theory T has property M.
Exercise 6 Apply the Quantifier Elimination procedure for the theory DLO to the following sentence E:
∃x∃y∃z∀u(x < y ∧ x < z ∧ z < y ∧ (u = z ∨ u < y ∨ u = x)).
Decide if DLO |= E or DLO |= ¬E.
3