First-Order Logic: Semantics and Examples

Author

Your Name

Published

February 5, 2025

Introduction

This document delves into the semantics of first-order logic, providing illustrative examples to solidify key concepts. We will explore the evaluation of formulas within a given structure, the role of quantifiers, and the expression of various properties using first-order logic. The main objectives are to understand:

How to define a structure and evaluate formulas within it.
The significance of free and bound variables.
The distinction between sentences (formulas without free variables) and formulas with free variables.
How to express properties of relations, functions, and operators using first-order logic.
The impact of quantifier order on the meaning and strength of formulas.
The limitations of first order logic and the types of properties that it can and cannot express

This document aims to provide a comprehensive understanding of first-order logic, preparing the reader for more advanced topics in logic and its applications.

Semantics of First-Order Logic

This section provides a detailed explanation of the semantics of first-order logic through several examples. We will examine how to evaluate formulas within a given structure and understand the impact of changing the structure on the truth value of the formulas.

Example 1: Evaluating a Formula

Let’s consider a formula $\phi(X)$ with a free variable $X$: \[\phi(X) := \forall Y (E(X, Y) \lor O(X, Y))\] Here, we have two binary relational symbols, $E$ and $O$.

To evaluate this formula, we need to define a structure $S$. A structure consists of a universe, interpretations for the relational symbols, and an assignment for the free variable. Formally, $S = (U_S, E_S, O_S, X_S)$, where:

$U_S$ is the universe (a non-empty set of objects).
$E_S \subseteq U_S \times U_S$ is the interpretation of the binary relation $E$.
$O_S \subseteq U_S \times U_S$ is the interpretation of the binary relation $O$.
$X_S \in U_S$ is the interpretation of the free variable $X$.

Let’s define a structure $S$ as follows:

$U_S = \mathbb{N}$ (the set of natural numbers).
$E_S = \{ (n, m) \in \mathbb{N}^2 \mid n = m \}$ (the equality relation).
$O_S = \{ (n, m) \in \mathbb{N}^2 \mid n < m \}$ (the less-than relation).
$X_S = 0$ (the free variable $X$ is assigned the value 0).

Now, we evaluate the formula $\phi(X)$ in the structure $S$. The formula states that for every $Y$, either $E(X, Y)$ or $O(X, Y)$ holds.

We need to check if for every $u \in U_S$, the structure $S$ extended with $Y = u$ satisfies $E(X, Y) \lor O(X, Y)$. Let $S_u$ be the structure $S$ extended with $Y = u$, meaning $Y_S = u$. We need to check if $S_u \models E(X, Y) \lor O(X, Y)$ for all $u \in U_S$.

For $u = 0$, $S_0 \models E(X, Y)$ because $X_S = 0$ and $Y = 0$, so $E_S(0, 0)$ holds (since $0 = 0$).
For $u = 1$, $S_1 \models O(X, Y)$ because $X_S = 0$ and $Y = 1$, so $O_S(0, 1)$ holds (since $0 < 1$).
For any $u \in \mathbb{N}$, either $u = 0$ (and $E(X, Y)$ holds) or $u > 0$ (and $O(X, Y)$ holds).

Thus, for every $u \in U_S$, $S_u \models E(X, Y) \lor O(X, Y)$. Therefore, $S \models \forall Y (E(X, Y) \lor O(X, Y))$, and consequently, $S \models \phi(X)$.

The structure $S$ satisfies the formula $\phi(X)$ because for every possible value of $Y$ in the universe of natural numbers, either $X$ is equal to $Y$ or $X$ is less than $Y$ when $X$ is interpreted as 0.

Changing the Structure:

