1 Consider the language L := {c, R2} consisting of a constant and a binary relation symbol. a Find two non-isomorphic L -structures.
b Prove that the number of symbols in any L -formula is divisible by 3.
2 For the language L := {c,f1,g2,R3} consisting of one constant, one unary function symbol, one binary function symbol, and one ternary relation symbol, define an L -structure on the set of L -terms in a way such that the interpretation of a term t is not equal to t.
3 Let L be a first-order language and let A be an L -structure. If s is a variable assignment function into A , prove that A |= (∃x)(α)[s] if, and only if, there exists some a ∈ A such that A |= α[s[x|a]].
4 You might think that (φxy)yx is equal to φ, but a moment’s thought will give you an example to show that this doesn’t always work. (What if y is free in φ?) Find an example that shows that even if y is not free in φ, we can still have that (φxy)yx is different from φ. Under what conditions do we know that (φxy )yx is equal to φ?
5 Let φ and ψ be L -formulas.
(a) Prove that if |= (φ → ψ) then φ |= ψ.
(b) Ifφ:=x<y,andψ:=z<w,provethatφ|=ψbut̸|=(φ→ψ).
This exercise shows that the two possible ways to define logical equivalence are not equivalent