Description
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.
- 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
- 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 if and only if B ,
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.)
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 L0 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 L0.
- Group2
Definition B is a substructure of A if: B ⊆ A; for every constant symbol c, cA = cB, every relation RB (resp. function fB) is the restriction of RA (resp. fA) to B.
Exercise 1 Prove the following two points.
- 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].
- 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.
- A2 is a substructure ofA1.
- A1 e A2 are isomorphic.
- A1 e A2 satisfy the same sentences in L.
- If A1 |= ∃xF(x)[α] for an assignment α in A2, then there exists a ∈ A2 such that A
- If E is a sentence of the form ∀xF(x) with F(x) a quantifier-free formula then: If A1 |= E then A2 |= E.
- 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:
- (N,+,×,0,1,<) and (Q,+,×,0,1,<)
- (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.
