MLCS-Homework 1 Solved

1. Group1

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  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.

2. 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.

(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 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.