In this tutorial, we will guide you through the principles of using first-order logic (FOL) and set theory. We assume you have a basic knowledge of propositional logic. During the tutorial, we also explain the language used in the tool It’s a True World. In this tutorial you will study:

  1. The basics of set theory and relations;
  2. The basics of predicates and FOL;
  3. Relation between set theory and first order logic;

The basics of set theory

Before we start modeling, first a small crash course on set theory and logic. A set is nothing more than a collection of elements. If the sets are finite, we can visualize the elements using a Venn-Diagram. An example is depicted below.

The Venn diagram shows four sets, named A, B, C, and D. All elements together form the universe, U. Some elements can be part of multiple sets. For example, element h belongs to sets A and B, and elements k and l reside in both B and D. Formally, we write this universe as follows, Using a “curly” U to denote the universe:

\begin{array}{lcl} \mathcal{U} & = & \{ e, f, g, h, i, j, k, l \} \\ A & = & \{e, f, g, h \}\\ B & = & \{ h, i, j, k \} \\ C & = & \{ l \} \\ D & = & \{ j, k \} \end{array}

Some common sets are:

  1. The empty set, i.e., the set containing no elements at all: \emptyset;
  2. The set of all natural numbers: \mathbb{N} = \{0, 1, 2, \ldots \};
  3. The set of all integers: \mathbb{Z} = \{ \ldots, -2, -1, 0, 1, 2 \ldots \};
  4. The set of all boolean values: \mathbb{B} = \{ \mbox{True}, \mbox{False} \}.

In this universe we want to make statements. For example:

  1. f is an element of A;
  2. g is en element of C;
  3. h is an element of both A and B;
  4. Any element in D is also an element of B;
  5. Any element that is both in A and in B, is not in C.

The statements may or may not hold in a given universe. However, as the last example shows, writing such statements in natural language can become quite large. And more importantly, some statements may be ambiguous, i.e., the same statement can be interpreted in different ways. For example, The set of A without B and C can be interpreted as A does not contain any element from B nor from C, or it can be the set of elements that are both in C and in A, without any element from B. Therefore, we introduce a language that allows us to make concise statements.

The language consists of statements about elements, and construction operators to create new sets.

Statements and First-order logic

The basic statement in set theory is element inclusion: an element a is included in some set S. Formally written as:

a \in S

If an element is not included, we write:

a \not\in S

In this way, the above examples can be formalized as:

  1. f \in A: f is an element of A
  2. g \in C: g is en element of C;

Statements are either true or false, depending on the context. For example, given the above sets, the first statement is true, whereas the second is false. If a statement S is true in a given context C, we say the statement is valid in C. Formally, we write this as:

C \models S

If the statement is not valid in that context, we write:

C \not\models S

Some statements are always true, in any given context. For example, an element a is either included in a set A, or not. If a statement S is true in any context, it is called a tautology. Formally, we write this as:

\models S

As an example:

\models (a \in A) \vee (a \not\in A)

Similarly, statements exist that are always false in any given context. For example, the statement that an element a is both included in a set B, and not included in the same set is false, no matter what set B is. Such a statement S that is always false is called a contradiction. Formally:

\not\models S

Thus, the example can be formally written as:

\not\models (a \in B) \wedge (a \not\in B)

Another class of statements are properties of elements, called predicates. A predicate is a statement that is either true or false, depending on the the value of its variables. Formally, a predicate is an n-ary function:

P(x_1, \ldots x_n) \rightarrow \{ \mbox{True}, \mbox{False} \}

Hence, a statement can only be evaluated if all its variables are instantiated. Consider as an example predicate P that takes a natural number, and evaluates whether it is even. Then P(2) is valid, whereas P(13) is invalid. Note that element inclusion is a special case of a predicate: take the predicate Q that takes one variable a from the universe, and is true if and only if a is included in A, i.e.:

Q(a) = \mbox{True} \iff a \in A

Instead of making this predicate explicit for each set, we simply interpret the statement “element a is included in set A” as a predicate.

