Chapter 0: Logic and Sets

0.1 Propositional Logic

In arithmetic, one studies numbers and how they are combined via operations such as addition and multiplication. In Propositional logic, one studies statements and how they are combined with operations such as and and or.

Start with a collection images/sets1.png of (atomic) statements. Individual statements will be denoted by capital letters: images/sets2.png images/sets3.png images/sets4.png .... So, for example images/sets5.png might be the statement "The sky is blue." and images/sets6.png might be the statement "The area of a circle is images/sets7.png times the radius squared." Each statement can be either true or false. We assume that the statements include one which is known to be true and one which is known to be false; these are denoted images/sets8.png and images/sets9.png

One can combine statements to make additional statements in a number of ways:

is true if and only if that either is true or is true.
is true if and only if that both and are true.
is true is and only if is false.
is true if and only if either is true of is false.
is true if and only if either both A and B are true or else both and are false.

Remark 0.1:

Throughout mathematics, the word or means the inclusive or and not the exclusive or. So is true if and only if at least one of and is true. Exclusive or would imply that not both and are true.
is often expressed as, "If A is true, then B is true." This is exactly the meaning of "If...Then..." in mathematics. However, you should be careful to note that it is only one of multiple possible meanings in everyday language. Another meaning is expressed by, "If you don't obey, you will be punished."

By repeatedly combining the above operations, one can make more and more complex statements. Faced with two complex statements images/sets30.png and images/sets31.png , it is natural to ask if they are equivalent, i.e. Is images/sets32.png true? To answer such questions, we need to develop a set of rules for simplifying statements. Let's begin with some properties of equivalence:

Proposition 1.1: For all statements images/sets33.png images/sets34.png and images/sets35.png

( is reflexive)
( is symmetric) If then
( is transitive) If and then

Proof:One can use the definition of equivalence:

is reflexive because A is true if and only if A is true.
is true if either and are both true or they are both false. But then and are either both true or both false. So is true.
If is true, then either both and are true or they are both false. Suppose and are true. If then it follows that must also be true and so both and are true.
On the other hand, suppose and are both false. If then it follows that must also be false. So both and are both false. In either case, we see that and are both either true or both false. So,

Exercise 1.1: Show that images/sets70.png is reflexive and transitive. Is it also symmetric?

Relations like images/sets71.png which are reflexive, symmetric, and transitive are called equivalence relations. Intuitively, these are the relations which behave like equality.

The next result lists some important equivalent expressions and the proof introduces the important technique of using truth tables:

Proposition 1.2: For all statements images/sets72.png images/sets73.png and images/sets74.png :

(Commutativity) and .
(Associativity) and
(Distributive Laws) and
(True and False) and
(Absorption) and

Proof: For each assertion, just verify that the assertion is true for each of the possible cases of whether images/sets85.png images/sets86.png etc. are true or false. You can summarize the steps in a what is called a truth table. For example, to show that images/sets87.png is commutative, one has the truth table:


false	false	false	false
false	true	true	true
true	false	true	true
true	true	true	true

In the first two columns, each row represents one possible combination of possibilities for the truth or falsehood of images/sets92.png

and

. The subsequent columns are computed from the values in the earlier columns. For example, in the second row, images/sets94.png

is true because images/sets95.png

is false but images/sets96.png

is true. The commutative law is true because, in each row, the values in the third and fourth columns are the same.

For the first distributive law, the truth table for the expression images/sets97.png looks like:


false	false	false	false	false
false	false	true	false	false
false	true	false	false	false
false	true	true	true	true
true	false	false	false	true
true	false	true	false	true
true	true	false	false	true
true	true	true	true	true

The truth table for images/sets103.png

is:


false	false	false	false	false	false
false	false	true	false	true	false
false	true	false	true	false	false
false	true	true	true	true	true
true	false	false	true	true	true
true	false	true	true	true	true
true	true	false	true	true	true
true	true	true	true	true	true

The distributive law asserts that the two expressions are equivalent, and this is true because the values in the last column of corresponding rows always match.

As a final example, the truth table for the first absorption identity is:


false	false	false	false
false	true	false	false
true	false	false	true
true	true	true	true

The rule is correct because the entries in the first and fourth columns of each row are identical.

Exercise 1.2 Complete the proof of this proposition by making all the remaining truth tables.

Exercise 1.3 Use truth tables to prove De Morgan's Laws:

0.2 Sets

A set is a collection of things: For example, one has the set of positive integers, a set of stamps, a set of theorems, etc. The things in the set are called elements of the set. For example, 3 is an element of the set of positive integers. The assertion that images/sets116.png is an element of a set images/sets117.png is written images/sets118.png .

The set images/sets119.png with finitely many elements images/sets120.png images/sets121.png ..., images/sets122.png is written images/sets123.png where we simply list out the elements comma separated between curly brackets. Similarly, one can write

for the set of integers.

Definition 2.1: A set images/sets125.png is a subset of the set images/sets126.png (written images/sets127.png ), if and only if every element of images/sets128.png is an element of images/sets129.png Two sets images/sets130.png and images/sets131.png are equal if and only if each is a subset of the other. A set images/sets132.png is a proper subset of the set images/sets133.png if images/sets134.png is a subset of images/sets135.png and images/sets136.png is not equal to images/sets137.png

Example 2.1:(i) The set of integers is a subset of the set of real numbers because every integer is a real number.

(ii) The empty set images/sets138.png is the set with no elements. The empty set is a subset of every set.

(iii) It is false that 2 is a subset of images/sets139.png In fact, 2 is an integer not a set. On the other hand images/sets140.png is a set with the single element 2; images/sets141.png is a subset of images/sets142.png

We would like to develop a mathematical theory of sets. Choose a particular set images/sets143.png called the universal set. Our theory of sets will deal with subsets of images/sets144.png Whenever, we talk about a set, it will be implicitly assumed that it is a subset of images/sets145.png

Remark: We will change images/sets146.png as is appropriate for the application. For example, when doing geometry in the plane, we might take images/sets147.png to be the set of all points in the plane. If we need real numbers too, we might take images/sets148.png to be the set of all points in the plane and all real numbers. This notion of a universal set is an artifice to avoid a logical anomaly known as Russell's paradox.

Just as in the last section, we will introduce a number of operations:

Definition 2.2: Let images/sets149.png images/sets150.png and images/sets151.png be subsets of the universal set images/sets152.png

The union of and is the set whose elements are all the elements of with or
The intersection of and is the set whose elements are all the elements of with and Two sets are called disjoint if and only if their intersection is the empty set.
The complement of in is the set whose elements are all the elements of with and (The symbol is read not in or not an element of.)
The complement of is the set
The sets and are equal if and only if they have the same elements.

The equality relation is an equivalence relation, i.e.:

Proposition 2.1: For all subsets images/sets180.png images/sets181.png and images/sets182.png of the universal set images/sets183.png

(Equality is reflexive)
(Equality is symmetric) If then
(Equality is transitive) If and then

Proof: Left as an exercise.

Proposition 2.2: For all subsets images/sets190.png images/sets191.png and images/sets192.png of the universal set images/sets193.png

(Commutativity) and .
(Associativity) and
(Distributive Laws) and
(Empty and Universal Sets) and
(Absorption) and

Proof: These are straightforward to verify. For example, to see that intersection images/sets204.png is commutative, you just note that the elements of images/sets205.png and of images/sets206.png are both the set of elements of images/sets207.png which are both in images/sets208.png and in images/sets209.png Similarly, for the second distributive law, the elements of images/sets210.png are the set of elements of images/sets211.png which are in images/sets212.png and either in images/sets213.png or in images/sets214.png . This is the same as the set of elements that are either both in images/sets215.png and images/sets216.png or both in images/sets217.png and images/sets218.png , which is the set of elements of images/sets219.png As an exercise, you should verify all the remaining assertions.

There is a parallel between the set theory operations and the logic operations. With each set A, we can associate the statement images/sets220.png where images/sets221.png is an element of the universal set. Then one has equivalent statements:

This allows one to verify identities or subset relationships using truth tables. For example, for absorption, one has the truth table:


true	true	true	true
true	false	false	true
false	true	false	false
false	false	false	false

Because the first and last columns are the equal, we can conclude that images/sets232.png

is equivalent to images/sets233.png

and so

by the definition of set equality.

Exercise 2.1 Prove De Morgan's Laws:

Hint: For the first assertion, start by assuming that images/sets237.png is an element of images/sets238.png Then images/sets239.png or images/sets240.png If images/sets241.png then images/sets242.png and so images/sets243.png So images/sets244.png On the other hand, if images/sets245.png then images/sets246.png and so images/sets247.png So images/sets248.png Next, assume that images/sets249.png is an element of the right hand side, and show that it must be an element of the set images/sets250.png If you can fill in all the reasons, you will have a proof of the first of the two assertions. Construct a proof of the second one along the same lines. Alternatively, you can use truth tables to make up a proof in a purely mechanical way.

2.3 Boolean Algebras

In the two previous sections, we studied two apparently unrelated subjects: the logic of propositions and the theory of sets. But there is an obvious parallel. Let's formalize the situation reflected by Propositions 1.2 and 2.2 as:

Definition 3.1: A Boolean algebra is a set of with two binary operations + and images/sets251.png and one unary operation - which satisfy the following conditions for all images/sets252.png images/sets253.png and images/sets254.png in the Boolean algebra

(Commutativity) and .
(Associativity) and
(Distributive Laws) and
(0 and 1) There are elements 0 and 1 with and
(Absorption) and

Example 3.1: Propositional logic and set theory are two examples of Boolean algebras.

Duality Principle: If one has any result about Boolean algebras, then one can obtain another result by replacing the operators +, images/sets265.png and the elements 0 and 1 with the operators images/sets266.png , + and the elements 1 and 0 respectively. This new result is called the dual of the original result.

Proof: This transformation maps each condition in the definition of Boolean algebra into another condition. So, if one has proved some result, the proof of the dual result is obtained by replacing each step with the its dual dual.

Rather than continuing to develop Propositional logic and set theory, separately, we can instead work in the context of a Boolean algebra. Any result there will then apply to both of these earlier examples.

Proposition 3.1: In an Boolean algebra images/sets267.png , one has:

For any one has and The dual results and are also true. In particular, and
(Idempotence) For any , one has and the dual result
For any one has
For any and in one has if and only if

Proof: (i) One has

and so the dual result images/sets286.png is also true. In particular, one has images/sets287.png and its dual images/sets288.png One has

and so also its dual images/sets290.png

(ii)

and so the dual images/sets292.png is also true.

(iii) One can calculate

and

(iv) If images/sets295.png then

The dual of this is: If images/sets297.png then images/sets298.png and so the by switching the roles of images/sets299.png and images/sets300.png we get the other half of (iv).

Definition 3.2: If images/sets301.png and images/sets302.png are in a Boolean algebra, then one says that images/sets303.png if and only if images/sets304.png

Remark 3.1 By part (iv) of the last proposition, this condition is equivalent to images/sets305.png

Proposition 3.2: The relation images/sets306.png satisfies:

(Reflexivity)
(Anti-symmetry) If and then
(Transitivity) If and then

Proof: (i) images/sets314.png means images/sets315.png which was proved in Proposition 3.1.

(ii) If images/sets316.png then images/sets317.png If images/sets318.png then images/sets319.png Combining results, we get images/sets320.png

(iii) If images/sets321.png and images/sets322.png then images/sets323.png and images/sets324.png So,

and so images/sets326.png

Definition 3.3: If a binary relation images/sets327.png is reflexive, anti-symmetric, and transitive, it is said to define a partial order.

Remark 3.2: The dual of images/sets328.png is images/sets329.png This means that the dual of images/sets330.png is images/sets331.png So, in forming the dual of an assertion, you need to replace images/sets332.png with images/sets333.png and vice versa.

Proposition 3.3: In a Boolean algebra, if images/sets334.png then images/sets335.png

Proof: Suppose images/sets336.png Then images/sets337.png and multiplying by images/sets338.png gives images/sets339.png Since images/sets340.png one has images/sets341.png On the other hand, multiplying both sides of images/sets342.png by images/sets343.png gives

and so images/sets345.png

Proposition 3.4: (De Morgan's Laws) In a Boolean algebra, one has

Proof: Multiply both sides of images/sets348.png by images/sets349.png to get

The last term on the right can be simplified:

where we have used associativity, commutativity and the fact that the product of any element with its complement is zero. With this simplification, the equation becomes

which just means that images/sets353.png

The dual must also be true: images/sets354.png In particular, this holds when we substitute images/sets355.png and images/sets356.png in place of images/sets357.png and images/sets358.png respectively: images/sets359.png . Since images/sets360.png and images/sets361.png it follows that images/sets362.png Applying the complement to both sides switches the images/sets363.png to images/sets364.png to yield

Using anti-symmetry, we can therefore conclude that images/sets366.png which proves the first of the De Morgan laws.

The second De Morgan law follows from the first by duality.

Example 3.2: Consider the set of factors of the number 30. This is the set images/sets367.png Define the sum of two of these numbers to be the least common multiple of the two numbers and the product of the two numbers to be the greatest common divisor of the two numbers. The complement of the number k is the number 30/k. With these operations, one can verify that our set is a Boolean algebra. It follows that all the results in this section are true of this Boolean algebra.

Exercise 3.1: What plays the role of 0 and 1 in this Boolean algebra? Are there other numbers like 30 with this same property? Are there numbers for which the corresponding set of factors do not form a Boolean algebra?