Skip to content
Topos Uranos
English

The language of propositional logic

Summary

This lesson builds, from scratch, the language in which every formula of the course will be written. It first introduces the indispensable minimum about sets (membership, sets given by listing and by set-builder notation, inclusion and union) and applies it to strings of symbols: their length, their concatenation and their prefixes, and the count of the strings that can be written with two symbols. Over the two-symbol alphabet, the circle and the disk, it defines the base language: infinitely many variables, a single formation rule and a closure clause, from which a principle for proving properties of all formulas is derived. It then shows how to decide whether a string is a formula, states unique readability and, finally, builds on the base language the metalanguage that will be used from then on: metavariables, joint denial written with parentheses and the official abbreviations of the other connectives, with their reading in English.

Learning objectives

  1. Describe sets of strings by listing and by set-builder notation, and decide relations of membership, inclusion and union between them.
  2. Count the strings of a given length, and those of bounded length, over a two-symbol alphabet.
  3. Decide whether a string of circles and disks is a formula and, when it is, reconstruct the way it was formed.
  4. Prove that every formula has a property by means of the closure principle, and use such properties to rule out strings.
  5. Distinguish the object language from the metalanguage, unfold an abbreviation down to the string of the base language, and read formulas in English.

What is needed about sets

A formal language is, above all, a collection of strings of symbols; if so, speaking about it with precision requires a vocabulary for collections. That vocabulary is the language of sets, from which this lesson takes only what the course will use. A set is a collection of objects, called its elements, which is determined by them: two sets with the same elements are the same set. That an object aa is an element of the set AA is written a∈Aa \in A and read “aa belongs to AA”; that it is not is written a∉Aa \notin A.

A set can be given in two ways. By listing, naming its elements one by one between braces, with neither order nor repetitions mattering; and by set-builder notation, stating the condition that its elements, and only they, satisfy, with a colon read “such that”. Thus the natural numbers less than 55 form the set

{1,2,3,4}={n∈N:n<5}\{1, 2, 3, 4\} = \{ n \in \mathbb{N} : n < 5 \}

A variant of set-builder notation, very frequent in what follows, describes the elements by the form they have: {2n:n∈N}\{ 2n : n \in \mathbb{N} \} is the set of numbers of the form 2n2n with nn natural, that is, the set of even numbers. A set given by listing is necessarily finite; by set-builder notation infinite sets can be given as well, such as that of the even numbers.

AA is said to be included in BB, written A⊆BA \subseteq B, when every element of AA is an element of BB. It follows that two sets are equal if and only if each is included in the other, because then they have the same elements; and this is indeed the usual way of proving an equality of sets: proving both inclusions. Finally, the union A∪BA \cup B is the set of objects that belong to AA, to BB or to both; whence each of the two sets is included in their union.

ExampleMembership, inclusion and union

Let A={1,2,3}A = \{1, 2, 3\}, B={2,4,6,8}B = \{2, 4, 6, 8\} and P={2n:n∈N}P = \{ 2n : n \in \mathbb{N} \}. We have 2∈A2 \in A and 4∉A4 \notin A; moreover, B⊆PB \subseteq P, because each element of BB is twice a natural number, whereas AA is not included in PP, because 1∈A1 \in A and 1∉P1 \notin P. The union of AA and BB is {1,2,3,4,6,8}\{1, 2, 3, 4, 6, 8\}: the 22, which lies in both, appears only once.