With these two classes of statements, we can compose any statement. However, this can become very cumbersome, or even impossible. For example, the statement that all even numbers are divisible by 2 is valid. But, one needs to state this for each natural element explicitly. For this purpose, we introduce quantifiers. A quantifier provides a predicate over the elements in a set. There are two quantifiers:

  1. The universal quantifier, that states something for all elements in the set, written as: \forall a \in S : P(a); and
  2. The existential quantifier states that there is some element for which the predicate is true, written as \exists a \in S: P(a).

The universal quantifies reads as: if an element a is included in set S, then predicate P(a) has to be true. Hence, this is an implication! The existential quantifier reads as a large disjunction: at least for one of the included elements, the statement is true.

As any other statement, quantified statements are either or false, depending on the context. However, the predicate needs to be checked for each element in the quantification. Hence, to check the statement:

Added: \forall d \in D : d \in B

Added: We need to validate for each element that if it is included in D, it is included in B as well:

(d \in D) \implies (d \in B)

Hence, unfolding this for each element in D, gives the following conjunction:

((j \in D) \implies (j \in B)) \wedge ((k \in D) \implies (k \in B))

Creating a truth table for this proposition using the above context C yields a valid result, i.e.,

C \models \forall d \in D : d \in B

For the existential quantifier, a similar unfolding is required. As an example, consider the statement that some element exists that is included in both A and in B, i.e.:

\exists a \ in A : a \in B

To validate this, we need to check for each element whether it is both in A and in B:

(a \in A) \wedge (a \in B)

We need to unfold this statement for each element in A, resulting in a large disjunction:

((e \in A) \wedge (e \in B)) \vee ((f \in A) \wedge (f \in B)) \vee ((g \in A) \wedge (g \in B)) \vee ((h \in A) \wedge (h \in B))

Again, in the above context C, this statement is true, as only the last clause for element h evaluates to true. Hence:

C \models \exists a \in A : a \in B

There is one important edge case to consider for the quantified statements: what if the statement is made over the empty set? The universal quantifier reads as an implication: if the elements is included in the set, then the predicate should hold. As this reads as an implication, any universal quantified statement over the empty set is true, as false implies anything. In other words: it is a tautology! Hence:

\models \forall a \in \emptyset : P(a)

In a similar line of thinking, an existential statement unfolds to a large disjunction, of which at least one should be true. But as no element can be found that satisfies the predicate, it cannot be true. Hence, the existential quantifier over the empty set is a contradiction:

\not\models \exists a \in \emptyset : P(a)

Composing sets

The operators to compose new sets out of existing ones are:

  1. A special set is the empty set, which contains no elements at all: \emptyset
  2. Union: create a set S containing all elements from A, from B, or from both. Formally: S = A \cup B
  3. Intersection: create a set S containing all elements that are both in A and in B. Formally: S = A \cap B
  4. Exclusion: create a set S from the elements of A that are not in B. Formally: S = A \setminus B

These sets can be interpreted as quantified statements:

\begin{array}{rcl} A \cup B & \iff & \forall a \in (A \cup B) : ( (a \in A) \vee (a \in B) ) \\ A \cap B & \iff & \forall a \in (A \cap B): ( (a \in B) \wedge (a \in B) ) \\ A \setminus B & \iff & \forall a \in (A \setminus B): ( (a \in A) \wedge (a \not\in B)) \end{array}

Relations

Elements can have relations. For example, if elements resemble persons, a relation can be that one person likes some other person, or that one person is married to some other person. To explain relations, we start with the Cartesian product. The Cartesian product is defined between two sets, S and T, and denotes that any element in the set S is related to all elements in set T. Formally:

S \times T = \{ (s,t) \mid s \in S, t \in T \}

Notice that the Cartesian product is a set itself! In the above case, the Cartesian product of A and D results in the following set:

A \times D = \{ (e,j), (e,k), (f,j), (f,k), (g,j), (g,k), (h,j), (h,k) \}

Formally, relations are a subset of the Cartesian product. If the relation equals the Cartesian product, the relation is called total. However, this is rarely the case.

First order logic and set theory