0

Consider this definition of first-order (or Herbrand) logic syntax. Here is the vocabulary:

Definition (Vocabulary): A vocabulary V consists of:

  • A set of relation constants {r1, ..., rn}, each with an associated arity.
  • A set of function constants {f1, ..., fm}, each with an associated arity.
  • A non-empty set of object constants {c1, ..., ck}.
  • A set of variables {x1,x2,...}.

Here is the definition for 'term':

Definition (Term): A term in V:

  • A variable.
  • An object constant.
  • A function constant with arity n applied to n terms.
  • Only expressions produced by the above rules are terms.

Here is the definition for 'sentence':

Definition (Sentence): A sentence in V:

  • A relation constant with arity n applied to n terms.
  • (¬ φ) where φ is a sentence.
  • (φ ∨ ψ), where φ and ψ are sentences.
  • (φ ∧ ψ), where φ and ψ are sentences.
  • (φ ⇐ ψ), where φ and ψ are sentences.
  • (φ ⇒ ψ), where φ and ψ are sentences.
  • (φ ⇔ ψ), where φ and ψ are sentences.
  • (∀x.φ), where φ is a sentence.
  • (∃x.φ), where φ is a sentence.
  • Only expressions produced by the above rules are sentences.

I noticed that a function is a term, but a relation is a sentence. At first I thought that was because of the quantifiers associated with a relation, but sentences using quantifiers are also defined. Also the definition of relation does not involve quantifiers.

This makes me wonder what is the difference between functions and relations in first-order logic that one would be considered a term and the other a sentence.


Francois Bry, Mike Genesereth, Tim Hinrichs, Nat Love. Herbrand Logic. Retrieved on September 28, 2019 at https://www.cs.uic.edu/~hinrichs/herbrand/html/herbrandlogic.html

| improve this question | | | | |
  • Incidentally, you may find this old answer of mine useful as supplementary information. – Noah Schweber Sep 28 '19 at 20:25
  • @NoahSchweber Thanks. It is good to know one doesn't need functions. From the article I used for the question it seems that Herbrand semantics relies on them. – Frank Hubeny Sep 28 '19 at 21:27
  • There are a lot of situations where they are very good things to have. It's just worth noting that technically we can get rid of them, if we're willing to deal with enough tedious nonsense. – Noah Schweber Sep 28 '19 at 22:02
3

First of all, a relation by itself is not a sentence. A relation applied to one or more terms is a sentence. Similarly, a function by itself is not a term. A function applied to one or more terms is a term.

The difference between functions and relations is that functions yield terms when applied to terms, while relations yield truth values. For instance, 'the father of x' is a function. When applied to a term, say 'Bob', we get a new term: 'the father of Bob'. This is not a sentence because it doesn't have a truth value. On the other hand, 'x is the father of y' is a relation. When applied to 'Jim' and 'Bob' we get a sentence that is either true or false: 'Jim is the father of Bob'.

You can also think of relations as functions that return truth values instead of terms, although in logic they are not usually defined this way.

| improve this answer | | | | |
  • What about something like IsUnmarried(Bob)? That can have a truth value (it can be taken as an atomic sentence) is it a “relation” even though it concerns only a single term (Bob)? – Hypnosifl Sep 28 '19 at 20:00
  • 2
    @Hypnosifl Yes, relations can be unary - or even nullary: just like how a constant can be thought of as a 0-ary function, we can think of nullary relations as "bare truth values" - or perhaps as propositional atoms lifted into the first-order context; indeed, some presentations of first-order logic include FALSE and TRUE as "logical nullary relation symbols" just like how = is a logical binary relation symbol. This is a bit of a stretch of the word "relation," and arguably "predicate" is more correct (indeed, we could talk about predicates on n-tuples instead of n-ary relations), but oh well. – Noah Schweber Sep 28 '19 at 20:21

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.