Now, let’s consider a new structure $S'$ where $X_{S'} = 1$. We have: \[S' = (\mathbb{N}, E_S, O_S, 1)\]

We need to check if $S' \models \forall Y (E(X, Y) \lor O(X, Y))$.

For $u = 0$, $S'_0$ is the structure $S'$ extended with $Y = 0$. Here, $X_{S'} = 1$ and $Y = 0$.
$S'_0 \not\models E(X, Y)$ because $E_S(1, 0)$ is false (since $1 \neq 0$).
$S'_0 \not\models O(X, Y)$ because $O_S(1, 0)$ is false (since $1 \nless 0$).

Since $S'_0 \not\models E(X, Y) \lor O(X, Y)$, we conclude that $S' \not\models \forall Y (E(X, Y) \lor O(X, Y))$, and thus $S' \not\models \phi(X)$.

By changing the interpretation of $X$ from 0 to 1, the structure $S'$ no longer satisfies the formula $\phi(X)$ because there exists a value for $Y$ (namely 0) for which neither the equality nor the less-than relation holds with $X$.

Example 2: Syllogism

Consider the syllogism: "If all humans are mortal and Socrates is a human, then Socrates is mortal."

Translated into a first-order formula: \[\forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)\] where $A$ represents "is a human" and $B$ represents "is mortal". Both are unary predicates.

Possible structure $S$:

$U_S = \{ \text{Socrates, Plato, Cyclop, Jupiter} \}$
$A_S = \{ \text{Socrates, Plato} \}$ (the set of humans)
$B_S = \{ \text{Socrates, Plato, Cyclop} \}$ (the set of mortals)
$Y_{0_S} = \text{Socrates}$ (the constant $Y_0$ is interpreted as Socrates)

$S \models \forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)$ because $S \models B(Y_0)$ (Socrates is in the set of mortals).

The structure $S$ satisfies the syllogism because Socrates, the interpretation of $Y_0$, is in the set of mortals ($B_S$).

Changing the Structure:

Let $S'$ be a structure where $A_{S'} = \{ \text{Plato} \}$ and $B_{S'} = \{ \text{Plato, Cyclop} \}$. Socrates is no longer considered human or mortal in this structure.

$S' \models \forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)$ because $S' \not\models A(Y_0)$ (Socrates is not in the set of humans), making the premise of the implication false, and thus the implication true.

Even when Socrates is removed from both the set of humans and mortals, the structure $S'$ still satisfies the syllogism. This is because the premise of the main implication is false, making the entire implication true.

Example 3: Isolated Node in a Graph

Consider the statement: "There exists a node in the graph that is isolated from all other nodes."

Translated into a first-order formula: \[\exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))\] where $E(X, Y)$ represents an edge from $X$ to $Y$. $E$ is a binary predicate.

Possible structure $S$:

$U_S = \{ \text{nodes of a graph} \}$
$E_S = \{ \text{edges of the graph} \}$ (a set of ordered pairs of nodes)

Example Graphs:

We will use TikZ to visualize the graphs.

Graph with two nodes and no edge: $S \models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$
Graph with two nodes and self-loops: $S \models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$
Graph with three connected nodes: $S \not\models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$

A graph satisfies the formula if it has at least one node that is not connected to any other node by an edge.

Example 4: Running Man

Consider the statement: "There’s a man such that when he runs, everybody runs."

Translated into a first-order formula: \[\exists X (R(X) \rightarrow \forall Y R(Y))\] where $R(X)$ represents "X runs". $R$ is a unary predicate.

Possible structure $S$:

$U_S = \{ \text{people in this room} \}$
$R_S = \{ \text{people who are running} \}$ (a subset of the universe)

If $R_S = \emptyset$ (nobody is running), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ because the premise $R(X)$ is false for any $X$ we choose. Therefore, the implication is true.
If $R_S$ is a proper subset of $U_S$ (some people are running, but not all), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ by picking an $X$ such that $X \notin R_S$ (someone who is not running). For this $X$, the premise $R(X)$ is false, making the implication true.
If $R_S = U_S$ (everybody is running), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ because the consequent $\forall Y R(Y)$ is true. We can choose any $X$, and the implication will hold.

This statement is a tautology in first-order logic. It is always true regardless of the structure, as long as the universe is not empty.

Expressing Properties with First-Order Logic

This section demonstrates how to express various properties of relations, functions, and operators using first-order logic. We will also explore the concept of continuity and uniform continuity and the importance of quantifier order.

Functions as Relations

In first-order logic, a function can be represented as a special type of relation. A function is a relation where each input maps to at most one output.

