0
$\begingroup$

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 first-order logic with equality. The finite 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 finite spectrum is {2^m | m ∈N}. Hint. Construct a formula such that the elements of any finite model can be identified with bit strings of a given finite 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
| cite | improve this question | | | | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Le Quoc Minh Oct 9 '19 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.