Is $F(x,y)=x$ an atomic formula?

142 Views Asked by At

$F$ is a function symbol with arity $2$. Is $F(x,y)=x$ an atomic formula?

My teachers solutions say it is but I thought that atomic formula had to be a predicate name followed by a variable and if a $F$ is a function variable than it is not an atomic formula.

Is it an atomic formula or not? Thanks

2

There are 2 best solutions below

6
On

It is an atomic formula. The atomic formulas include all formulas of the shape $s=t$ where $s$ and $t$ are terms. The terms $s$ and $t$ can be quite complicated. For instance $G(F(x,y))$ is a term, where $x$ and $y$ are variable symbols, $F$ is a binary function symbol, and $G$ is a unary function symbol.

0
On

The source of the confusion might be the difference between infix and prefix notation. In some formulations of first-order logic, the official definition of "atomic formula" presupposes prefix notation, where the predicate symbol comes first, followed by its argument(s). In that notation, the formula you asked about would be $=(F(x,y),x)$ or, depending on how eager the author is to avoid parentheses, $=F(x,y)x$ or even $=Fxyx$ (which is unambiguous as long as you know that $=$ and $F$ are binary symbols). For the sake of human readers, people usually adopt some notational conventions, including ones that say you can write binary predicate symbols between their arguments; the resulting expression is regarded as an "abbreviation" of the official formula or an alternative way of writing it. So $F(x,y)=x$ would be an alternative way of writing something like $=Fxyx$ and would therefore count as a formula.

By the way, there is a similar convention for certain function symbols, like $+$, that are usually written between their arguments rather than in front. So if the function symbol $F$ in your example were $+$, you could write $x+y=x$ rather than $+(x,y)=x$.

The reason for such conventions is that prefix notation is more systematic and easier to analyze but people have difficulty reading things like $=+xyx$ and are much happier with $x+y=x$.