What is the structure of first order logic?

First-order logic's structure involves defining relationships between objects using predicates and quantifiers. It's a formal system used to reason about objects, their properties, and the relations between them. Let's break down the key components:

Core Components of First-Order Logic

Here's a breakdown of the components that define the structure:

• Objects: Represented by constants (e.g., a, b, c) or variables (e.g., x, y, z). The reference mentions a domain D, which is a set of objects. So, consider the domain to be the set of all integers.

• Predicates: These express properties of objects or relationships between them. Predicates are applied to objects. For example, P(x) could mean "x is a prime number" or Loves(x, y) could mean "x loves y." The reference states that "P is true" means the predicate assigned to the predicate symbol P by the interpretation is true.

• Functions: Functions map objects to other objects. For example, father_of(x) might return the father of object x.

• Logical Connectives: These connect statements (formulas) together:

  • ¬ (Negation: "not")
  • ∧ (Conjunction: "and")
  • ∨ (Disjunction: "or")
  • → (Implication: "if...then")
  • ↔ (Equivalence: "if and only if")

• Quantifiers: These express the scope of a statement:

  • ∀ (Universal Quantifier: "for all") e.g., ∀x P(x) means "For all x, P(x) is true."
  • ∃ (Existential Quantifier: "there exists") e.g., ∃x P(x) means "There exists an x such that P(x) is true." The reference states that ∃x P(x) "states the existence of some object in D for which the predicate P is true."

Formula Structure

Formulas in first-order logic are built recursively:

1. Atomic Formulas: These are the simplest formulas, consisting of a predicate applied to terms (constants, variables, or function applications). Examples: P(a), Loves(x, y), GreaterThan(father_of(x), y).

2. Complex Formulas: These are built from atomic formulas using logical connectives and quantifiers. Examples:

   • ¬P(x) (Negation)
   • P(x) ∧ Q(y) (Conjunction)
   • P(x) → Q(y) (Implication)
   • ∀x P(x) (Universal Quantification)
   • ∃x P(x) (Existential Quantification)

Example with Integers

Let's consider an example where the domain D is the set of integers. We can define a predicate Even(x) which is true if x is an even number. Then:

• Even(2) is true.
• ∃x Even(x) is true (because there exists at least one even integer).
• ∀x Even(x) is false (because not all integers are even).

First-Order Structure in a Nutshell

Component	Description	Example
Domain (D)	The set of objects the logic is talking about.	Set of integers, set of people, etc.
Constants	Specific objects in the domain.	2, john, table1
Variables	Used to refer to objects generally (often used with quantifiers).	x, y, z
Predicates	Properties of objects or relationships between them.	Even(x), Loves(x, y), IsAbove(table1, object)
Functions	Maps objects to other objects.	father_of(x), add(x, y)
Connectives	Used to combine formulas (¬, ∧, ∨, →, ↔)	∧, ∨, →
Quantifiers	Used to express the scope of a statement (∀, ∃)	∀, ∃