Definition 1 (Partial Function). A binary relation $R$ is a partial function if for every $X$, there is at most one $Y$ such that $R(X, Y)$ holds. Formally: \[\forall X \forall Y_1 \forall Y_2 (R(X, Y_1) \land R(X, Y_2) \rightarrow Y_1 = Y_2)\] This formula states that if $X$ is related to both $Y_1$ and $Y_2$, then $Y_1$ must be equal to $Y_2$.

Definition 2 (Total Function). A relation $R$ is a total function if it is a partial function and for every $X$, there exists at least one $Y$ such that $R(X, Y)$ holds. Formally: \[\forall X \exists Y R(X, Y)\] This formula states that for every $X$ in the universe, there exists some $Y$ such that $R(X, Y)$ is true.

A partial function ensures that each input maps to at most one output.
A total function ensures that each input maps to exactly one output.

Syntactic Sugar: When we know that a relation $R$ represents a (total) function, we can use the syntactic sugar $R(X) = Y$ as a shorthand for the formula: \[R(X, Y) \land \forall Z (R(X, Z) \rightarrow Y = Z)\] This formula states that $R(X, Y)$ holds and that $Y$ is the only element related to $X$ by $R$.

Operators and Their Properties

We can express properties of operators using first-order logic. For example, let’s consider the addition operator $+$. We will treat $+$ as a ternary relation, where $+(X, Y, Z)$ means $X + Y = Z$.

Definition 3 (Commutativity). The addition operator $+$ is commutative if the order of the operands does not affect the result. Formally: \[\forall X \forall Y \forall Z (+(X, Y, Z) \rightarrow +(Y, X, Z))\] This is equivalent to the more familiar notation: \[\forall X \forall Y (X + Y = Y + X)\] Using the ternary relation representation, we can expand this as: \[\forall X \forall Y \forall Z \forall T (+(X, Y, Z) \land +(Y, X, T) \rightarrow Z = T)\] This formula states that if $X + Y = Z$ and $Y + X = T$, then $Z$ must be equal to $T$.

Definition 4 (Identity Element (Zero)). An operator $+$ has an identity element (zero) if there exists an element $X$ such that adding $X$ to any other element $Y$ results in $Y$. Formally: \[\exists X \forall Y \forall Z (+(X, Y, Z) \rightarrow Z = Y)\] This is equivalent to: \[\exists X \forall Y (X + Y = Y)\] Here, $X$ represents the identity element (zero).

Definition 5 (Inverses). For every element $Y$, there exists an additive inverse $Z$ such that adding $Y$ and $Z$ results in the identity element (zero). Let’s assume we have already defined the identity element as 0. Then, we can express the existence of inverses as: \[\forall Y \exists Z (Y + Z = 0)\] Using the ternary relation and the definition of zero, we can write this as: \[\forall Y \exists Z \forall T (+(Y, Z, T) \rightarrow T = 0)\] Where 0 is the identity element defined previously.

We can express properties like commutativity, the existence of an identity element, and the existence of inverses using first-order logic by treating operators as relations.

Continuity vs. Uniform Continuity

Let’s consider the concepts of continuity and uniform continuity of a function $f: \mathbb{R} \rightarrow \mathbb{R}$. We will use the absolute value function, denoted by $|\cdot|$, and the standard ordering relation $<$ on real numbers.

Definition 6 (Continuity). A function $f$ is continuous at a point $X$ if for every $\epsilon > 0$, there exists a $\delta > 0$ such that for all $Y$, if the distance between $X$ and $Y$ is less than $\delta$, then the distance between $f(X)$ and $f(Y)$ is less than $\epsilon$. Formally: \[\forall X \forall \epsilon > 0 \exists \delta > 0 \forall Y (|X - Y| < \delta \rightarrow |f(X) - f(Y)| < \epsilon)\]

Definition 7 (Uniform Continuity). A function $f$ is uniformly continuous if for every $\epsilon > 0$, there exists a $\delta > 0$ such that for all $X$ and $Y$, if the distance between $X$ and $Y$ is less than $\delta$, then the distance between $f(X)$ and $f(Y)$ is less than $\epsilon$. Formally: \[\forall \epsilon > 0 \exists \delta > 0 \forall X \forall Y (|X - Y| < \delta \rightarrow |f(X) - f(Y)| < \epsilon)\]

