[Solved] MLCS Homework1

$25

File Name: MLCS_Homework1.zip
File Size: 131.88 KB

SKU: [Solved] MLCS Homework1 Category: Tag:
5/5 - (1 vote)

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

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

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

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

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[Solved] MLCS Homework1
$25