Logic Archives - Principles of Cryptography

authored by Premmi and Beguène

We will now briefly discuss the terms formula and free variables that we encountered during our discussion of the substitution axiom which is one of the two Axioms of Equality.

We can think of language as being comprised of a set of symbols or letters called the alphabet of the language, from which we form words by constructing sequences of letters taken from the alphabet.

Similarly, in mathematical logic, a formal language consists of words whose letters are taken from the set of formal symbols referred to as an alphabet and are well-formed according to a specific set of rules called formal grammar.

A symbol or string (sequence) of symbols may comprise a well-formed formula if it is consistent with the formation rules of the language. Formation rules describe which strings formed from the alphabet of a formal language are syntactically valid within that language. These rules address only the location and manipulation of strings; they do not describe anything else about a language, such as its semantics (i.e., what the strings mean).

Therefore, a well-formed formula, abbreviated WFF or wff, often referred to simply as a formula, is a finite sequence of symbols from a given alphabet that belongs to the formal language for which it makes sense to ask “Is this formula true?”, once any free variables in the formula have been instantiated.

A free variable is a symbol that specifies places in a formula where the symbol will later be replaced by some value. It should be noted that free variables appear only in the first-order formulas. A first-order formula is a formula in first-order logic—a system of logic more expressive and hence more powerful than proportional logic—used to express statements about objects and their relationships in a structured way, which we will discuss in detail later.

Example of a First-Order Formula

The following is an example of a first-order formula.

\forall x \ \, \, \exists y \ R(x, y)

This is interpreted in mathematical parlance as “for all $x$ , there exists a $y$ , such that $x \text{ and} y$ are related by the relation $R$ .” This formula isn’t true or false unless we assign values to $x, y \text{ and the relation} R$ .

A first-order formula isn’t true or false on its own. Before we can get a truth value we have to give an interpretation.Turning a first-order formula into a statement that is either true or false is called giving an interpretation for the formula.

Interpretation

An interpretation of a first-order formula consists of a set $X$ , called the domain of the interpretation, along with a relation on $X$ for each relation symbol in the formula.

Once we’ve given an interpretation, i.e., substituted any variables in the formula with values from the domain and any relation with that defined on the domain, we can evaluate whether the formula is true or false in that interpretation.

Here are some interpretations of the first-order formula:

\forall x \ \, \, \exists y \ R(x, y)

In the ensuing discussion, let’s denote $\mathbb{N}$ as the set of all natural numbers $\{0, 1, 2, \dots\}$ .

First Interpretation:

Domain: $\mathbb{N}$
Relation: $R$ is $<$

The interpreted formula becomes:

\forall x \in \mathbb{N} \ \, \, \exists y \in \mathbb{N} \ x < y

This interpreted formula is true. For every natural number $x$ there does exist a natural number $y$ with $x < y$ , e.g. $y$ could be the natural number $x + 1$ .

Second Interpretation:

Domain: $\mathbb{N}$
Relation: $R$ is $>$

The interpreted formula becomes:

\forall x \in \mathbb{N} \ \, \, \exists y \in \mathbb{N} \ x > y

In this case, the interpreted formula is false. It is not true that for every natural number $x$ there exists a natural number $y$ such that $x > y$ . For example, $x$ could be $0$ in which case no natural number $y$ satisfies $x > y$ .

authored by Premmi and Beguène

Introduction

In mathematics, the relation “equals” is a foundational concept that can be applied to any two mathematical objects to indicate that these objects represent the same mathematical entity. Since the concept of equality pertains to all mathematical objects, it is universal across mathematics and transcends its specific branches, situating itself firmly within the realm of logic. The equality relation is denoted by the symbol “=”.

Examples of Equality Relation

For numbers:
$\hspace*{4cm} 4 + 3 = 7$
For sets:
$\hspace*{4cm}\{1, 2, 3\} = \{3, 1, 2\}$
For functions:
$\hspace*{4cm}f(x) = x^3 = g(x)$ , where $g(x)$ is also defined as $x^3$
For matrices:
$\hspace*{4cm}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I_2 \, (\text{the } 2 \times 2 \text{ identity matrix})$
For geometric objects:
$\hspace*{4cm}\text{The set of all points } (x, y) \in \mathbb{R} \times \mathbb{R} \text{ such that } x² + y² = 1 \, (\text{a circle with radius } 1)$

In general, we write $a = b$ to denote that $a \text{ and } b$ represent the same mathematical object. This notation is universal across all areas of mathematics, from basic arithmetic to abstract algebra.

Axioms of Equality

The Axioms of Equality refer to a set of foundational principles that govern the relationship of equality in mathematics. These axioms include two key properties that describe how equality operates among mathematical objects.

In logic, equality is described through the following axioms:

