5
$\begingroup$

Several books introduce functions as non-logical symbols of languages of first-order logic. They then introduce again functions as ordered pairs, where for each $x$ there is a unique pair $\langle x, f(x)\rangle$.

I wonder whether the two are different notions which happen to have the same name and notation or the second is an instance of the first, that is, in $\langle x, f(x)\rangle$, $ f(x)$ can be thought as a special case, where variables are set (elements).
Finally, what is a good way to address the two types of functions to avoid ambiguities?

UPDATE

As per request of Rob Arthan, I give two book references.

This is Kunen, K. (2013). Set theory. Elsevier.

[O]ne must distinguish between the logical symbols and nonlogical symbols. The logical symbols are fixed, [...] The nonlogical symbols vary with context. Each application of logic will specify a set $\mathcal{L}$ of nonlogical symbols. [...] Each symbol in $\mathcal{L}$ has a specified arity, which is some natural number, and a specified type, which is either ''predicate symbol" or "function symbol". If we are discussing ZFC, then $\mathcal{L} = \left\{ \in\right\}$, where $\in$ is a predicate symbol.

Definition 1.6.3 $\;$ $R$ is a function iff $R$ is a relation and for every $x$, there is at most one $y$ such that $(x,y) \in R$. If $\exists y [xRy]$, then $R(x)$ denotes that unique $y$.

And now Enderton, H. B. (2001). A mathematical introduction to logic. Elsevier.

A function is a relation $F$ with the property of being single-valued. For each $x$ in dom $F$ there is only one $y$ such that $x, y \in F$.

We assume henceforth that we have been given infinitely many distinct objects (which we call symbols), arranged as follows:
A. Logical symbols $\;$ 0. Parentheses: $($ , $)$. $\;$ 1. Sentential connective symbols: $\rightarrow$, $\neg$. $\;$ 2. Variables (one for each positive integer n): $\; v_1 , v_2 , \ldots$ $\;$ 3. Equality symbol (optional): =.
B. Parameters $\;$ 0. Quantifier symbol: $\forall$. $\;$ 1. Predicate symbols: For each positive integer $n$, some set (possibly empty) of symbols, called $n$-place predicate symbols. $\;$ 2. Constant symbols: Some set (possibly empty) of symbols. $\;$ 3. Function symbols: For each positive integer $n$, some set (possibly empty) of symbols, called $n$-place function symbols.

$\endgroup$
4
  • $\begingroup$ I think you will get a much better answer if you cite a specific book that is causing you difficulties. Roughly speaking the difference here is between something like $+$ viewed as a formal symbol (as when you are applying BODMAS to decide where the implicit brackets go in expression like $1 + 2 \times 3$) and the operator that that symbol is standardly used to denote (as when you are finding the numerical value of $1 + (2\times 3)$). Without more information about the actual book you are looking at, it is hard to say more. $\endgroup$
    – Rob Arthan
    Commented Oct 28, 2021 at 22:41
  • 1
    $\begingroup$ In set theory functions are objects of the "world of sets", i.e. sets themselves. In First-Order logic, function symbols are part of the language and thus in a FO theory (like set theory) we use them to describe the objects of the "world" the theory is speaking of $\endgroup$ Commented Oct 29, 2021 at 6:04
  • $\begingroup$ @RobArthan: Please, see the updated question with required citations. $\endgroup$
    – antonio
    Commented Oct 29, 2021 at 9:58
  • $\begingroup$ As you can see from your example, in first-order set theory language there are no function symbols but the language "speaks of" mathematical functions (that are defined as sets, and thus in terms of the only basic $\in$ relation). $\endgroup$ Commented Oct 29, 2021 at 16:22

1 Answer 1

4
$\begingroup$

These are two distinct but related notions.

In one-sorted first order logic, we define a "vocabulary" as a set of predicate symbols and a set of function symbols (each with a given arity). For example, if we're describing an ordered field, we might have function symbols $+$ and $\cdot$ and the predicate symbol $\leq$. We abuse notation by writing $x + y$ instead of $+(x, y)$ (and do likewise with $\cdot$ and $\leq$).

Once we have a vocabulary, we can consider logical statements built from the vocabulary. For example, we could consider the sentence $\forall x \forall y \forall z, x \leq y \to x + z \leq y + z$.

It's important to note here that function symbols and predicate symbols are just symbols. They do not have any "meaning" per se except in how they can be used syntactically to construct statements and sentences.

We can then introduce a set of formal rules of deduction which describe how we can prove sentences from other previously known sentences. This gives us a notion of formal proof. There are a number of ways of doing this, but they're all equivalent.

Let's now switch gears to set theory. In set theory, we can define the notion of a "subset". We can also say what the statement $f : A \to B$ formally means.

Within set theory, we can take formal statements in first-order logic and interpret these statements to be about a specific set.

To be precise, let $P$ be a set of predicate symbols and $F$ a set of function symbols, each with an arity. A structure on the vocabulary $(P, R)$ is a set $M$, together with, for each $n$-ary predicate symbol $Q \in P$, a set $Q_M \subseteq M^n$, and also together with, for each $m$-ary function symbol $f \in F$, a function $f_M : M^m \to M$.

For every formal statement $\phi$, we can then interpret what it would mean for $\phi$ to be true in structure $M$. That is, we can determine what it would mean for $M$ to model $\phi$ (written $M \models \phi$). For example, let's say we're dealing with the vocabulary $+, \cdot, \leq$, and we interpret this vocabulary in the structure $(\mathbb{Z}, +, \cdot, \leq)$. Note that the $+$ function symbol and the $+$ function are two totally different things; we're just denoting them with the same character. This is known as "abuse of notation" - it is something that isn't technically correct, but can often lead to easier understanding.

The statement $\mathbb{Z} \models \forall x \forall y \forall z . x \leq y \to x + z \leq y + z$ is then interpreted to mean that for all integers $x, y,$ and $z$, if $x \leq y$ then $x + z \leq y + z$.

The situation is further complicated by the fact that set theory is itself a formal theory in first-order logic. So we're using set theory, which is formally expressed as a specific theory in first-order logic, to interpret theories in first-order logic within structures in set theory.

$\endgroup$
1
  • $\begingroup$ Thank you. With your symbology, $f \in F$ and $f_M : M^m \longrightarrow M$, there is no abuse of notation: $f$ denotes the function symbol and $f_M$ denotes the function. To me it seems there is still, so to say, an abuse of names. When we want to avoid ambiguities, can we say class function to address $f_M$ (or something else)? A second doubt is: to what vocabulary does the $f_M$ symbol belong? Or should we consider it an abbreviation built from the $(P,F)$ vocabulary? $\quad$ PS: Possible typo in "A structure on the vocabulary $(P,R)$...". $\endgroup$
    – antonio
    Commented Oct 29, 2021 at 11:13

You must log in to answer this question.

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