# I am confused by some area of Logic

I currently am struggling with 3 questions:

1. Show a formula that is satisfiable but doesn't have a Hebrand model.
• However, I don't quite know what formula needs to be , satisfiable or not satisfiable, to not have a Hebrand model.
2. Consider a sentence F of ﬁrst-order logic with equality. The ﬁnite spectrum of F is the set of strictly positive natural numbers n such that F has a model whose universe has n elements. Write a sentence whose ﬁnite spectrum is {2^m | m ∈N}. Hint. Construct a formula such that the elements of any ﬁnite model can be identiﬁed with bit strings of a given ﬁnite length.
• I thought that if we are able to define a model of F as an Universe of size n. then F will have a model with Universe of size >n since we can just add elements to the Universe but do nothing with it?
3. Let F1,F2 be two sets of formulas such that for all assignments A, A |= F1 implies A not |= F2 and vice versa. They ask me to prove this using compactness theorem that there is a formula G such that F1 |= G and F2 not |= G.
• What I wonder here is I think G= conjunction of set of finite subset of formulas of S1. however, my proof has nothing to do with compactness theorem since I just show that for each A |= F2 => A not |= F1 => for some finite subset S' of F1 A(S')=0 => A(not S') =1 => F1 |= G since not S' belongs to not G. But I dont know how to prove it without knowing G and what compactness theorem has to do with the question here. Thank you very much

## 1 Answer

This is only a partial answer, but is hopefully helpful.

Re: 2:

I thought that if we are able to define a model of F as an Universe of size n. then F will have a model with Universe of size >n since we can just add elements to the Universe but do nothing with it?

This is false. As a trivial example, consider the sentence $$\forall x,y(x=y)$$. This has a model of size $$1$$ but no model of size $$>1$$.

As a more interesting example, suppose our language consists of a binary relation symbol $$E$$. Consider the sentence "$$E$$ is an equivalence relation and each $$E$$-class has exactly two elements" (do you see how to write this in first-order logic?). The spectrum of this sentence is exactly the set of even numbers: models of the sentence are basically a bunch of blocks of size $$2$$.

Re: 3:

You suggest "G= conjunction of set of finite subset of formulas of S1." But that $$G$$ is not a single formula (remember, $$S_1$$ and $$S_2$$ could be infinite!).

I would suggest solving the following problem first:

Suppose $$S_1,S_2$$ are sets of sentences such that $$S_1\cup S_2$$ is inconsistent (= not true in any assignment). Show that there are finite $$F_1\subseteq S_1$$, $$F_2\subseteq S_2$$ such that $$F_1\cup F_2$$ is inconsistent.

This is a straightforward application of compactness (HINT: is each finite subtheories of $$S_1\cup S_2$$ consistent?). It's also equivalent to the question you're asking, although that may not be immediately obvious (HINT: you can take the conjunction of finitely many formulas ...).

• Thank you. However, I understand the case for ∀x,y(x=y). However, for example, from what I understand ∀x(x=x) will have a model of any size? Because while solving questions, I come across a lot of questions that ask me to define a formula that have a model of certain size. However, I thought if I just use ∀x(x=x) then it can have any size. And if not, then what is a good way of thinking when think about constructing formula based on the cardinality of the universe? – Le Quoc Minh Oct 9 '19 at 8:55