[Solved] MLCS Homework1

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: xy(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 x₁ x_ny₁ y_mF 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 y₁ y_mF 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(x₁,,x_n), for any (a₁,,a_n) Aⁿ, A |= F(x₁,,x_n)[a₁,,a_n] if and only if B |= F(x₁,,x_n)[f(a₁),,f(a_n)]. 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 L⁰ 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⁰.

2. Group2

Definition B is a substructure of A if: B A; for every constant symbol c, c^A = c^B, every relation R^B (resp. function f^B) is the restriction of R^A (resp. f^A) to B.

Exercise 1 Prove the following two points.

• If B is a substructure of A, then for any atomic formula F(x₁,,x_n), for all b₁,,b_n in B, B |= F[b₁,,b_n] iff A |= F[b₁,,b_n].
• 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(x₁,,x_n) for all b₁,,b_n in B, A |= F[b₁,,b_n] iff B |= F[b₁,,b_n]. That is, A and B agree on elements of B.

Exercise 2 Let A₁ = (N,+,0) and A₂ = (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. A₁ and A₂ 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.

• A₂ is a substructure ofA₁.
• A₁ e A₂ are isomorphic.
• A₁ e A₂ satisfy the same sentences in L.
• If A₁ |= xF(x)[] for an assignment in A₂, then there exists a A₂ such that A
• If E is a sentence of the form xF(x) with F(x) a quantifier-free formula then: If A₁ |= E then A₂ |= E.
• If E is a sentence of the form xF(x) with F(x) a quantifier-free formula then:

If A₁ |= E then A₂ |= 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:

xyzu(x < y x < z z < y (u = z u < y u = x)).

Decide if DLO |= E or DLO |= E.