1
$\begingroup$

There are different interpretations for any FOL sentence. One of several things that we should specify when we choose some interpretation is domain of discourse over which we quantify. What is not clear for me is what is allowed to be in this domain. Can we have domain of discourse consisting of some functions for example? From one side I have never seen any limitations for contents of domain, so why not? But from another side as far as I know we can't quantify over functions and predicates in FOL, so it implies that we can't add functions in domain of discourse. So I am not sure about the answer for this question.

Sorry if it is a very stupid question, perhaps I have some deep misunderstanding. But for me it looks quite important to understand with what kind of objects we can legally work in scope of FOL.

$\endgroup$

2 Answers 2

2
$\begingroup$

Long story short: Our domain can include functions and we can quantify over them. However, we cannot quantify over function letters, which are interpreted as functions on our domain of discourse (from now on, we will use the term universe).

For example, fix a group G, and consider its automorphism group Aut(G). It is a legitimate group, in particular it meets the condition $\forall g \in Aut(G), g \circ e = g$. Since its elements are functions (in particular automorphisms) we have in some sense quantified over functions. More generally, we can include any objects in our universe as long as it remains a set in the sense of our meta- theory, typically ZFC. Once we fix our universe, however, we cannot quantify over functions that our defined on our universe.

Again, and in other words, you are correct to say we cannot quantify over function letters and predicate letters in FOL. That is, by the typical semantics of FOL, $\forall x. P$ is true iff $M \models P[x/a]$, where x has been substitued for any element of the universe. Now, if that element of the universe happens to be a function, that is fine. However, it will not be picked out by a function letter, since function letters are mapped to functions whos domain is our universe by defintion of a first order structure.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you, I think I understand. One more question: do I understand correctly that we can have almost any (if not any) kind of objects in our universe? I mean if we use ZFC as meta-theory then we can include functions, numbers, graphs - anything that can be defined in ZFC as set. Right? $\endgroup$
    – user341
    Commented Jan 14 at 14:20
  • $\begingroup$ yes basically- it just has to be a set $\endgroup$
    – emesupap
    Commented Jan 14 at 15:16
2
$\begingroup$

The domain of discourse in FOL can be any set, and therefore can contain functions. However, it is not particularly useful since we cannot use them as functions within the syntax of first order logic. There is no allowed syntax in first order logic in which elements of the domain of discourse can be applied a function to other elements. The domain of discourse can only be used as input to function and predicate symbols in an FOL language.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .