Logic is the discipline that deals with the methods of reasoning. On an elementary level, logic provides rules and techniques for determining whether a given argument is valid. Logical reasoning is used in mathematics to prove theorems, in computer science to verify the correctness of programs.
In the 1840s Augustus De Morgan, a British mathematician, set out to extend the logic developed by the early Greeks and the others and to correct some of the weaknesses in these ideas. In 1847, a few years after De Morgan’s work on an extended system of logic had appeared, his countryman George Boole published the book THE MATHEMATICAL ANALYSIS OF LOGIC and it was followed by the book AN INVESTIGATION OF THE LAWS OF THOUGHT. Boole’s objective was to investigate the fundamental laws of those operations of the mind by which reasoning is performed; to give expression to them in the symbolical language of calculus and upon this foundation to establish the science of logic and construct its method.
Once we have mathematical definitions of these notions, we can try to prove theorems about these formalized notions. If done with imagination, this process can lead to unexpected rewards. Of course, formalization tends to caricature the informal concepts it aims to capture, but no harm is done if this is kept firmly in mind.
Example. The notorious Goldbach Conjecture asserts that every even integer greater than 2 is a sum of two prime numbers. With the understanding that the variables range over N = {0, 1, 2, . . . }, and that 0, 1, +, ·, < denote the usual arithmetic operations and relations on N, this assertion can be expressed formally as
∀x[(1+ 1 < x∧even(x)) → ∃p∃q(prime(p)∧prime(q)∧x = p+q)]
where even(x) abbreviates ∃y(x = y + y) and prime(p) abbreviates 1 < p ∧ ∀r∀s(p = r · s → (r = 1 ∨ s = 1)). The expression GC is an example of a formal statement (also called a sentence) in the language of arithmetic, which has symbols 0, 1, +, ·, < to denote arithmetic operations and relations, in addition to logical symbols like =, ∧, ∨, ¬, →, ∀, ∃, and variables x, y, z, p, q, r, s.The Goldbach Conjecture asserts that this particular sentence GC is true in the structure (N; 0, 1, +, ·, <). (No proof of the Goldbach Conjecture is known.) It also makes sense to ask whether the sentence GC is true in the structure (R; 0, 1, +, ·, <) where now the variables range over R and 0, 1, +, ·, < have their natural ‘real’ meanings. (It’s not, as is easily verified. That the question makes sense —has a yes or no answer—does not mean that it is of any interest.) A century of experience gives us confidence that all classical number-theoretic results—old or new, proved by elementary methods or by sophisticated algebra and analysis—can be proved from the Peano axioms for arithmetic. 2 However, in our present state of knowledge, GC might be true in (N; 0, 1, +, ·, <), but not provable from those axioms. (On the other hand, once you know what exactly we mean by provable from the Peano axioms, you will see that if GC is provable from those axioms, then GC is true in (N; 0, 1, +, ·, <), and that if GC is false in (N; 0, 1, +, ·, <), then its negation ¬GC is provable from those axioms.) The point of this example is simply to make the reader aware of the notions “true in a given structure” and “provable from a given set of axioms,” and their difference. One objective of this course is to figure out the connections (and disconnections) between these notions.
Sets and Maps
In an axiomatic treatment of set theory as in the book by Halmos all assertions about sets below are proved from a few simple axioms. In such a treatment the notion of set itself is left undefined, but the axioms about sets are suggested by thinking of a set as a collection of mathematical objects, called its elements or members. To indicate that an object x is an element of the set A we write x ∈ A, in words: x is in A (or: x belongs to A). To indicate that x is not in A we write x /∈ A. We consider the sets A and B as the same set (notation: A = B) if and only if they have exactly the same elements. We often introduce a set via the bracket notation, listing or indicating inside the brackets its elements.
For example, {1, 2, 7} is the set with 1, 2, and 7 as its only elements. Note that {1, 2, 7} = {2, 7, 1}, and {3, 3} = {3}: the same set can be described in many different ways. Don’t confuse an object x with the set {x} that has x as its only element: for example, the object x = {0, 1} is a set that has exactly two elements, namely 0 and 1, but the set {x} = {{0, 1}} has only one element, namely x.
(1) The empty set: ∅ (it has no elements).
(2) The set of natural numbers: N = {0, 1, 2, 3, . . .}.
(3) The set of integers: Z = {. . . , −2, −1, 0, 1, 2, . . .}.
(4) The set of rational numbers: Q.
(5) The set of real numbers: R.
(6) The set of complex numbers: C.
Let A and B be sets. Then we can form the following sets:
(a) A ∪ B := {x : x ∈ A or x ∈ B} (union of A and B);
(b) A ∩ B := {x : x ∈ A and x ∈ B} (intersection of A and B);
(c) A r B := {x : x ∈ A and x /∈ B} (difference of A and B);
(d) A × B := {(a, b) : a ∈ A and b ∈ B} (cartesian product of A and B).
Thus the elements of A × B are the so-called ordered pairs (a, b) with a ∈ A and b ∈ B. The key property of ordered pairs is that we have (a, b) = (c, d) if and only if a = c and b = d. For example, you may think of R × R as the set of points (a, b) in the xy-plane of coordinate geometry. We say that A and B are disjoint if A∩B = ∅, that is, they have no element in common.
Maps
Definition. A map is a triple f = (A, B, Γ) of sets A, B, Γ such that Γ ⊆ A×B and for each a ∈ A there is exactly one b ∈ B with (a, b) ∈ Γ; we write f(a) for this unique b, and call it the value of f at a (or the image of a under f). We call A the domain of f, and B the codomain of f, and Γ the graph of f. We write f : A → B to indicate that f is a map with domain A and codomain B, and in this situation we also say that f is a map from A to B. Among the many synonyms of map are mapping, assignment, function, operator, transformation. Typically, “function” is used when the codomain is a set of numbers of some kind, “operator” when the elements of domain and codomain are themselves functions, and “transformation” is used in geometric situations where domain and codomain are equal. (We use equal as synonym for the same or identical; also coincide is a synonym for being the same.)
Examples.
(1) Given any set A we have the identity map 1A : A → A defined by 1A(a) = a
for all a ∈ A.
(2) Any polynomial f(X) = a0 + a1X + · · · + anXn with real coefficients a0, . . . , an gives rise to a function x 7→ f(x) : R → R. We often use the “maps to” symbol 7→ in this way to indicate the rule by which to each x in the domain we associate its value f(x).
