2

I just started learning about Herbrand model so I apologise if this may sound like a stupid question. How are you supposed to find how many elements are there in Herbrand model? (i have searched everywhere but couldn't find an answer)

For example, in this case:

Let the set of constant symbols C = {0,1}. Let the set of function symbols F = {s1}. Let the set of predicate symbols P = {=2, R1}. How many elements are there in a Herbrand model?

Select one: A. infinite, countable B. 2 C. 0 D. infinite, uncountable E. 4 F. 1

I tend to say it's infinite but I don't know if it's countable or not. Any ideas?

KeykoYume
  • 492

1 Answers1

4

A. Infinite, countable.

See Herbrand structure :

In first-order logic, a Herbrand structure $S$ is a structure over a vocabulary $σ$, that is defined solely by the syntactical properties of $σ$. The idea is to take the symbols of terms as their values.

In your language, there are two constant symbols : $0,1$ and a (unary) function symbol : $s_1$.

Terms are like : $0,1,s_1(0), s_1(1), s_1(s_1(0)), \ldots$.

The Herbrand universe of a first order language is enumerable, and infinitely countable if a function symbol of arity greater than $0$ exists [that is your case].

Mauro ALLEGRANZA
  • 94,169
  • Thank you so much for your answer! I still have a question though, how did the predicate symbols {=2, R1} help in getting your answer? – KeykoYume Nov 22 '15 at 11:09
  • 2
    @KeykoYume - they do not "act", because the domain of the H structure is made of terms; a term is like a "name" : it denotes an object in an interpretation. In this case, we use the terms as names for themselves, i.e. as objects of the interpretation. Predicate symbols are used to build sentences (or formuale) i.e. "phrases" that say something of the objects : $0=1$ is a sentence saying that the two objects denoted by $0$ and $1$ are the same, which is false e.g. in $\mathbb N$. – Mauro ALLEGRANZA Nov 22 '15 at 11:17
  • @MauroALLEGRANZA Can't you have an infinite countable model without function symbols?, that is in the case when the signature of the language has ifninite number of individual constants (plus possibly some relational predicates). – Rafał Gruszczyński Mar 14 '20 at 22:26