The difference between continuity and uniform continuity lies in the order of the quantifiers. In continuity, $\delta$ can depend on both $X$ and $\epsilon$, while in uniform continuity, $\delta$ depends only on $\epsilon$.

Strength of Quantifier Order: The order of quantifiers significantly affects the meaning of a formula. In general, $\exists \forall$ is a stronger statement than $\forall \exists$.

For example, consider the statements:

$\exists X \forall Y \text{ Loves}(X, Y)$: There exists a person who loves everyone.
$\forall Y \exists X \text{ Loves}(X, Y)$: Everyone is loved by someone.

The first statement ($\exists \forall$) is stronger because it claims the existence of a single person who loves everyone, while the second statement ($\forall \exists$) only claims that for each person, there is at least one person who loves them.

$\exists \forall$ is generally a stronger statement than $\forall \exists$. The order of quantifiers fundamentally changes the meaning of a logical formula.

Vocabulary and Meaning of Continuity Formulas:
- Universe: Real numbers ($\mathbb{R}$)
- Relations:
  - $<$ (less than): A binary relation on $\mathbb{R}$
  - $|\cdot|$ (absolute value): A function from $\mathbb{R}$ to $\mathbb{R}$
  - $-$ (subtraction): A function from $\mathbb{R} \times \mathbb{R}$ to $\mathbb{R}$
  - $f$: The function being analyzed for continuity, $f: \mathbb{R} \rightarrow \mathbb{R}$

Conclusion

This document has explored the semantics of first-order logic, demonstrating how to evaluate formulas within structures and how to express various properties using this logic. We have seen that:

The choice of structure significantly impacts the truth value of a formula. A formula can be true in one structure and false in another.
Free variables require interpretation within a structure, while bound variables are quantified over the universe.
Sentences, having no free variables, can be evaluated based solely on the universe and relations defined in the structure. Their truth value depends only on the structure itself.
First-order logic can effectively describe properties of relations, functions, and operators, such as commutativity, the existence of identity elements, and inverses.
The order of quantifiers, especially the alternation between existential and universal quantifiers, is crucial for the meaning and strength of a statement. $\exists \forall$ is generally stronger than $\forall \exists$.

Structures determine the truth of formulas.
Quantifier order is crucial.
First-order logic is a powerful tool for expressing properties of mathematical objects.

Follow-up Questions:

How can we formally prove that a formula is a tautology, true in all possible structures (with a non-empty universe)?
What are the limitations of first-order logic? Are there properties that cannot be expressed? For example, can we express the concept of infinity or the property of a set being finite in first-order logic?
How does the concept of satisfiability relate to the notion of a model? A formula is satisfiable if there exists at least one structure in which it is true. A model of a formula is a structure in which the formula is true.
A more detailed analysis of the continuity formulas would be helpful. We can expand the formulas using the definitions of absolute value and subtraction as relations. For example, $|X - Y| < \delta$ can be expressed as a relation involving $X$, $Y$, $\delta$, and the ordering relation $<$.
Explore the relationship between the continuity formulas and their logical structure, paying particular attention to the quantifier order and its implications. Why does the change in quantifier order make uniform continuity a stronger condition than continuity?
How can we use first-order logic to define other important mathematical concepts, such as limits, derivatives, and integrals?
What is the connection between first-order logic and other logical systems, such as propositional logic, second-order logic, and modal logic?

These notes provide a foundation for understanding first-order logic. Further exploration of these topics will deepen your understanding and prepare you for more advanced concepts in logic and its applications in computer science, mathematics, and other fields.

