1
$\begingroup$

I am having trouble understanding what exactly an atomic formula is and its relevance.

The definition I have is as follows: An Atomic Formula is an expression of the form $A(t_1, \dots, t_n)$ where $A$ is an n-ary predicate symbol and each $t_i$ is a term (i.e., variable or constant symbol).

I believe my confusion primarily lies in the fact that it seems to just be a predicate with values filled in rather than a "standard" formula (using $\neg, \lor, \land, \rightarrow, \leftarrow$). Moreover, I am having issue understanding when this would not be the case. I.e., what is an example of a non-atomic formula?

$\endgroup$
4
  • $\begingroup$ See this post $\endgroup$ Dec 18, 2021 at 16:47
  • 1
    $\begingroup$ $R(x)$ is an atomic formula while $\lnot R(x)$ is not. $\endgroup$ Dec 18, 2021 at 16:47
  • $\begingroup$ @MauroALLEGRANZA Ah, I see. So since formulas are built on predicates, an expression such as $R(x)$ is an atomic formula and introducing any other connectives (or other predicates) such as $\neg R(x)$ would make it a non-atomic formula? $\endgroup$
    – user946947
    Dec 18, 2021 at 16:53
  • 1
    $\begingroup$ Exactly........ $\endgroup$ Dec 19, 2021 at 10:18

1 Answer 1

-1
$\begingroup$

Welcome to MSE!

Recall how formulas are (recursively) defined. let's work with the language of arithmetic for concreteness. So we have symbols $0,1,S,+,\times,<,=$ with their expected arities.

First we make the terms, which pick out elements of our structure. For instance

  • $0$
  • $S(0)$
  • $(1 + 1) + 1$
  • $1 \times y$
  • $y \times (y + 1)$
  • etc.

Next we define the atomic formulas. These are "atoms" in the sense that they "can't be broken down". These have truth values, but are the most basic questions we can ask. For us,

  • $0 = S(0)$
  • $(1 + 1) + 1 < 1 \times y$
  • etc.

Notice these all look like one of the relation symbols given in our language, with terms inside it. Notice, importantly, that these have nothing to do with the truth values of the formulas. It only has to do with whether it's a question we can ask. Of course, there's plenty of nonatomic formulas too:

  • $\big ( 0 = S(0) \big ) \land \big ( (1+1) + 1 < 1 \times y \big )$
  • $\lnot (0 = S(0))$
  • $\big ( (0 = x) \to (x \times y = 0) \big )$
  • etc.

Notice these are all formulas, which have truth values (at least once we instantiate the variables). They aren't "atomic" though, in the sense that they can be broken down into smaller parts.

If you like, formulas are trees, with leaves corresponding to atomic formulas and internal nodes corresponding to the connectives. See the example below

an example of the tree structure


I hope this helps ^_^

$\endgroup$
7
  • $\begingroup$ Hmm, I thought expressions such as $(1 + 1) + 1$ don't count as terms unless you are considering that a symbol for a constant (which doesn't seem correct). $\endgroup$
    – user946947
    Dec 18, 2021 at 21:51
  • $\begingroup$ Do you mean if I'm considering $1$ as a symbol for a constant? Or if I'm considering $(1+1)+1$ as a symbol for a constant? $\endgroup$ Dec 18, 2021 at 22:18
  • $\begingroup$ Considering $(1 + 1) + 1$ as a constant. If not, that will not be a term? $\endgroup$
    – user946947
    Dec 19, 2021 at 0:42
  • $\begingroup$ $(1+1)+1$ is a term even if it is not a constant. You should think of a term as "something that names an element of the structure". So $x$ names an element (albeit one whose value we don't know), $0$ names an element, $1$ names an element. Similarly, $1+1$ names an element, and in general if $t_1$ and $t_2$ are terms (that is, they name elements) then $t_1 + t_2$ is again a term (it names another element). I don't know what book you're reading, but you can find this (say) on page 11 of Hodges A Shorter Model Theory $\endgroup$ Dec 19, 2021 at 17:39
  • 1
    $\begingroup$ @Rahul -- a formula is just an allowable question to ask. The answer might be true or false depending on the model. In the standard model of the language of arithmetic (namely $\mathbb{N}$), this particular formula is false. However, it's still an atomic formula. $\endgroup$ Jan 31, 2022 at 19:20

You must log in to answer this question.

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