Essential Set-Theoretic Foundations

Before we delve deeper into predicate logic, it’s important to clarify a few essential concepts from set theory. Predicate logic itself relies on some basic set-theoretic notions for its formal definitions and interpretations. This short introduction provides the minimal set theory you’ll need.

Introduction to Sets

A set is a collection of distinct objects, called elements, considered as a single entity.

• Examples:
  • Set of integers \(\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}\)
  • Set of real numbers \(\mathbb{R}\)

Membership and Subsets

• Membership: If an object aa belongs to a set \(A\), we write \(a \in A\).
  • Example: \(3 \in \mathbb{Z}\), \(\pi \in \mathbb{R}\).
• Subsets: A set \(A\) is a subset of another set \(B\) (written \(A \subseteq B\)) if every element of \(A\) is also in \(B\).
  • Example: The set of integers \(\mathbb{Z}\) is a subset of real numbers \(\mathbb{R}\), written as \(\mathbb{Z} \subseteq \mathbb{R}\).

Cartesian Product

The Cartesian product \(A \times B\) of sets \(A\) and \(B\) is the set of all ordered pairs where the first element is from \(A\) and the second from \(B\): \(A \times B = \{(a,b) \mid a \in A, b \in B\}\)

• Example: If \(A = \{1,2\}\) and \(B = \{x,y\}\), then: \(A \times B = \{(1,x), (1,y), (2,x), (2,y)\}\)

Relations and Functions

• A relation between sets \(A\) and \(B\) is a subset of their Cartesian product \(A \times B\).
  • Example: “Less than” relation on integers, represented as: \(\{(x,y) \mid x,y \in \mathbb{Z}, x<y\}\)
• A function from a set \(A\) to set \(B\) assigns exactly one element of \(B\) to each element of \(A\).
  • Formally: \(f: A \rightarrow B\).
  • Example: The square function on integers \(f(x)=x^2\) takes an integer \(x\) and maps it to its square in \(\mathbb{Z}\).

Relations as Subsets

In predicate logic, predicates are interpreted as subsets of Cartesian products. For instance, the predicate “\(<\)” (less than) on integers is the subset of all integer pairs \((x,y)\) where \(x<y\).

---

Exercises

1. Define the set \(A \times A\) explicitly, given \(A = \{0,1\}\).
2. Let \(A = \{1,2,3\}\). Write explicitly the subset defined by the predicate “greater than.”
3. Given sets \(A=\{a,b\}\), \(B=\{1,2\}\), and \(C=\{x\}\), determine \(A\times B\times C\).

These basic set-theoretic concepts are foundational to clearly understanding the semantics of predicate logic, enabling us to rigorously discuss structures and interpretations in logic.