Talk:First-order logic

First-Order Sentence definition

According to my understanding a first-order sentence (or just sentence) is defined by not having any free variables. In the article it is stated that a formula is called a sentence when there are no free variable occurrences, specifically: "A formula in first-order logic with no free variable occurrences is called a first-order sentence.".

Does that imply that if we have only one occurrence of a variable to be free (but is bound in the whole formula), the formula is no valid sentence?

If not, it would be good to remove the word "occurrences" in the definition. Dark.Rider85 (talk) 07:32, 31 July 2023 (UTC)

"Free" and "bound" are not predicates that apply to variable symbols, like $x$, but to particular occurrences of variable symbols, e.g. the first and second occurrence of $x$ in the formula $p(x)\land \exists x.q(x)$ is free and bound, respectively. Therefore, your question doesn't make sense, imo (or maybe, I didn't understand it properly?).

On the other hand, I'm not sure that the distinction "sentence" / "formula" is made consistently throughout the article. For example First-order logic ... allows the use of sentences that contain variables in the lead's 2nd sentence could as well be generalized to First-order logic ... allows the use of formulas that contain variables. I didn't check the rest, but I noticed that "sentence" is often used to refer to a natural language sentence, which is a possible source of confusion, but maybe unavoidable. - Jochen Burghardt (talk) 08:38, 31 July 2023 (UTC)

Syntax-semantics distinction and history

Would it help to include some information on the history of the syntax-semantics distinction? (E.g. according to Ebbinghaus's Ernst Zermelo (2007), pp.182--183, acceptance of it was what set "classic" set theory researchers such as Zermelo and Fraenkel apart from the younger generation of set theory researchers such as Goedel, Skolem, and von Neumann). In this way the syntax-semantics distinction appears much more recent than the advent of first-order logic. C7XWiki (talk) 21:23, 20 April 2024 (UTC)

If-then-else

The article currently states:

This definition of a formula does not support defining an if-then-else function ite(c, a, b), where "c" is a condition expressed as a formula, that would return "a" if c is true, and "b" if it is false. This is because both predicates and functions can only accept terms as parameters, but the first parameter is a formula. Some languages built on first-order logic, such as SMT-LIB 2.0, add this.

I don't understand what this is trying to say. Is it trying to say that one can extend first-order logic with if-then-else, and get a (meta-)theory that is still equivalent to first-order logic? This seems incorrect at first blush: ite(P, P, Q) with P as a predicate corresponds to "the simplest second-order sentence admitting a nontrivial model", if I understand the article on second-order logic correctly. But if the extension of first-order logic with ite yields second-order logic, then why not come out and say that? Maybe the result is something else entirely? If so, what is that? Does it have a name? Are all such extensions equivalent/isomorphic to SMTLIB-2.0 or are there non-equivalent extensions? What, exactly, is the above paragraph trying to say? 84.15.176.27 (talk) 10:35, 18 June 2024 (UTC)

It seems rather odd to me too. If C, A and B are propositional variables then $ite(C,A,B)$ is equivalent to $(C\rightarrow A)\wedge (\neg C\rightarrow B)$ which is a well-defined truth function. Dezaxa (talk) 15:19, 18 June 2024 (UTC)

I removed the statement on if-then-else for now; in my opinion it is certainly misplaced in the paragraphs defining formulas (there are many extensions that are not supported, why highlight this one), and it is confusing at least to the posters in this section and to me. Felix QW (talk) 19:31, 18 June 2024 (UTC)

Comment: I think this paragraph referred to expressions like ite(x>0, x, -x) that are known from programming languages, e.g. (x>0 ? x : -x) can be used in C to denote the absolute value of x. See Ternary conditional operator for details in many programming languages. Such expressions, however, do not fit into the scheme of terms admitted by first-order logic. - Jochen Burghardt (talk) 05:00, 19 June 2024 (UTC)

Possible problem with the variable assignment function way to interpret truth in a model

Please correct me if I'm wrong. There is this example, ∃x (Px  ∧ ∃x (Qx)). This is a well-formed formula, yet if use that approach listed in "Evaluation of truth values", then we run into a problem. It's perfectly possible for there to be a model where this is true and exactly two objects of the domain have the properties P and Q respectively, but the variable assignment approach described overlooks this. ElskverdigHug (talk) 00:30, 26 July 2025 (UTC)

No. In the rule for existential quantifiers in sect. First-order_logic#Evaluation_of_truth_values, the variable assignment $\mu '$ needn't agree with $\mu$ on $x$.

The rule is such that applying a bounded renaming to the variable doesn't change the evaluation result. In your example, the argument for P is bound by the outer quantifier, while that of Q is bound by the inner one. Renaming the latter results in $\exists x(Px\land \exists y(Qy))$, and the problem disappeared.

Alternatively, if e.g. the domain of discourse is the natural numbers, and P and Q is satisfied by 0 and 1, respectively, then the formula $\exists x(Qx)$ is satisfied by an assignment $\mu '$ mapping x to 1. Hence, by the rule for existential quantifiers, is is also satisfied by an assignment mapping x to 0, since $\mu$ and $\mu '$ are allowed to disagree on the variable under consideration, viz. x. Hence, $\mu$ evaluates $Px\land \exists x(Qx)$ to true. Hence, every assignment evaluates the complete (closed) formula to true. - Jochen Burghardt (talk) 14:55, 26 July 2025 (UTC)

Atomic Formulas

The article currently states:

The formulas obtained from the first two rules are said to be atomic formulas.

The first two rules are 1) predicate symbols and 2) negation. I think that only formulas obtained from the first rule are atomic formulas:

1. The linked page Atomic formula does not mention negation.
2. In the BNF grammar, atomic formulas do not include negation.
3. The page Literal (mathematical logic) says: "a literal is an atomic formula (also known as an atom or prime formula) or its negation."
4. The Stanford Encyclopedia of Philosophy article on Classical Logic has a section on Atomic formulas and their definition does not include negation https://plato.stanford.edu/entries/logic-classical/#AtomForm
5. The definition of "atom" in Chapter 1, § 1 of "Mathematical Logic" by Stephen C. Kleene does not include negation. In fact, it states: "If $A$ is a given formula, then $\neg A$ is a (composite) formula."

~2026-20727-4 (talk) 20:06, 10 January 2026 (UTC)

Fixed. JRSpriggs (talk) 20:24, 10 January 2026 (UTC)