--- title: "First-Order Logic: Semantics and Examples" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This document delves into the semantics of first-order logic, providing illustrative examples to solidify key concepts. We will explore the evaluation of formulas within a given structure, the role of quantifiers, and the expression of various properties using first-order logic. The main objectives are to understand: - How to define a structure and evaluate formulas within it. - The significance of free and bound variables. - The distinction between sentences (formulas without free variables) and formulas with free variables. - How to express properties of relations, functions, and operators using first-order logic. - The impact of quantifier order on the meaning and strength of formulas. - The limitations of first order logic and the types of properties that it can and cannot express This document aims to provide a comprehensive understanding of first-order logic, preparing the reader for more advanced topics in logic and its applications. # Semantics of First-Order Logic This section provides a detailed explanation of the semantics of first-order logic through several examples. We will examine how to evaluate formulas within a given structure and understand the impact of changing the structure on the truth value of the formulas. ## Example 1: Evaluating a Formula Let's consider a formula $\phi(X)$ with a free variable $X$: $$\phi(X) := \forall Y (E(X, Y) \lor O(X, Y))$$ Here, we have two binary relational symbols, $E$ and $O$. To evaluate this formula, we need to define a structure $S$. A structure consists of a universe, interpretations for the relational symbols, and an assignment for the free variable. Formally, $S = (U_S, E_S, O_S, X_S)$, where: - $U_S$ is the universe (a non-empty set of objects). - $E_S \subseteq U_S \times U_S$ is the interpretation of the binary relation $E$. - $O_S \subseteq U_S \times U_S$ is the interpretation of the binary relation $O$. - $X_S \in U_S$ is the interpretation of the free variable $X$. Let's define a structure $S$ as follows: - $U_S = \mathbb{N}$ (the set of natural numbers). - $E_S = \{ (n, m) \in \mathbb{N}^2 \mid n = m \}$ (the equality relation). - $O_S = \{ (n, m) \in \mathbb{N}^2 \mid n < m \}$ (the less-than relation). - $X_S = 0$ (the free variable $X$ is assigned the value 0). Now, we evaluate the formula $\phi(X)$ in the structure $S$. The formula states that for every $Y$, either $E(X, Y)$ or $O(X, Y)$ holds. We need to check if for every $u \in U_S$, the structure $S$ extended with $Y = u$ satisfies $E(X, Y) \lor O(X, Y)$. Let $S_u$ be the structure $S$ extended with $Y = u$, meaning $Y_S = u$. We need to check if $S_u \models E(X, Y) \lor O(X, Y)$ for all $u \in U_S$. - For $u = 0$, $S_0 \models E(X, Y)$ because $X_S = 0$ and $Y = 0$, so $E_S(0, 0)$ holds (since $0 = 0$). - For $u = 1$, $S_1 \models O(X, Y)$ because $X_S = 0$ and $Y = 1$, so $O_S(0, 1)$ holds (since $0 < 1$). - For any $u \in \mathbb{N}$, either $u = 0$ (and $E(X, Y)$ holds) or $u > 0$ (and $O(X, Y)$ holds). Thus, for every $u \in U_S$, $S_u \models E(X, Y) \lor O(X, Y)$. Therefore, $S \models \forall Y (E(X, Y) \lor O(X, Y))$, and consequently, $S \models \phi(X)$. ::: tcolorbox The structure $S$ satisfies the formula $\phi(X)$ because for every possible value of $Y$ in the universe of natural numbers, either $X$ is equal to $Y$ or $X$ is less than $Y$ when $X$ is interpreted as 0. ::: **Changing the Structure:** Now, let's consider a new structure $S'$ where $X_{S'} = 1$. We have: $$S' = (\mathbb{N}, E_S, O_S, 1)$$ We need to check if $S' \models \forall Y (E(X, Y) \lor O(X, Y))$. - For $u = 0$, $S'_0$ is the structure $S'$ extended with $Y = 0$. Here, $X_{S'} = 1$ and $Y = 0$. - $S'_0 \not\models E(X, Y)$ because $E_S(1, 0)$ is false (since $1 \neq 0$). - $S'_0 \not\models O(X, Y)$ because $O_S(1, 0)$ is false (since $1 \nless 0$). Since $S'_0 \not\models E(X, Y) \lor O(X, Y)$, we conclude that $S' \not\models \forall Y (E(X, Y) \lor O(X, Y))$, and thus $S' \not\models \phi(X)$. ::: tcolorbox By changing the interpretation of $X$ from 0 to 1, the structure $S'$ no longer satisfies the formula $\phi(X)$ because there exists a value for $Y$ (namely 0) for which neither the equality nor the less-than relation holds with $X$. ::: ## Example 2: Syllogism Consider the syllogism: \"If all humans are mortal and Socrates is a human, then Socrates is mortal.\" Translated into a first-order formula: $$\forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)$$ where $A$ represents \"is a human\" and $B$ represents \"is mortal\". Both are unary predicates. Possible structure $S$: - $U_S = \{ \text{Socrates, Plato, Cyclop, Jupiter} \}$ - $A_S = \{ \text{Socrates, Plato} \}$ (the set of humans) - $B_S = \{ \text{Socrates, Plato, Cyclop} \}$ (the set of mortals) - $Y_{0_S} = \text{Socrates}$ (the constant $Y_0$ is interpreted as Socrates) $S \models \forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)$ because $S \models B(Y_0)$ (Socrates is in the set of mortals). ::: tcolorbox The structure $S$ satisfies the syllogism because Socrates, the interpretation of $Y_0$, is in the set of mortals ($B_S$). ::: **Changing the Structure:** Let $S'$ be a structure where $A_{S'} = \{ \text{Plato} \}$ and $B_{S'} = \{ \text{Plato, Cyclop} \}$. Socrates is no longer considered human or mortal in this structure. $S' \models \forall Y (A(Y) \rightarrow B(Y)) \land A(Y_0) \rightarrow B(Y_0)$ because $S' \not\models A(Y_0)$ (Socrates is not in the set of humans), making the premise of the implication false, and thus the implication true. ::: tcolorbox Even when Socrates is removed from both the set of humans and mortals, the structure $S'$ still satisfies the syllogism. This is because the premise of the main implication is false, making the entire implication true. ::: ## Example 3: Isolated Node in a Graph Consider the statement: \"There exists a node in the graph that is isolated from all other nodes.\" Translated into a first-order formula: $$\exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$$ where $E(X, Y)$ represents an edge from $X$ to $Y$. $E$ is a binary predicate. Possible structure $S$: - $U_S = \{ \text{nodes of a graph} \}$ - $E_S = \{ \text{edges of the graph} \}$ (a set of ordered pairs of nodes) **Example Graphs:** We will use TikZ to visualize the graphs. - Graph with two nodes and no edge: $S \models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$ - Graph with two nodes and self-loops: $S \models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$ - Graph with three connected nodes: $S \not\models \exists X (\forall Y (Y \neq X \rightarrow \neg E(X, Y)))$ ::: tcolorbox A graph satisfies the formula if it has at least one node that is not connected to any other node by an edge. ::: ## Example 4: Running Man Consider the statement: \"There's a man such that when he runs, everybody runs.\" Translated into a first-order formula: $$\exists X (R(X) \rightarrow \forall Y R(Y))$$ where $R(X)$ represents \"X runs\". $R$ is a unary predicate. Possible structure $S$: - $U_S = \{ \text{people in this room} \}$ - $R_S = \{ \text{people who are running} \}$ (a subset of the universe)  - If $R_S = \emptyset$ (nobody is running), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ because the premise $R(X)$ is false for any $X$ we choose. Therefore, the implication is true. - If $R_S$ is a proper subset of $U_S$ (some people are running, but not all), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ by picking an $X$ such that $X \notin R_S$ (someone who is not running). For this $X$, the premise $R(X)$ is false, making the implication true. - If $R_S = U_S$ (everybody is running), $S \models \exists X (R(X) \rightarrow \forall Y R(Y))$ because the consequent $\forall Y R(Y)$ is true. We can choose any $X$, and the implication will hold. ::: tcolorbox This statement is a tautology in first-order logic. It is always true regardless of the structure, as long as the universe is not empty. ::: # Expressing Properties with First-Order Logic This section demonstrates how to express various properties of relations, functions, and operators using first-order logic. We will also explore the concept of continuity and uniform continuity and the importance of quantifier order. ## Functions as Relations In first-order logic, a function can be represented as a special type of relation. A function is a relation where each input maps to at most one output. ::: definition **Definition 1** (Partial Function). *A binary relation $R$ is a partial function if for every $X$, there is at most one $Y$ such that $R(X, Y)$ holds. Formally: $$\forall X \forall Y_1 \forall Y_2 (R(X, Y_1) \land R(X, Y_2) \rightarrow Y_1 = Y_2)$$ This formula states that if $X$ is related to both $Y_1$ and $Y_2$, then $Y_1$ must be equal to $Y_2$.* ::: ::: definition **Definition 2** (Total Function). *A relation $R$ is a total function if it is a partial function and for every $X$, there exists at least one $Y$ such that $R(X, Y)$ holds. Formally: $$\forall X \exists Y R(X, Y)$$ This formula states that for every $X$ in the universe, there exists some $Y$ such that $R(X, Y)$ is true.* ::: ::: tcolorbox - A **partial function** ensures that each input maps to at most one output. - A **total function** ensures that each input maps to exactly one output. ::: **Syntactic Sugar:** When we know that a relation $R$ represents a (total) function, we can use the syntactic sugar $R(X) = Y$ as a shorthand for the formula: $$R(X, Y) \land \forall Z (R(X, Z) \rightarrow Y = Z)$$ This formula states that $R(X, Y)$ holds and that $Y$ is the only element related to $X$ by $R$. ## Operators and Their Properties We can express properties of operators using first-order logic. For example, let's consider the addition operator $+$. We will treat $+$ as a ternary relation, where $+(X, Y, Z)$ means $X + Y = Z$. ::: definition **Definition 3** (Commutativity). *The addition operator $+$ is commutative if the order of the operands does not affect the result. Formally: $$\forall X \forall Y \forall Z (+(X, Y, Z) \rightarrow +(Y, X, Z))$$ This is equivalent to the more familiar notation: $$\forall X \forall Y (X + Y = Y + X)$$ Using the ternary relation representation, we can expand this as: $$\forall X \forall Y \forall Z \forall T (+(X, Y, Z) \land +(Y, X, T) \rightarrow Z = T)$$ This formula states that if $X + Y = Z$ and $Y + X = T$, then $Z$ must be equal to $T$.* ::: ::: definition **Definition 4** (Identity Element (Zero)). *An operator $+$ has an identity element (zero) if there exists an element $X$ such that adding $X$ to any other element $Y$ results in $Y$. Formally: $$\exists X \forall Y \forall Z (+(X, Y, Z) \rightarrow Z = Y)$$ This is equivalent to: $$\exists X \forall Y (X + Y = Y)$$ Here, $X$ represents the identity element (zero).* ::: ::: definition **Definition 5** (Inverses). *For every element $Y$, there exists an additive inverse $Z$ such that adding $Y$ and $Z$ results in the identity element (zero). Let's assume we have already defined the identity element as 0. Then, we can express the existence of inverses as: $$\forall Y \exists Z (Y + Z = 0)$$ Using the ternary relation and the definition of zero, we can write this as: $$\forall Y \exists Z \forall T (+(Y, Z, T) \rightarrow T = 0)$$ Where 0 is the identity element defined previously.* ::: ::: tcolorbox We can express properties like commutativity, the existence of an identity element, and the existence of inverses using first-order logic by treating operators as relations. ::: ## Continuity vs. Uniform Continuity Let's consider the concepts of continuity and uniform continuity of a function $f: \mathbb{R} \rightarrow \mathbb{R}$. We will use the absolute value function, denoted by $|\cdot|$, and the standard ordering relation $<$ on real numbers. ::: definition **Definition 6** (Continuity). *A function $f$ is continuous at a point $X$ if for every $\epsilon > 0$, there exists a $\delta > 0$ such that for all $Y$, if the distance between $X$ and $Y$ is less than $\delta$, then the distance between $f(X)$ and $f(Y)$ is less than $\epsilon$. Formally: $$\forall X \forall \epsilon > 0 \exists \delta > 0 \forall Y (|X - Y| < \delta \rightarrow |f(X) - f(Y)| < \epsilon)$$* ::: ::: definition **Definition 7** (Uniform Continuity). *A function $f$ is uniformly continuous if for every $\epsilon > 0$, there exists a $\delta > 0$ such that for all $X$ and $Y$, if the distance between $X$ and $Y$ is less than $\delta$, then the distance between $f(X)$ and $f(Y)$ is less than $\epsilon$. Formally: $$\forall \epsilon > 0 \exists \delta > 0 \forall X \forall Y (|X - Y| < \delta \rightarrow |f(X) - f(Y)| < \epsilon)$$* ::: ::: tcolorbox The difference between continuity and uniform continuity lies in the order of the quantifiers. In continuity, $\delta$ can depend on both $X$ and $\epsilon$, while in uniform continuity, $\delta$ depends only on $\epsilon$. ::: **Strength of Quantifier Order:** The order of quantifiers significantly affects the meaning of a formula. In general, $\exists \forall$ is a stronger statement than $\forall \exists$. For example, consider the statements: - $\exists X \forall Y \text{ Loves}(X, Y)$: There exists a person who loves everyone. - $\forall Y \exists X \text{ Loves}(X, Y)$: Everyone is loved by someone. The first statement ($\exists \forall$) is stronger because it claims the existence of a single person who loves everyone, while the second statement ($\forall \exists$) only claims that for each person, there is at least one person who loves them. ::: tcolorbox $\exists \forall$ is generally a stronger statement than $\forall \exists$. The order of quantifiers fundamentally changes the meaning of a logical formula. ::: - **Vocabulary and Meaning of Continuity Formulas:** - **Universe:** Real numbers ($\mathbb{R}$) - **Relations:** - $<$ (less than): A binary relation on $\mathbb{R}$ - $|\cdot|$ (absolute value): A function from $\mathbb{R}$ to $\mathbb{R}$ - $-$ (subtraction): A function from $\mathbb{R} \times \mathbb{R}$ to $\mathbb{R}$ - $f$: The function being analyzed for continuity, $f: \mathbb{R} \rightarrow \mathbb{R}$ # Conclusion This document has explored the semantics of first-order logic, demonstrating how to evaluate formulas within structures and how to express various properties using this logic. We have seen that: - The choice of structure significantly impacts the truth value of a formula. A formula can be true in one structure and false in another. - Free variables require interpretation within a structure, while bound variables are quantified over the universe. - Sentences, having no free variables, can be evaluated based solely on the universe and relations defined in the structure. Their truth value depends only on the structure itself. - First-order logic can effectively describe properties of relations, functions, and operators, such as commutativity, the existence of identity elements, and inverses. - The order of quantifiers, especially the alternation between existential and universal quantifiers, is crucial for the meaning and strength of a statement. $\exists \forall$ is generally stronger than $\forall \exists$. ::: tcolorbox - Structures determine the truth of formulas. - Quantifier order is crucial. - First-order logic is a powerful tool for expressing properties of mathematical objects. ::: **Follow-up Questions:** - How can we formally prove that a formula is a tautology, true in all possible structures (with a non-empty universe)? - What are the limitations of first-order logic? Are there properties that cannot be expressed? For example, can we express the concept of infinity or the property of a set being finite in first-order logic? - How does the concept of satisfiability relate to the notion of a model? A formula is satisfiable if there exists at least one structure in which it is true. A model of a formula is a structure in which the formula is true. - A more detailed analysis of the continuity formulas would be helpful. We can expand the formulas using the definitions of absolute value and subtraction as relations. For example, $|X - Y| < \delta$ can be expressed as a relation involving $X$, $Y$, $\delta$, and the ordering relation $<$. - Explore the relationship between the continuity formulas and their logical structure, paying particular attention to the quantifier order and its implications. Why does the change in quantifier order make uniform continuity a stronger condition than continuity? - How can we use first-order logic to define other important mathematical concepts, such as limits, derivatives, and integrals? - What is the connection between first-order logic and other logical systems, such as propositional logic, second-order logic, and modal logic? These notes provide a foundation for understanding first-order logic. Further exploration of these topics will deepen your understanding and prepare you for more advanced concepts in logic and its applications in computer science, mathematics, and other fields.