3
$\begingroup$

I started to learn first-order logic and I am confused with the sentence below:

It is wrong to say "For all y in range of a function f, P(y) holds" as $\forall f(x)[P(f(x))]$ . It is because f(x) is not a variable.

In Wikipedia, the word "variable" appears out of nowhere and I could not figure out why $f(x)$ cannot be a variable.

My idea is that if we say "$\forall f(x)$" then $f(x)$ will be considered as a symbol without meaning rather than "value of a function $f$".

Apologies for bad grammars, as I am not a native speaker.

$\endgroup$
1
  • 1
    $\begingroup$ Because variables are the symbol: $x,y,z,\ldots$ while we have the more general concept of tertm: either a variable, a constant or a "complex" term built with function symbols, like e.g. $f(x), g(x,y), \ldots$. $\endgroup$ Commented Apr 14, 2020 at 8:46

2 Answers 2

5
$\begingroup$

The definition of First-Order Logic (also Wiki's one) starts with the definition of the syntax: alphabet, formula, etc.

(Individual) variables are part of the alphabet:

"An infinite set of variables, often denoted by lowercase letters at the end of the alphabet $x,y,z,\ldots$"

An expression like $f(x)$ is a term; terms are: either (individual) variables, or constants, or built using function symbols.

FOL is called "first-order" because w can only quantify over individual variables: $∀x(x=x)$.

In Second- (and Higher-) order we can quantify also over predicate and function symbols: $∀f \varphi(f)$.

$\endgroup$
2
$\begingroup$

"Variable" is a vague term in everyday mathematics, but has a rigorous definition in mathematical logic, e.g. in first order logic. There one fixes a set $\mathcal V$ of variables. The elements of that set are usually single symbols like $x,y,...$ and then these are the variables, and nothing else. In particular, $f(x)$ is not a variable $-$ never!

First order logic further is very percise about how symbols can be arranged, and one rule is that after the $\forall$-symbol, there always comes a variable, and nothing else.

So, while your way two write $\forall f(x)[P(f(x))]$ would be a nice abbreviation of

$$\forall x[x\in\mathrm{Dom}(f)\to P(f(x))]\qquad\text{or}\qquad \forall x[x\in\mathrm{Cod}(f)\to P(x)],$$

it is not standard and therefore should not be used without further explanation.

$\endgroup$

You must log in to answer this question.

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