Law of Identity: This axiom states that any mathematical object is equal to itself, expressed as:
$\hspace{6cm}\forall a \,(a = a)$
Substitution Axiom: This axiom states that if two mathematical objects are equal, then any property of one must also be a property of the other. This implies that one can be substituted for the other in any mathematical formula without changing the truth of that formula once any free variables in the formula have been instantiated. This axiom is also sometimes referred to as Leibniz’s law.

In mathematical terms this law can be expressed as follows:

For every $a \text{ and } b$ and any formula $\phi(x)$ , where $x$ is a free variable, if $a = b$ , then $\phi(a) \text{ implies } \phi(b)$ .

Symbolically, this can be represented as:
$\hspace{6cm}\forall a, b \,(a = b) \implies \big[\phi(a) \Rightarrow \phi(b)\big]$

For example, for all real numbers $a \text{ and } b$ , if $a = b$ , then $a \geq 0 \text{ implies } b \geq 0 \, (\text{here } \phi(x) \text{ is } x \geq 0)$ .

It should be noted that these two axioms do not define equality, they only state what properties that objects that are related by equality must satisfy. However, these two axioms are usually sufficient for deducing most properties of equality that mathematicians care about.

We can deduce from these two axioms some more properties of the equality relation. We will discuss these next.

Derivations of Properties of Equality Relation

Reflexivity of Equality: For any element $a$ in a set $S$ with a relation $R$ induced by equality $(xRy \Leftrightarrow x = y)$ , it holds that $\forall a \in S\, (aRa)$ .

That is, for any element $a$ in the set $S$ , the relation $R$ asserts that $a$ is related to itself, which is equivalent to saying that $a$ is equal to itself.

Proof. Given some set $S$ with a relation $R$ induced by equality, let us assume that $a \in S$ . Then, by the Law of Identity, $a = a$ and consequently, $aRa$ .
Symmetry of Equality: For any elements $a \text{ and } b$ in a set $S$ with a relation $R$ induced by equality $(xRy \Leftrightarrow x = y)$ , it holds that $\forall a, b \in S\, (aRb \implies bRa)$ .

That is, for any elements $a \text{ and } b$ in the set $S$ , the relation $R$ asserts that if $a$ is equal to $b$ (i.e., $aRb$ ), then it follows that $b$ is equal to $a$ (i.e., $bRa$ ).

Proof. Given some set $S$ with a relation $R$ induced by equality, let us assume that there are elements $a, b \in S$ such that $aRb$ . Let us consider the formula $\phi(x) : xRa$ .

By the Substitution Axiom, we have:
$\hspace{6cm}(a = b) \implies \big[\phi(a) \Rightarrow \phi(b)\big]$
Thus, we obtain:
$\hspace{6cm}(a = b) \implies (aRa \Rightarrow bRa)$

Since by assumption, $a = b$ and by Reflexivity, $aRa$ , it follows that $bRa$ .

Therefore, we have shown that if $aRb$ , then $bRa$ , demonstrating the symmetry of equality.
Transitivity of Equality: For any elements $a, b \text{ and } c$ in a set $S$ with a relation $R$ induced by equality $(xRy \Leftrightarrow x = y)$ , it holds that $\forall a, b, c \in S\, \big[(aRb \land bRc) \implies aRc\big]$ .

That is, for any elements $a, b \text{ and } c$ in the set $S$ , the relation $R$ asserts that if $a$ is equal to $b$ (i.e., $aRb$ ) and $b$ is equal to $c$ (i.e., $bRc$ ), then it follows that $a$ is equal to $c$ (i.e., $aRc$ ).

Proof. Given some set $S$ with a relation $R$ induced by equality, let us assume that there are elements $a, b, c \in S$ such that $aRb \text{ and } bRc$ . Then let us consider the formula $\phi(x) : xRc$ .

By the Substitution Axiom,
$\hspace{5cm}(b = a) \implies (bRc \Rightarrow aRc)$ .

Since by assumption, $a = b$ , it follows from Symmetry that $b = a$ . Additionally, since by assumption $bRc$ , it follows that $aRc$ .

Therefore, we have shown that if $aRb \text{ and } bRc$ , then $aRc$ , demonstrating the transitivity of equality.
Function Application: For any elements $a \text{ and } b$ from the domain of a function $f$ it holds that if $a = b$ then it implies that $f(a) = f(b)$ .

Proof. Given a function $f$ , let us assume that there are elements $a \text{ and } b$ from its domain such that $a = b$ . We will consider the formula $\phi(x) : f(a) = f(x)$ .

By the Substitution Axiom, we have:
$\hspace{6cm}(a = b) \implies \big[(f(a) = f(a)) \Rightarrow (f(a) = f(b))\big]$ .

Since, by assumption $a = b$ and by the Law of Identity $f(a) = f(a)$ , it follows that $f(a) = f(b)$ .

Therefore, we have shown that for any elements $a \text{ and } b$ from the domain of a function $f$ , if $a = b$ then it must be the case that $f(a) = f(b)$ .

These properties are sometimes included in the axioms of equality, but it is not necessary to include them since they can be derived from the two axioms of equality as shown above.