To introduce modern logical theory and reasoning, we will begin by looking at what it means for two things to be "equal". We will then look at propositional logic: determining when logical statements are the equivalent (the same) and when they are true, and when they are different. Next, we will look at how we can describe queries about a collection of items we are discussing, namely our universe of discourse: statements such as one particular question is true for all items being discussed (All Canadians are human) or when a statement is true for at least one item being discussed (There is a Canadian older than 100 years old). Finally, we will reinterpret all this in terms of set theory.

1. Equality

We all intuitively understand the concept of equality, but it is necessary to be a little more precise as to what it means for two items to be equal. To begin, we cannot compare everything, but rather, we will restrict our comparisons of objects to items that we may currently be discussing. This collection or set of items is described as our universe of discourse. For example, how we compare two integers differs from how we compare two rational numbers, which differs again from how we compare two real numbers. We will see that there are different circumstances under which we may want to say that two triangles are "equal." Thus, rather than trying to define equality of arbitrary objects, we will first define our universe of discourse and then define on the objects in that universe a comparison operation we will call an equality if the following four properties hold.

1.1 Relevant properties of an equality

There are four properties of equality that are generally required for a comparison operation to actually represent what we consider an equality, and all of these were generally understood by the ancient Greeks.

1.1.1 Reflexivity

Equality must be reflexive: meaning, for whatever objects we are considering, for each such object x, it must be true that x = x.

With real numbers, we can define x = y if x - y = 0. This operation is reflexive because x - x = 0 for all real numbers.

With real numbers, we can defined x < y. This operation is not reflexive, for 5 < 5 is false.

This is Aristotle's first so-called "law of logic," even if equality has nothing to do with modern definitions of propositional and predicate logic.

1.1.2 Symmetry

Equality must be symmetric: meaning that given two items x and y that are possibly being compared, then x = y if and only if y = x.

With real numbers, if we define x = y if x - y = 0, then if x = y, for y = x, it must be true that y - x = 0. But y - x = (-1)(x - y), and if x - y = 0, then so is y - x, as y - x = (-1)(x - y) = -1·0 = 0.

With real numbers, we can define x ≤ y. This is reflexive, as x ≤ x for all real numbers x, but it is not symmetric, for 3 ≤ 5 is true, but 5 ≤ 3 is false. Thus, while the comparison operation of less-than-or-equal-to is definitely useful, it is not an equality.

1.1.3 Transitivity

If a = b, and b = c, it must follow that a = c.

If a = b and b = c, it is common to write a = b = c. This is Euclid's first common notion with respect to planar geometry.

Note that we can prove the following theorem:

1.1.3.1 Theorem

If a₁ = a₂ and a₂ = a₃ and ··· and aₙ₋₁ = aₙ, then a₁ = aₙ.

Proof:

If n = 1, then a₁ = a₁, so by reflexivity, they are equal.

Assume for n = k that if a₁ = a₂ and a₂ = a₃ and ... and aₖ₋₁ = aₖ, then a₁ = a ₖ.

For n = k + 1, we have a₁ = a₂ and a₂ = a₃ and ... and aₖ₋₁ = aₖ₊ and aₖ = aₖ₊₁, but by assumption, a₁ = aₖ and aₖ = aₖ₊₁, so by transitivity, a₁ = aₖ₊₁.

Thus, by the process of mathematical induction, the statement is true for all n. ▮

With floating-point numbers, it is often useful to suggest that two numbers x and y are equal if |x - y| < ε where ε is a specified positive number. For example, we may consider two numbers to be equal if |x - y| < 10⁻¹². This definition of equality is reflexive, as |x - x| = 0 < ε; it is also symmetric, as |x - y| = |y - x|; however, it is not transitive, as 1 = 1.0000000000005 and 1.0000000000005 = 1.000000000001, but 1 ≠ 1.000000000001, for

|1 - 1.000000000001| = 0.000000000001 = 10⁻¹²,

which is not less than 10⁻¹².

1.1.4 Substitutivity

If a = b and F(x) is an expression involving item an item x in our universe of discourse, then F(a) = F(b).

This is, in a sense, a summary of Euclid's second and third common notions: m = n if and only if both m + a = n + a and m - a = n - a for all positive real values a.

1.2 Examples

Two integers m and n are equal if the are the same integer, otherwise they are unequal.

Two rational numbers a/b and c/d are equal if ad = bc.

Two real numbers x and y are equal if x - y = 0. This is subtly different from comparing two integers, for you may recall that 4.729999··· = 4.73000···.

Suppose we are performing integer arithmetic modulo a prime number p. In this case, two integers m and n are equal if m - n is a multiple of p.

Two triangles may be equal if the coordinates of their corners are equal, or, alternatively, two triangles are equal if one can be translated or rotated (or both) so as to coincide with the other. In the first case, two triangles are equal if and only if they occupy the exact same area of the plane. In the second, two triangles are equal if they are not only similar, but also that the lengths of their sides when read clockwise from smallest side first are all equal. You will note that under this definition, the mirror image of a triangle with three different lengths are unequal.

Alternatively, one could define two triangles as equal if they are similar: that is, one can be translated, rotated, reflected and scaled to match the other. If your only interest is to compare the ratios of the sides, or to apply the cosine law, then this is a perfectly acceptable definition of equality.

1.3 Summary of equality

Following this first topic you now understand what we normally consider to be a definition of equality. We first noted that we must restrict the objects we are comparing to a universe of discourse over which we define can define a comparison operation which is called an equality if and only if it satisfies all four common properties. Specifically, we saw that in geometry, our definition of equality may depend on how we intend to interact with those triangles. This is our first introduction to the axiomatic method. If you have previously studied Euclidean geometry, then you have already seen an axiomatic method, where Euclid's common notions and postulates for the axioms for his geometry. Next, we will look at propositional logic.

2. Propositional logic

There are certain quantifiable statements that may be determined to be true or false, or for all intents and purposes, may be generally determined to be either true or false. The most common of these is in mathematics:

13 < 23
There are infinitely many prime numbers
P = NP

The first is false, the second is true, and the third is either true or false, but the truth of the statement is currently unknown.

We can, however, have more complex statements:

3 < 10 and 124 > 20
5 < 9 and 2 < 0
5 < 9 or 2 < 0
If x > 3, then x² > 9
If x > 0, then sin(x) > 0
x = 5 if and only if x² = 25
x > 0 if and only if x³ > 0
x = 5 if and only if both x² = 25 and x > 0 are true

The first statement is true, because both 3 < 10 and 124 > 20 are true. It is false that both 5 < 9 and 2 < 0 because 2 is positive, and thus greater than zero, but the third is true, because 5 < 9: The statement "I am home or I am at school" is true if I am either home, or if I am at school. The statement "I am home and I am at school" can only be true if your home is at school and you happen to be at school (say, for example, if you live in residence). The statement "x < 5 or x ≥ 5" must be true if x is real, because there are no other alternatives. The fourth statement is true, because if x > 3, then x² > 3² = 9. The fifth statement is false because 5.555 > 0 and yet sin( 5.555 ) = -0.666 < 0. The sixth statement is also false, because x² = 25 if x = 5 or if x = -5, so x² = 25 even if x ≠ 5. The statement if and only if means the left side is true if and only if the right side is true, and yet, if x = -5, then the right side is false, but the left side (-5)² = 25 is true. Consequently, assuming x is a real number, the seventh statement is true, because if x > 0, then x³ > 0, and if x ≤ 0, x³ ≤ 0; consequently, the only time x³ > 0 is when x > 0, and vice versa.

The last statement is interesting, because English can be very ambiguous. For example, if I say "x = 5 if and only if x² = 25 and x > 0" does this mean that "'x = 5 if and only if x² = 25' and 'x > 0'" or "'x = 5' if and only if 'x² = 25 and x > 0'" We will look at these two interpretations:

'x = 5 if and only if x² = 25' and 'x > 0'

The second statement x > 0 currently has an unknown truth value, because we don't have any constraints on x. It may be true, or i tmay be false, but at this point, there is no way of saying one way or the other. However, the first statement is false, because of our argument in a Statement 6 above. Now, if the author of this article told "I have $1,000,000 and I did not author this article", while you may not know the truth value of the first statement (perhaps the author does have $1,000,000 or perhaps the author does not) but by definition the second statement is false. Thus, regardless of the truth of the first statement, because it is "P and Q", the entire statement must be false.

'x = 5' if and only if 'x² = 25 and x > 0'

For this to be true, if x = 5 is true, then the right-hand side must be true; and if x ≠ 5 (that is, x = 5 is false), then the right-hand side must be false. Thus:

If x = 5, then x² = 25 and x > 0, so the right-hand side is true.
If x ≠ 5, then x² = 25 if and only if x = -5, but x > 0, so it is not possible for both statements "x² = 25" and "x > 0" to be true, and thus, the right-hand side must be false.

Thus, we have deduced that the left-hand side is true if and only if the right-hand side is true, and therefore the complete statement "'x = 5' if and only if 'x² = 25 and x > 0'" is also true.

In the statement above, we were however much more precise in our wording: x = 5 if and only if both x² = 25 and x > 0 are true. The statement to the right of "if and only if" is "both x² = 25 and x > 0 are true" and this clearly we mean the second interpretation.

This is equivalent to asking does 5 + 6 × 7 mean 11 × 7 = 77 or 5 + 48 = 53, and when we start interpreting statements mathematically, we will in general use parentheses.

Quick quiz: is the following a true statement? Both x = 5 and x > 0 are true if and only if x² = 25.

We can also make statements about the real world:

Carbon dioxide is comprised of one carbon atom bonded with two oxygen atoms.
Ali is 19 years old.
A person holds a German passport if and only if a person is a German citizen.
A person may hold a German passport if and only if a person is a German citizen.
A person holds a criminal record implies that person has been convicted of a crime.
A person holds a criminal record if and only if that person has been convicted of a crime.
A person holds a criminal record if and only if both a person has been convicted one or more crimes and that person has not been pardoned for all those crimes.
A person holds a driver's licence if and only if that person is 16 years old or older.
If a person holds a driver's licence, that person is 16 years old or older.
Jamie Teather is taller than 6 feet.
Beer is sold by the pint in the UK.
The Earth orbits the Sun.
The gravitational force is G m₁ m₂/r².

You will notice that these all involve definitions, measures (time or distance) or laws imposed by humans.

The first statement is true by definition: CO₂ has a carbon atom and two oxygen atoms.
This statement is true it has been at least 19 years since Ali's birth and not 20 or or more years.
This statement is false: If a person holds a German passport, then that person must be a German citizen. However, a person not holding a German passport may still be a German citizen. My uncle, for example, is German, but he does not currently hold a German passport.
This statement seems true, but is actually still false. A more true statement is "A person may hold a German passport if and only if both that person is a German citizen and that person has not breached any laws forbidding that person to hold a German passport." For example, a German convicted of espionage against the German state may be forbidden from obtaining a German passport. There may indeed be other circumstances whereby a German citizen may not obtain a passport; however, that is beyond the scope of this discussion.
This statement is true: upon conviction of certain crimes, the person is given a criminal record.
This statement is false. See Statement 7.
A person who has a criminal record can apply for a pardon which expunges that criminal record. This is important, because statements about reality may only be true in specific contexts, and even then, there may be exceptions. For example, in Statements 6 and 7, there is an implict assumption by the author that we are discussing such issues in Canada. The laws in other countries may differ. Some countries may not even have the concept of a criminal record, or if they do, those countries may not have the concept of a pardon.
Like Statement 6, this statement is false. A person may not have a driver's licence even if that person is 16-years old or older. One friend of the author did not get his driver's licence until he was in his mid thirties.
This statement has again an implicit assumption that we are discussing residents of Ontario. By law, a person in Ontario under the age of 16 cannot acquire an Ontario driver's licence, regardless of how skilled that individual in driving a car. Thus, if a person does hold a driver's licence, that person must be at least 16 years old. If the person does not hold a driver's licence, this gives us no information as to how old that person is. The person is likely to be younger than 16, as the majority of residents do acquire a (or at least, used to acquire) a beginner's driver's licence around the age of 16, but if the only information you have is that the person does not have a driver's licence, you cannot definitively say anything about that person's age.
This is either true or false, depending on how tall Jamie is. It happens to be true.
This statement is false. A true statement is "The majority of beer sold in bars in the UK is sold by the pint." This means that more than 50% of beers sold at public houses and other establishments in the United Kingdom are sold by the pint.
It would be better to say "The Earth is orbiting the Sun at this moment in time." After all, there was some point in time before our Sun was even a star instead of just a ball of gas, when the gravitational force was sufficient to sustain fusion at the Sun's center, and the Earth was an orbiting pile of gravitationally attracted rubble before it formed the sphere that we know today, and at some point of time in the future, the Earth may or may not be enveloped by an expanding star, after which it may no longer be considered to be "orbiting" the Sun.
This is only Newton's model of the force between two bodies, and if you were looking for a better model, one must apply Einstein's general relativity; and while all evidence has so far suggested that general relative is an accurate model, it may turn out that even general relative may only be an approximation.

Suddenly, we notice how much easier it is to make mathematically true statements than it is to make true statements about real life. There are so many more nuances and subtleties in the real world. Thus, a statement like "If we reduce the number of legal firearms in the hands of denizens in Canada, then violence involving firearms will go down" may be true, but would be very difficult to actually determine if it is true. For example, if illegal firearms continue to be illegally brought into Canada (such as with drones), then these illegal firearms do not increase the number of legal firearms, and yet they almost certainly will contribute to an increase in the latter.

Some qualitative but absolute statements are not even only true or false:

She is tall.
He is a good shot.
The crime rate is low.
Casey is old.

If a woman is 6' tall, then she is likely considered to be 'tall'. If she is 5' tall, then she is likely considered to be 'not tall'. How about 5'8" or 5'9"? Similarly, what is a "good shot"? Is it taking out someone at 2 km? Or even 1 km? Or is it just that that individual can get a 1" grouping at 100 m? Is someone whose grouping at 100 m is 1¼" suddenly not a good shot?

However, it is generally possible to have qualitative but relative statements be true or false:

She is taller than he is.
Susanne Cassidy is a better shot than this author.
The crime rate has gone down from last year.
Casey is older than Ashley.

On the other hand, when a measure cannot be quantified, it may be very difficult to make a truth statement:

He is smart.
She is smarter than he is.

What is "smart"? Without a measure, it is very difficult to even tell what is "smart" is or is not. There are even more bizarre statements, such as "This statement is false" or "You stopped beating your spouse." Thus, like above, we will restrict ourselves to a universe of discourse, and restrict our statements to Boolean-valued statements about objects in that universe of discourse.

2.1 Boolean operators

At this point, we have established that there are some statements that may be true or false, and we will call such statements Boolean-valued statements, as they have a truth value that is either true or false, even if the truth value may currently be unknown. We will represent any Boolean-valued statement by a capital letter like P or Q. Consequently, any of the above statements that are either true or false could be represented by such a letter.

2.1.1 Logical NOT (negation)

Next, note that every Boolean statement can be negated. In English, this may be done in many different ways, as all of the following are ways of negating the statement "Ali is 19 years old."

Ali is not 19 years old.
It is false that Ali is 19 years old.
Ali is 18 years old or younger, or 20 years old or older.

Note that "Ali is 10 years old" is not a negation of the statement "Ali is 19 years old." If Ali is not 19 years old, that does not mean Ali is 10 years old. If P is a statement, we will represent the negation of that statement by ¬P. Thus, if P is a Boolean-valued statement, either P or ¬P is true; while similarly, P and ¬P cannot both be true. Either Ali is 19 years old, or Ali is not 19 years old. Ali cannot both be 19 years old while also not being 19 years old.

We will describe this operation as logical negation and ¬ is the logical not operator. You will note that the symbol looks very similar to negation: given x, -x is the negation of x. Given a logical statement P, ¬P is the negation of that logical statement.

You will note that in some cases we may rewrite a statement, as ¬(x < 3) is equivalent to x ≥ 3, and ¬(x = 4) is equivalent to x ≠ 4 and ¬(x ≤ -5) is equivalent to x > -5.

2.1.2 Logical AND

Next, we saw compound statements such as "x > 5 and x < 10". Both "x > 5" and "x < 10" are statements, so we could represent these as P and Q. We could write the compound statement as "P AND Q", but to be more succinct, we will use the logical AND operator ∧. The easiest way to remember this is observing that it looks like the "A" in AND. Thus, P ∧ Q is true if both P and Q are true. Now, the statement "(x > 5) ∧ (x < 10)" may be true or false depending on the value of x. On the other hand, the statement "(x < 1) ∧ (x > 2)" is necessarily false, for if x < 1, then x < 2, and thus the second statement is false; while if x > 2, then x > 1, so the first is also false.

Now, logical AND is commutative and associative, so P ∧ Q has the same truth value as Q ∧ P, and (P ∧ Q) ∧ R has the same truth value as P ∧ (Q ∧ R). Thus, in essence, any number of statements combined using logical AND (∧) may be combined in any order, so P ∧ Q ∧ R ∧ S ∧ T has the same truth value as S ∧ R ∧ P ∧ T ∧ Q. This statement is true if all five statements P, Q, R, S and T are true, otherwise it is false.

2.1.3 Logical OR

We also saw statements of the form "x < 1 or x > 2", and as above, we could represent both "x < 1" and "x > 2" as statements P and Q, and again, we could write the compound statement as "P OR Q", but one again, we will replace the operator with the logical OR operator ∨. Thus, P ∨ Q is true if either P or Q is true. If x = 1.5, then the compound statement is false, but if x = 0.5 or x = 2.5, the statement is true.

Like the logical AND operator, the logical OR operator is also commutative and associative, so P ∨ Q has the same truth value as Q ∨ P, and (P ∨ Q) ∨ R has the same truth value as P ∨ (Q ∨ R). Thus, P ∨ Q ∨ R ∨ S ∨ T has the same truth value as T ∨ S ∨ R ∨ P ∨ Q. This statement is false if all five statements P, Q, R, S and T are false, otherwise it is true (if even one of the statements is true).

2.1.4 Logical IMPLIES (implication)

The next statement we saw were compound statements that were conditional on the first statement, so for example, "if x > 2, then x² > 4" or "if it is raining, there are clouds in the sky." In the first case, "x > 2" and "x² > 4" are the two statements, and "it is raining" and "there are clouds in the sky" is the second. Both these are true, for if the first statement is true, we may infer that the second must also be true. If x ≤ 2 or it is not raining, the statements say nothing about the value of x² or the existence of clouds in the sky. On the other hand, the statement "if x > 0, then sin(x) > 0" is false, for if x = 5.555, then x > 0 is true, and yet sin(x) = -0.666 and -0.666 ≤ 0. Thus, we may not infer the second statement if the first statement is true.

We could write this as "IF P, THEN Q" or "P IMPLIES Q", but instead we will use the more succinct notation P → Q.

The IMPLIES operator is not commutative, as P → Q may be true, but Q → P is false. For example "if there are clouds in the sky, it is raining" is a false inference, for at this very moment, the author is looking out the window and sees clouds in the sky, and yet it is not raining. Also, (x² > 4) → (x > 2) is also false, for if x = -3, then x² = 9 > 4, and yet x ≤ 2. Interestingly enough, the correct inference is (x² > 4) → ((x < -2) ∨ (x > 2)); that is, if x² > 4, then either x < -2 or x > 2, and there are no other possibilities.

The IMPLIES operator is used in discourse and mathematical proofs as follows: if the implication P → Q is true, then

if it can be shown that P is true, then Q must be true, and
alternatively, if it can be shown that Q is false, then P must also be false.

Again, if P is false, Q may be true or false.

Just to work this out:

If it is raining, there are clouds in the sky, and
it is raining;
therefore, there are clouds in the sky.

If it is raining, there are clouds in the sky, and
the sky is clear;
therefore, it is not raining.

If it is raining, there are clouds in the sky, and
it is not raining;
therefore we cannot determine if there are or are not clouds in the sky.

You can work this out as well with mathematical statements, such as if |x|< ½π, then cos(x) > 0.

As |-1|< ½π, thus, cos(-1) > 0.
If cos(x) ≤ 0 then |x|< ½π is false, so |x| ≥ ½π.
|x| ≥ ½π, then this rule of inference says nothing about the sign of cos(x).

Now, one small point: P → Q is equivalent to ¬P ∨ Q. For example,

Either it is not raining or there are clouds in the sky. A logical OR statement is false if both sides are false, so this compound logical statement is false if it is raining and there are no clouds in the sky; however, if it is raining, there are clouds in the sky.
(|x|≥ ½π) ∨ (cos(x) > 0). This is false if |x|< ½π and cos(x) ≤ 0; however, if the first statement is true, then we know cos(x) is positive.

2.1.5 Logical IF-AND-ONLY-IF (equivalence)

The last compound statement we saw was of the form "P IF-AND-ONLY-IF Q" or "P IS-EQUIVALENT-TO Q" means that P is true if Q is true, and P is false if Q is false. We will write this using the logical EQUIVALENT-TO operator ↔, so P ↔ Q.

Recall above that we described equality. You will notice that the logical EQUIVALENT-TO operator satisfies all the properties of an equality. Thus, rather than writing P = Q, we say P ↔ Q. To explain why we use ↔ instead of =, I suspect this is a consequence of the separate development of arithmetic and logic, and ↔ also hints at the fact that P ↔ Q is itself equivalent to both P → Q and Q → R being true. Consequently, we can actually write P ↔ Q as (¬P ∨ Q) ∧ (P ∨ ¬Q).

2.1.6 Summary of logical operators

You will recall that there were many operators associated with arithmetic: given integers, there is +, -, ×, ÷ but there is also exponentiation, unary minus -x, and the factorial operation n!. Now, we are restricting ourselves to something even easier: instead of integers, there are two values we call true and false, and each statement P, Q, R, S, ... is required to have such a value, even if that value is not known. With these values, we have one logical unary operator ¬ that negates the truth value of what it is a applied to (just like -(x + yz) negates the result of x + yz), and four operators ∧, ∨, → and ↔.

Like equality, there are axioms for logical operators:

Both logical AND and logical OR are both commutative and associative.
Each distributes over the other, so like x(y + z) = xy + xy, so does [P ∧ (Q ∨ R)] ↔ [(P ∧ Q) ∨ (P ∧ R)] and [P ∨ (Q ∧ R)] ↔ [(P ∨ Q) ∧ (P ∨ R)].
Like 0 + x = x and 1 × y = y, it is also true that (false ∨ P) ↔ P and (true ∧ P) ↔ P.
Like x + (-x) = 0 and x × (1 ÷ x) = 1, it is also true that (P ∧ ¬P) ↔ false and (P ∨ ¬P) ↔ true.
P ∧ (P ∨ Q) ↔ P, meaning the result only depends on P; for example, "I am 5'11" and either I am 5'11" or there is a canary on my shoulder" is true if I'm 5'11" and false if I am not 5'11": it doesn't matter if there is a canary on my shoulder or not.
P ∨ (P ∧ Q) ↔ P, meaning the truth only depends on P; for example, "Either I am 5'11" or both I am 5'11" and my hair is pink" is true if I'm 5'11" and false if I am not 5'11": it doesn't matter if my hair is pink or not.

2.2 Tautologies

The most useful applications of Boolean logic are tautologies; that is statements that are guaranteed to be true regardless of the truth values of any of the statements. We have already seen a few tautologies, but we have not yet named them as such, but we will involve tautologies that first include equivalencies, and we will then look at tautologies that involve implications. Before we look at these, there are some trivial ones: P ∨ ¬P, that is, either P or ¬P must be true. Similarly, ¬(P ∧ ¬P) says that it is false that both P and ¬P can be simultaneously true.

2.2.1 Equivalencies

An equivalency P ↔ Q says that if the left-hand side is true, then the right-hand side must be true, and if the left-hand side is false, so must the right-hand side. If it is established that the equivalency is valid, you may show that either the left-hand side or the right-hand side is true or false to establish the truth of the other side. If you can ever demonstrate that the left-hand and right-hand sides have different truth values, then the equivalency is invalid.

Equivalencies are often useful when you want to establish the truth of one proposition, but it is easier to establish the truth of the other side of an equivalent proposition. For example, we will see that if you want to establish that P → Q is a valid implication, it may be easier to establish that ¬Q → ¬P is a valid implication; or if you want to show that P → Q is an invalid implication, then it may be easier to argue that ¬Q → ¬P is an invalid implication; because, as we will see, P → Q is equivalent to ¬Q → ¬P: "if you are a good student, you will get good marks" is equivalent to "if you are not getting good grades, you are are a bad student." The first may sound reasonable, but it is much easier to find a counter-example for the second: I know many individuals whom I consider good students who simply, for one reason or another, get poor grades. This suggests the second is a false implication, and therefore the first is also false: it is possible to find a good student who gets poor grades (that is, the individual is a good student and never-the-less gets low grades).

2.2.1.1 (P ∨ Q) ↔ (Q ∨ P)

The truth of the left-hand side must be the same as the truth of the right-hand side; so saying "I am home or I'm at work" is equivalent to saying "I'm at work or I am at home." If you either at home or at work, both of these statements are true, and if you are anywhere else, both statements are false.

2.2.1.2 (¬¬P) ↔ P

This says that the negation of the negation of P has the same truth value of P itself. If P is true, then ¬P is false, and thus ¬¬P must again be true. This parallels the arithmetic equation -(-x) = x. Me not being not at home, this is equivalent to me being at home.

2.2.1.3 (P ↔ Q) ↔ (Q ↔ P) ↔ (¬P ↔ ¬Q) ↔ (¬Q ↔ ¬P)

This says that P and Q are equivalent (have the same truth value) if and only if Q and P are equivalent if and only if ¬P ↔ ¬Q are equivalent if and only if ¬Q ↔ ¬P are equivalent. Thus, for example, if a lightning strike occurs within one kilometer of me, I see lightning if and only if I hear thunder is equivalent to me not hearing thunder if and only if I don't see lighting.

2.2.1.4 ¬(P ∧ Q) ↔ (¬P ∨ ¬Q)

Suppose P and Q is true, in which case, P ∧ Q is true. The negation of P ∧ Q is therefore false. If P and Q are both both true, then ¬P and ¬Q are both false, and false ∨ false is false. However, suppose at least one of P and Q is false. In this case, P ∧ Q is also false, so the negation is therefore true. If at least one of P and Q is false, then at least one of ¬P and ¬Q are true, and the logical OR of two statements, at least one of which is true is also true.

For example, suppose it is false that I am reading a book and watching television; this is equivalent to saying I am not reading a book or I am not watching television or both.

Notice that we can take the negation of both (from the previous tautology), so we get ¬¬(P ∧ Q) ↔ ¬(¬P ∨ ¬Q), and using the tautology (¬¬P) ↔ P, we get that (P ∧ Q) ↔ ¬(¬P ∨ ¬Q). Suppose P ∧ Q is true, in which case, both P and Q are true, in which case, ¬P and ¬Q are both false. The logical OR of two false statements is false, and the negation of a false statement is true. Thus, proving P and Q to be true is equivalent to proving that not P or not Q is false.

We can also show this with a truth table, where we give the statements all possible combinations of true and false, and then see if in all cases, the evaluation of ¬(P ∧ Q) and ¬P ∨ ¬Q is the same:

P Q P∧Q ¬(P∧Q) ¬P ¬Q ¬P∨¬Q

F F F T T T T

F T F T T F T

T T T F F F F

T F F T F T T

Using a truth table is a brute force approach to determining if two statements are equivalent, but useful.

2.2.1.5 ¬(P ∨ Q) ↔ (¬P ∧ ¬Q)

This is similar to the previous tautology, only now it says: if P ∨ Q is false, then both ¬P and ¬Q must be true.

P Q P∨Q ¬(P∨Q) ¬P ¬Q ¬P∧¬Q

F F F T T T T

F T T F T F F

T T T F F F F

T F T F F T F

If you can argue that both P is false and Q is false, then P or Q must be false.

2.2.1.6 (P → Q) ↔ (¬P ∨ Q)

We have already discussed this one, but saying "If it is raining, there are clouds in the sky" is the same as saying "It is either not raining or there are clouds in the sky." An implication is false if it is ever true that the left-hand side is true but the right-hand side is false.

P Q P→Q ¬P ¬P∨Q

F F T T T

F T T T T

T T T F T

T F F F F

2.2.1.7 (P → Q) ↔ (¬Q → ¬P)

This tautology says that P → Q is a valid implication if and only if ¬Q → ¬P is also a valid inference. Suppose a car impacts a solid wall, then "if the car was travelling at less than 5 km/h, then the car will still be drivable" versus "If the car is not drivable, it was travelling at 5 km/h or faster."

P Q P→Q ¬Q ¬P ¬Q→¬P

F F T T T T

F T T F T T

T T T F F T

T F F T F F

Each side is the contrapositive of the other side.

You will notice that the entire statement is actually of the form R → (P → Q), for it is "If a car impacts a solid wall, then if that car was travelling at less than 5 km/h, then that car will still be drivable." This leads to the next tautology.

2.2.1.8 (P → (Q → R)) ↔ ((P ∧ Q) → R) ↔ (Q → (P → R))

This is likely the first tautology that is not obvious: recall that the previous statement was

If a car impacts a solid wall, then if that car was travelling at less then 5 km/h, then that car will still be drivable.

This is equivalent to saying

If a car both impacts a solid wall and was travelling at less than 5 km/h, then that car will still be drivable.

But not only that, this is equivalent to saying

If a car was travelling at less than 5 km/h, then if the car impacts a solid wall, then the car will still be drivable.

We will only show the first two are equivalent, for if the first two are equivalent, then so are the second and third, as (P ∧ Q) ↔ (Q ∧ R)

P Q R Q→R P→(Q→R) P∧Q (P∧Q)→R

F F F T T F T

F F T T T F T

F T T T T F T

F T F F T F T

T T F F F T F

T T T T T T T

T F T T T F T

T F F T T F T

In case you are familiar with C/C++/Java programming, the following two are equivalent structures:

if ( condition-1 ) {

if ( condition-2 ) {

// Do something

}

if ( condition-1 && condition-2 ) {

// Do something

}

2.2.1.9 (P ↔ Q) ↔ ((P → Q) ∧ (Q → P))

We will look at one penultimate truth table of an equivalence we already saw: that P is equivalent to Q if and only if both P implies Q and Q implies P:

P Q P↔Q P→Q Q→P (P→Q)∧(Q→P)

F F T T T T

F T F T F F

T T T T T T

T F F F T F

Thus, one can prove that two statements are equivalent if the truth of one implies the truth of the other, and the truth of the other implies the truth of the first. However, there is another approach to such a proof, as we will see next.

2.2.1.10 (P ↔ Q) ↔ ((P → Q) ∧ (¬P → ¬Q))

Recall the contrapositive, so if we take the tautology (Q → P) ↔ (¬P → ¬Q), and substitute this equivalence into the tautology (P ↔ Q) ↔ ((P → Q) ∧ (Q → P)), we get the tautology we see above. This gives another proof for showing an equivalence: P and Q are equivalent if and only if P implies Q and P being false implies Q is false, too. Hopefully this is obvious, but we includde a truth table for completeness. Note that if we want to show that P is equivalent to Q and we find Q → P but we also find ¬P → ¬Q is false, then we may deduce that P is not equivalent to Q.

P Q P↔Q P→Q ¬P ¬Q ¬P→¬Q (P→Q)∧(¬P→¬Q)

F F T T T T T T

F T F T T F F F

T T T T F F T T

T F F F F T T F

2.2.2 Implications

Next, we will look at implications, so that if the implication is valid, if the left-hand side is true, the right-hand side must also be true; and if the right-hand side is false, the left-hand side must also be false. However, if it is ever the case that the left-hand side is true while the right hand side is false, then we have an invalid implication.

2.2.2.1 (P ∧ (P → Q)) → Q

If P is true and P → Q is a valid implication, then Q must be true; however, if Q is false, then either P is false or P → Q is an invalid implication.

"There are clouds in the sky, and if there are clouds in the sky, it is raining; therefore it is raining." This is of course false, and in this case, the only possibility is that the implication is false.

2.2.2.2 ((P → Q) ∧ ¬Q) → ¬P

If P → Q is a valid implication but Q is false, then P is false; however, if P is true, then either Q is true or P → Q is an invalid implication.

2.2.2.3 ((P → Q) ∧ (Q → R)) → (P → R)

If P → Q is a valid implication and Q → R is a valid implication, then P → R is a valid implication; however, if P → R is an invalid implication, then at least one of the two implications on the left-hand side is an invalid implication. This is called a syllogism, as the right-hand side id deducdd from the two implications on the left. [(P₁ → P₂) ∧ (P₂ → P₃) ∧ ··· ∧ (Pₙ₋₁ → Pₙ)] → (P₁ → Pₙ)

2.2.2.4 ((P ∨ Q) ∧ ¬P) → Q

If P or Q is true and P is false, then Q must be true. Alternatively, if Q is false, then P must be true.

2.2.2.5 ((P → Q) ∧ (R → S)) → ((P ∨ R) → (Q ∨ S))

If both P → Q and R → S are valid implications, then either of P or R being true must imply either Q or S are true. If, however, the right-hand side is an invalid implication, then one of the two implications on the left-hand side must also be invalid.

2.2.2.6 (P → ¬P) → ¬P

This is a proof by contradiction: if assuming P is true demonstrates that P is false, then P is false. However, if P is true, then the implication P → ¬P must be invalid.

This is used to prove, for example, that there are infinitely many prime numbers. You assume that there are finitely many prime numbers; however, you can then show that if this is what is assumed, then there are not finitely many prime numbers, and thus we conclude there are not finitely many prime numbers.

2.2.3 Summary of tautologies

We have looked at a number of tautologies. These can be used in arguments either by providing valid premises and valid implications, or to demonstrate a premise or a given implication is false.

2.3 A summary of propositional logic

In this topic, we've described the ideal of a Boolean-valued statement: one that is either true or false. We then described five logical operators that can be used to manipulate or join statements, creating compound Boolean-valued statements. We then looked at various tautologies: statements that are true regardless of the truth value of any individual statement P, Q, R, etc. These tautologies can be used to either substitute one expression with an equivalent statement, or to derive consequences from existing statements.

3. Predicate logic

We have previously discussed in our section on equalities the concept of a universe of discourse; that is, the total collection of items under discussion. Given an item x or y in our universe of discourse, a Boolean-valued function, or predicate, of these items is a function P(x) or P(y). For each item in our universe of discourse, a predicate must have one and only one truth value: true or false. Thus, we are significantly reduced as to the number of valid statements we may consider: we are only interested in statements about items in our universe of discourse.

We can now proceed to create compound Boolean-valued statements, such as (P(x) ∧ Q(x)) → P(x), so we may repeat all the previous statements we discussed in the previous section, only now they are restricted to predicates on our universe of discourse. We will say that two predicates P and Q are equal if and only if P(x) ↔ Q(x) for all x in our universe of discourse, and if this is the case, we will write P = Q. Note that "↔" is used to compare two Boolean values (true or false) while a predicate is a Boolean-valued statement, and thus, we will revert to using the more traditional "=" operator.

We may however now make statements about some or all of the items in our universe of discourse. For example, one predicate may be true for all items in our universe of discourse, another predicate may be false for all items in our universe of discourse, a third predicate may be true for at least one item in our universe of discourse, and a fourth predicate may be false for at least one item in our universe of discourse.

All adult humans are taller than one foot tall.
No adult humans are taller than ten feet tall.
There exists a human who is over six feet tall.
There exists a human who is less than four feet tall.

You will notice that 3 and 4 do not exclude the possibility that either every human is over six feet tall, or every human is less than four feet tall, they only state that there is there is at least one human who satisfies (evaluates to true for) these two predicates.

Important: We need to assume our universe of discourse is not empty: we must be discussing at least one item.

For all x, a predicate statement is true

To state that all x in our universe of discourse satisfy some predicate evaluates to true (that is, P(x) is true for all x), we will write ∀x:P(x). We can also use implication to restrict what is true: ∀x:(P(x) → Q(x)). This says, for all x such that P(x) is true, then Q(x) is also true. If we want to write that a predicate P(x) evaluates is false for all x, we can write ∀x:¬P(x).

You can remember the symbol ∀ as it is an upside-down "A" as in "for All."

This operator is ∀ is also known as the universal quantifier: it states that some predicate is true for all items in the universe of discourse.

There exists an x for which a predicate statement is true

To state that there is at least one x in our universe of discourse satisfy some predicate evaluates to true, we will write ∃x:P(x). If we want to write that some predicate evaluates to false for at least one x, we can write ∃x:¬P(x). This says nothing about how many such x exist, so if you wanted to say that two items satisfy some condition, you would say ∃x: ∃y:[(x ≠ y) ∧ P(x) ∧ P(y)]; that is, there exists an x and there exists a y such that they are unequal and each satisfies the predicate P. In general, however, and very fortunately it is not that necessary to discuss exact numbers.

You can remember the symbol ∃ as it is a reversed "E" as in "there Exists."

This operator is ∀ is also known as the existential quantifier: it states that some predicate is true for at least one items in the universe of discourse.

3.1 Negating quantifiers

Suppose the statement ∀x:P(x) is false; so in other words, ¬∀x:P(x) is true. But if it is false that P(x) is true for all x, then there must be at least one x such that P(x) is false, or in other words:

¬∀x:P(x) ↔ ∃x:¬P(x)

Similarly,

¬∃x:P(x) ↔ ∀x:¬P(x)

Now, we can continue with this: We can always replace P(x) with ¬¬P(x) (as P(x) ↔ ¬¬P(x)) in ∃x:P(x), so

∀x:P(x) ↔ ∀x:¬¬P(x) ↔ ¬∃:¬P(x)

and

∃x:P(x) ↔ ∃x:¬¬P(x) ↔ ¬∀:¬P(x)

Thus,

P(x) is true for all x is equivalent to it is false that there exists an x such that P(x) is false, and
P(x) is true for at least one x is equivalent to it being false that for all x, P(x) is false.

3.2 Syllogisms

We have seen previously that ((P → Q) ∧ (Q → R)) → (P → R). We could say the following:

3.2.1 { [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∀x:P(x) → R(x)]

This says that if for all x, P(x) → Q(x) and for all x, Q(x) → R(x); then it must be true that for all x, P(x) → R(x).

Notice that we are not guaranteed that there are any x that satisfy any of these:

All humans taller than 15 feet are taller than 14 feet, and all humans taller than 14 feet are taller than 13 feet;
thus all humans taller than 15 feet are taller than 13 feet.

This is completely correct, except that there are no humans who are taller than 15 feet. Thus, we may want to emphasize that there is at least one x such that P(x) is true:

{ [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∀x:P(x) → R(x)]

Now, if there exists an x such that P(x) is true, and if P(x) implies Q(x) and Q(x) implies R(x), then that one x must also satisfy R(x), so we may now say the following:

3.2.2 { [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → { [∀x:P(x) → R(x)] ∧ [∃x:P(x) ∧ R(x)] }

That is, if the left-hand side is true, then not only is the first statement on the right-hand side true, but so is the second: there exists an x such that both P(x) and R(x) are true. We actually have an easier version of this:

3.2.3 { [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] } → { [∃x:P(x) ∧ Q(x)] }

We have another variation:

3.2.4 { [∃x:P(x) ∧ Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∃x:P(x) ∧ R(x)]

How about the following?

{ [∀x:P(x) → Q(x)] ∧ [∃x:Q(x) ∧ R(x)] } → [∃x:P(x) ∧ R(x)]

Unfortunately, no such x may exist that satisfies P(x). How about the following?

{ [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] ∧ [∃x:Q(x) ∧ R(x)] } → [∃x:P(x) ∧ R(x)]

Again, the x that satisfies both Q(x) and R(x) may not have been the x that originally satisfied P(x).

Thus, we have seen four different statements that are true, and the three we are interested in are:

{ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∀x:P(x) → R(x)]
{ [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → { [∀x:P(x) → R(x)] ∧ [∃x:P(x) ∧ R(x)] }
{ [∃x:P(x) ∧ Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∃x:P(x) ∧ R(x)]

Substitution of a statement with its negation

In each of these, we could replace any P(x), Q(x) or R(x) with ¬P(x), ¬Q(x) or ¬R(x), respectively; for example:

{ [∀x:¬P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∀x:¬P(x) → R(x)]
{ [∃x:P(x)] ∧ [∀x:P(x) → ¬Q(x)] ∧ [∀x:¬Q(x) → R(x)] } → { [∀x:P(x) → R(x)] ∧ [∃x:P(x) ∧ R(x)] }
{ [∃x:P(x) ∧ Q(x)] ∧ [∀x:Q(x) → ¬R(x)] } → [∃x:P(x) ∧ ¬R(x)]

These say:

If both first for all x, P(x) being false implies Q(x) is true and second for all x, Q(x) being true implies R(x) is true;
then for all x, P(x) being false implies R(x) is true.
If all three that first there exists an x such that P(x) is false, second for all x, P(x) being true implies Q(x) is false, and third for all x, Q(x) being false implies R(x) is true;
then both for all x, P(x) being true implies R(x) is true and there exists an x such that P(x) and Q(x) are true, are true.
If both first there exists an x such that both P(x) and Q(x) are true, and second for all x, Q(x) being true implies that R(x) is false,
then there exists an x such that P(x) is true and R(x) is false.

Thus, each of these three statements can be replaced by eight variations, with none, some or all the predicates being negated.

Applying the contrapositive

Finally, we may use the contrapositive often to simply reverse the conditions, but the statement is identical:

{ [∀x:¬Q(x) → P(x)] ∧ [∀x:¬R(x) → ¬Q(x)] } → [∀x:¬R(x) → P(x)]
{ [∃x:P(x)] ∧ [∀x:Q(x) → ¬P(x)] ∧ [∀x:¬R(x) → Q(x)] } → { [∀x:¬R(x) → ¬Q(x)] ∧ [∃x:P(x) ∧ R(x)] }
{ [∃x:P(x) ∧ Q(x)] ∧ [∀x:R(x) → ¬Q(x)] } → [∃x:P(x) ∧ ¬R(x)]

These say:

If both first for all x, Q(x) being false implies P(x) is true and second for all x, R(x) being false implies Q(x) is false;
then for all x, R(x) being false implies P(x) is true.
If all three that first there exists an x such that P(x) is false, second for all x, Q(x) being true implies P(x) is false, and third for all x, R(x) being false implies Q(x) is true;
then both for all x, R(x) being false implies P(x) is false and there exists an x such that P(x) and Q(x) are true, are true.
If both first there exists an x such that both P(x) and Q(x) are true, and second for all x, R(x) being true implies that Q(x) is false,
then there exists an x such that R(x) is true and P(x) is false.

Changing the order of any statements that are combined by a logical AND operator

Finally, if the left-hand side is two statements combined by a logical AND operator, you can swap them. If the statement inside the existential quantifier is two statements combined by a logical AND operator, you can swap them. In all cases, the meaning is entirely unchanged.

A commentary on Aristotle

You may also notice that we applied the contrapositive here to each implication, although we did not have to. Thus, there are many dozen of possible combinations, all of which are true statements. Incidentally, you may remember that Aristotle chose out of these many dozen twenty-four chosen implications that he identified as "special." Unfortunately, there is much wasted repetition in Aristotle's syllogisms, for if "Some x are y" in Aristotle's arcane terminology, then "Some y are x." We would simply say that the logical AND operator is symmetric. Consequently, Aristotle did not actually identify a minimal set of syllogisms that one need remember, and he additionally misses some others, as well. Thus, instead of memorizing twenty-four arbitrarily chosen syllogisms, you may remember that:

You must remember the three syllogisms identified above.
You may substitute any predicate P(x) with ¬P(x).
You can apply to the contrapositive to any implication.
You may swap the order of any statements joined by a logical AND operator.

3.3 Another example

Another example of a tautology in propositional logic is ((P → Q) ∧ (R → S)) → ((P ∨ R) → (Q ∨ S)). We can interpret this in terms of predicate logic using two different approaches:

{ [∀x:P(x) → Q(x)] ∧ [∀x:R(x) → S(x)] } → {∀x:[P(x) ∨ R(x)] → [Q(x) ∨ S(x)]}

{ [∀x:P(x) → Q(x)] ∧ [∃x:R(x) ∧ S(x)] } → {∃x:[P(x) ∨ R(x)] ∧ [Q(x) ∨ S(x)]}

However, we cannot apply the existential quantifier to both, as the x that exists for the first may not be the same x that exists for the second.

A commentary on Aristotle

If one was to use Aristotle's terminology, "if all P are Q and all R are S, then all that are P or R are Q or S." This, however, cannot be proved using with only Aristotle's syllogisms.

3.4 A third example

You may recall the tautology (P → ¬P) → ¬P. This can be written as follows:

[∀x:P(x) → ¬P(x)] → ∀x:¬P(x)

For example, for all prime numbers, assuming that prime number p is the largest prime number, you can prove that p is not the greatest prime number, and therefore, for all prime numbers, none is the largest prime number.

3.5 A fourth example

Recall the contraposition (P → Q) ↔ (¬Q → ¬P). This can be interpreted with quantifiers as follows:

[∀x:P(x) → Q(x)] ↔ [∀x:¬Q(x) → ¬P(x)]

3.6 A summary of predicate logic

Predicate logic involves Boolean-valued questions or predicates on a given universe of discourse. All of the tautologies of propositional logic apply to the results of these predicates return either true or false values on items in the universe of discourse. We then introduce two quantifiers: one that says that a particular predicate statement holds for all x in our universe of discourse, and another that says that that predicate statement holds for at least one item x in our universe of discourse. We are therefore able to generalize the statements that Aristotle started with in his introduction of logic thousands of years ago.

4. Set theory

The final step in logic is the concept of a set. We will represent the universe of discourse by 𝒰. An equality is defined so that given two items in this universe of discourse, either x = y or x ≠ y. We will indicate that an item x is in our universe of discourse by writing x ∈ 𝒰. You can think of this script "E" as meaning "x is and Element of 𝒰."

Next, a set within this universe of discourse 𝒰 is a collection of unique items where each item is an element of 𝒰. We will represent sets by script capital letters, such as 𝒫, and if an item x is an element of 𝒫, we will write x ∈ 𝒫. If 𝒫 is a set in 𝒰, then (x ∈ 𝒫) → (x ∈ 𝒰); however, different sets may contain different elements. If x ∈ 𝒰 but x is not an element of a set 𝒫, we will write x ∉ 𝒫. Again, in general, when we are discussing sets, we will always have a universe of discourse to which we refer. The universe of discourse itself is a set: it is the set of all items in that universe 𝒰. For this reason, the universe of discourse is sometimes referred to as the universal set.

For example, one universe of discourse may be the collection of all lower-case letters, and we will write these as

𝒰 = {a, b, c, d, e, f, g, h, i, j, ..., x, y, z}.

Any collection of letters in 𝒰 forms a set. For example, 𝒱 = {a, e, i, o, u, y} is the set of all vowels. 𝒟 = {a, d, e, g, h, i, l, m, o, r, s, u, w} is the set of all letters in this author's name.

There is a very cool relationship between predicates and sets. Given a predicate P(x) on a universe of discourse, this defines a set 𝒫 within that universe as the collection of all items in that universe for which P(x) is true. We can write this as 𝒫 = {x:P(x)}; that is, 𝒫 is the set of all x in our universe of discourse such that P(x) is true.

On the other hand, every set defines a predicate, so given a set 𝒮 in our universe of discourse, we may define a predicate S(x) on our universe of discourse where S(x) ↔ x ∈ 𝒮; that is, S(x) is true if and only if x ∈ 𝒮.

We will say that two sets 𝒫 and 𝒬 are "equal" if and only if (x ∈ 𝒫) ↔ (x ∈ 𝒬).

Thus, we may think of a set as a generalization of a predicate. For a predicate, we must come up with a true-or-false question. Sets simply discard the need for explicitly finding that question, and instead, just describe the predicate by the entries in the set. For each set 𝒮 we will define a corresponding predicate S(x) and each predicate defines a corresponding set 𝒮.

Two sets in particular are the universe of discourse 𝒰 and the set containing no entries of 𝒰. This empty set can be written as {}, indicating that it has no items, but more generally, it is written as Ø. The slashed "O" harkens to the fact that, as we will see, the empty set in many ways works the same way as zero (0) does for integers.

The set-valued complement

Given a set 𝒫, we will define its complement 𝒫' which is defined as all items in 𝒰 such that that item is not 𝒫. If P is the corresponding predicate for the set 𝒫, then 𝒫' = {x:¬P(x)} = {x:x ∉ 𝒫} = {x:¬(x ∈ 𝒫)}; that is, all x in our universe for which P(x) is false, or equivalently all x that are not in 𝒫, or all x such that x ∈ 𝒫 is false. You will note therefore that 𝒰' = Ø and Ø' = 𝒰. Note that given a set, the complement is also a set, so we call this operator a set-valued operator.

Note the name "complement" (and not compliment). This contains the word "complete", so the complement is that set that completes what already is given.

You may observe that this complement operator on sets is very similar to negation in Boolean logic. We will continue to define operators on sets such that each operator on a set has an analogous operation on Boolean values.

The Boolean-valued subset operator

Suppose we have two sets 𝒫 and 𝒬 such that every item that is an element of 𝒫 is also an element in 𝒬. If this is the case, we will then say that 𝒫 is a subset of 𝒬 and write 𝒫 ⊆ 𝒬. For any two sets, either 𝒫 ⊆ 𝒬 or 𝒫 ⊈ 𝒬. Also, notice that all sets are subsets of the universal set, and the empty set is a subset of all sets, so ∀𝒫:((Ø ⊆ 𝒫) ∧ (𝒫 ⊆ 𝒰)); that is, for all sets 𝒫, both the empty set is a subset of 𝒫 and 𝒫 is a subset of the universal set.

Now, observe the following: (𝒫 ⊆ 𝒬) ↔ ∀x:[(x ∈ 𝒫) → (x ∈ 𝒬)] ↔ ∀x:[P(x) → Q(x)]. That is, 𝒫 is a subset of 𝒬 if and only if an item is an element of 𝒫 implies that that element is in 𝒬.

We can now demonstrate that the empty set is a subset of all sets:

Let 𝒫 be any set in our universe of discourse. Substituting Ø and 𝒫 into our definition of a subset, we get:

(Ø ⊆ 𝒫) ↔ ∀x:[(x ∈ Ø) → (x ∈ 𝒫)]

Because x ∈ Ø is false for all x, then we have essentially false → (x ∈ 𝒫), and this is always true. Thus, the right-hand side is always true regardless of which set 𝒫 we have chosen. Thus, the left-hand side is also always true, so Ø ⊆ 𝒫 for any set 𝒫.

We can also demonstrate that all sets are subsets of the universal set or universe of discourse:

Let 𝒫 be any set in our universe of discourse. Substituting 𝒫 and 𝒰 into our definition of a subset, we get:

(𝒫 ⊆ 𝒰) ↔ ∀x:[(x ∈ 𝒫) → (x ∈ 𝒰)]

Because x ∈ 𝒰 is true for all x, then we have essentially (x ∈ 𝒫) → true, and this is also always true. Thus, the right-hand side is always true regardless of which set 𝒫 we have chosen. Thus, the left-hand side is also always true, so 𝒫 ⊆ 𝒰 for any set 𝒫.

The set-valued union operator

Suppose we have two sets 𝒫 and 𝒬 and we would like to define the set that contains all items that are either an element of 𝒫 or an element of 𝒬, or possibly both. We will call this the union of 𝒫 and 𝒬 and write it as 𝒫 ∪ 𝒬.

Notice that we can define the union as follows:

𝒫 ∪ 𝒬 = {x:(x ∈ 𝒫) ∨ (x ∈ 𝒬)} = {x:P(x) ∨ Q(x)}

Notice that the union operator ∪ looks like the letter "U", but also it "points" the same direction as the logical OR operator ∨. Like the complement, the union of two sets is a set, and therefore this is a set-valued operator.

Note that for all sets 𝒫, the union of 𝒫 and its complement is the universal set: ∀𝒫:[(𝒫 ∪ 𝒫') = 𝒰)].

The set-valued intersection operator

Suppose we have two sets 𝒫 and 𝒬 and we would like to define the set that contains all items that are both an element of 𝒫 and an element of 𝒬. We will call this the intersection of 𝒫 and 𝒬 and write it as 𝒫 ∩ 𝒬.

Notice that we can define the union as follows:

𝒫 ∩ 𝒬 = {x:(x ∈ 𝒫) ∧ (x ∈ 𝒬)} = {x:P(x) ∧ Q(x)}

Notice that the intersection operator ∩ opens in the opposite direction of ∪, just like the logical AND operator ∧ points in the opposite direction of the logical OR operator ∨. Thus, in a sense, ∩ resembles ∧ and ∧ resembles the "A" in AND, and the intersection is all items that are in one set AND the other set.

Note that for all sets 𝒫, the intersection of 𝒫 and its complement is the empty: ∀𝒫:[(𝒫 ∩ 𝒫') = Ø)].

Tautologies interpreted using sets

For many but not all tautologies, there is an equivalent statement for sets:

(P ∨ Q) ↔ (Q ∨ P)

𝒫 ∪ 𝒬 = 𝒬 ∪ 𝒫

(P ∧ Q) ↔ (Q ∧ P)

𝒫 ∩ 𝒬 = 𝒬 ∩ 𝒫

(¬¬P) ↔ P

𝒫'' = 𝒫

(P ↔ Q) ↔ (Q ↔ P) ↔ (¬P ↔ ¬Q) ↔ (¬Q ↔ ¬P)

(𝒫 = 𝒬) ↔ (𝒬 = 𝒫) ↔ (𝒫' = 𝒬') ↔ (𝒬' = 𝒫')

¬(P ∧ Q) ↔ (¬P ∨ ¬Q)

(𝒫 ∩ 𝒬)' = 𝒫' ∪ 𝒬'

This one might not be obvious, but the complement of the intersection equals the union of the complements.

¬(P ∨ Q) ↔ (¬P ∧ ¬Q)

(𝒫 ∪ 𝒬)' = 𝒫' ∩ 𝒬'

(P → Q) ↔ (¬P ∨ Q)

(𝒫 ⊆ 𝒬) ↔ (𝒫' ∪ 𝒬 = 𝒰)

That is 𝒫 is a subset of 𝒬 if and only if the union of the complement of 𝒫 and 𝒬 is the universal set.

(P → Q) ↔ (¬Q → ¬P)

(𝒫 ⊆ 𝒬) ↔ (𝒬' ⊆ 𝒫')

(P → (Q → R)) ↔ ((P ∧ Q) → R) ↔ (Q → (P → R))

This author is still thinking about how to convert this into set notation. Certainly the middle is (𝒫 ∩ 𝒬) ⊆ ℜ.

(P ↔ Q) ↔ ((P → Q) ∧ (Q → P))

(𝒫 = 𝒬) ↔ [(𝒫 ⊆ 𝒬) ∧ (𝒬 ⊆ 𝒫)]

(P ↔ Q) ↔ ((P → Q) ∧ (¬P → ¬Q))

(𝒫 = 𝒬) ↔ [(𝒫 ⊆ 𝒬) ∧ (𝒫' ⊆ 𝒬')]

(P ∧ (P → Q)) → Q

[(𝒫 ≠ Ø) ∧ (𝒫 ⊆ 𝒬)] → (𝒬 ≠ Ø)

((P → Q) ∧ ¬Q) → ¬P

[(𝒫 ⊆ 𝒬) ∧ (𝒬 = Ø)] → (𝒫 = Ø)

((P → Q) ∧ (Q → R)) → (P → R)

[(𝒫 ⊆ 𝒬) ∧ (𝒬 ⊆ ℜ)] → (𝒫 ⊆ ℜ)

((P ∨ Q) ∧ ¬P) → Q

[(𝒫 ∪ 𝒬) ∩ 𝒫'] ⊆ 𝒬

((P → Q) ∧ (R → S)) → ((P ∨ R) → (Q ∨ S))

[(𝒫 ⊆ 𝒬) ∧ (ℜ ⊆ 𝒮)] → [(𝒫 ∪ ℜ) ⊆ (𝒬 ∪ 𝒮)]

(P → ¬P) → ¬P

(𝒫 ⊆ 𝒫') → (𝒫 = Ø)

This is interesting: the only set that is a subset of its complement is the empty set!

Finally, we can also discuss our syllogisms. Recall the three syllogisms:

{ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∀x:P(x) → R(x)]
{ [∃x:P(x)] ∧ [∀x:P(x) → Q(x)] ∧ [∀x:Q(x) → R(x)] } → { [∀x:P(x) → R(x)] ∧ [∃x:P(x) ∧ R(x)] }
{ [∃x:P(x) ∧ Q(x)] ∧ [∀x:Q(x) → R(x)] } → [∃x:P(x) ∧ R(x)]

In set theory, these say:

[(𝒫 ⊆ 𝒬) ∧ (𝒬 ⊆ ℜ)] → (𝒫 ⊆ ℜ)
[(𝒫 ≠ Ø) ∧ (𝒫 ⊆ 𝒬) ∧ (𝒬 ⊆ ℜ)] → { (𝒫 ⊆ ℜ) ∧ [(𝒫 ∩ ℜ) ≠ Ø] }
{ [(𝒫 ∩ 𝒬) ≠ Ø] ∧ (𝒬 ⊆ ℜ) } → [(𝒫 ∩ ℜ) ≠ Ø]

Any set can be replaced by its complement in the above three, any statement of the form 𝒫 ⊆ 𝒬 may be replaced by 𝒬' ⊆ 𝒫', and any statement of the form 𝒫 ∩ 𝒬 may be replaced by 𝒬 ∩ 𝒫.

There are many other great and interesting features of set theory, and this is just the start. Here are some other theorems:

(𝒫 ∩ 𝒫) = 𝒫 = (𝒫 ∪ 𝒫)

(𝒫 ⊆ 𝒬) ↔ [(𝒫 ∩ 𝒬) = 𝒫] ↔ [(𝒫 ∪ 𝒬) = 𝒬] ↔ (𝒬' ⊆ 𝒫')

(𝒫 ∩ 𝒬) ⊆ 𝒫 ⊆ (𝒫 ∪ 𝒬)

(𝒫 ∩ 𝒬) ∩ ℜ = 𝒫 ∩ (𝒬 ∩ ℜ)

(𝒫 ∪ 𝒬) ∪ ℜ = 𝒫 ∪ (𝒬 ∪ ℜ)

(𝒫' ∪ 𝒬)' ∪ (𝒫' ∪ 𝒬')' = 𝒫

[𝒫 ∪ (𝒫 ∩ 𝒬)] = 𝒫 = [𝒫 ∩ (𝒫 ∪ 𝒬)]

The reader is welcome try to proves these, or at least convince the reader's self that these are indeed true statements.

5. Representing sets

Often, sets may be described, so all Canadian citizens of voting age. However, in other cases, we may use special symbols. For example, the set of all real numbers is represented by R, and the set of all integers is represented by Z (from the German word for the integers Zahlen).

If we want to represent a set of only a few objects, we may use a comma-separated list of the elements in the set surrounded by curly braces, so for example, {2, 3, 5, 7} represents the set of the four single-digit prime numbers. We may use ellipsis to let the reader infer missing enteries, so {_, a, ..., z, A, ..., Z} represents the set of all characters that are valid first characters in a C++ identifier. The set of all ASCII characters that appear on a standard keyboard may be represented by {a, ..., z, A, ..., Z, 0, ..., 9, ~, `, !, @, #, $, %, ^, &, *, (, ), _, -, +, =, {, }, [, ], |, \, :, ;, ", ', <, >, ,, ., ?, /}. Of course, this is a little awkward, as one of the characters is itself a comma, generally this works quite well.

Other sets that are often of interests are intervals of the real line, so [a, b] represents all real numbers x such that a ≤ x ≤ b, (a, b) represents all real numbers x such that a < x < b, [a, b) represents all real numbers x such that a ≤ x < b, and (a, b] represents all real numbers x such that a < x ≤ b. All of these are subsets of the real line. For a single real number [a, a], we will just use {a}. If the interval includes the end-point, we say that that side of the interval is closed, and otherwise it is open, so (a, b) is an open interval while [a, b] is a closed interval. A single number {a} is closed.

We can also use, for example, [a, ∞), (a, ∞), (-∞, b) or (-∞, b] to represent all real numbers x such that x ≥ a, x > a, x < b or x ≤ b, respectively. Note that ∞ is not a real number, so you cannot have, for example, [1, ∞].

Finally, if we have established a universal set 𝒰, we can also have the set {x : P(x)}, which is all x that satisfy the predicate given. The ":" can be read as the words "such that", so if we are discussing real numbers, then {x : x² - 2 > 0} is the set of real numbers x such that x² - 2 > 0, or in other words, all real numbers x such that (x < -√2) ∨ (x > √2). Alternatively, you could also write this as (-∞, -√2) ∪ (√2, ∞).

Question: what is {x : sin(x) ≥ 0}? This would be infinitely many closed intervals ··· ∪ [-4π, -3π] ∪ [-2π, -π] ∪ [0, π] ∪ [2π, 3π] ∪ [4π, 5π] ∪ ··· . Again, the reader is asked to infer the pattern.

6. Functions between sets

Given two universal sets 𝒰 and 𝒱, a function is a rule that maps each element x ∈ 𝒰 to an to an element y ∈ 𝒱. You are most likely familiar with polynomials and trigonometric functions such as sine and cosine. These are all functions that map the real numbers onto the real numbers, so for example, the function p(x) = x² + 1 maps 3 onto the value 10, and we write p(3) = 10. sin(1) is a real number approximately equal to 0.8414709848 and cos(0.842) is another real number approximately equal to 0.666.

Suppose we have one universal set equal to all cars, and another universal set of all humans. Given a car x, we could define h(x) to be the human who owns the car x. This is not a function, because some cars are owned by businesses, and others are not owned by anyone (they are abandoned). Thus, this does not define a function. However, suppose the first set is equal to all legally owned private cars in Canada. In this case, because any legally owned private car can only be owned by one person (the person listed on the ownership papers), then this defines a function.

A function f that maps one universal set 𝒰 to a second universal set 𝒱 will be succinctly described as f : 𝒰 → 𝒱. We will say that 𝒰 is the domain of f, and 𝒱 is the co-domain (the complementary domain). Given an x ∈ 𝒰, if we write f(x), we will say that x is the argument and whatever x is mapped to in 𝒱 will be said to be the image of x under the function f.

Thus, for example, sin:R → R, as does any polynomial p, so p:R → R. Note that the relation g(x) = 1/x is not a function g:R → R, as there is no real number equal to 1/0. Technically, we would say g: (-∞, 0) ∪ (0, ∞) → R, that is, the reciprocal function maps all real numbers other than 0 to the real numbers.

The easiest functions are constant functions, where if y ∈ 𝒱, we will define the function χ[y] : 𝒰 → 𝒱 as that function such that χ[y](x) = y for all x ∈ 𝒰. For example, χ[1.5] : R → R is the real-valued function of a real variable where χ[1.5](x) = 1.5 for all real arguments x.

Onto

A function f : 𝒰 → 𝒱 must have an image in 𝒱 for every x ∈ 𝒰 for it to be a function. However, it is not necessary that for every y ∈ 𝒱 that there is even a single x ∈ 𝒰 such that f(x) = y. For example, if we consider χ[0] : R → R then χ[10](x) = 10 for all arguments x, and there is no real number x such that, for example, χ[10](x) = 3. Similarly, if we have the polynomial p:R → R defined by p(x) = x², there is no x such that p(x) = -1. As one final example, given sin:R → R, there is no x such that sin(x) = 1.00000000000001.

However, some functions f have the property that for each y ∈ 𝒱, there is at least one x such that f(x) = y. Example include x³, x sin(x) and x(x - 1)(x + 1). We will say that such functions are onto because they map onto every point in the co-domain 𝒱. Using logic, we can say ∀y ∈ 𝒱 ∃x ∈ 𝒰: f(x) = y, or in English, for every y in 𝒱 there exists an x in 𝒰 such that f(x) = y.

One-to-one

A function f : 𝒰 → 𝒱 must have a unique image in 𝒱 for every x ∈ 𝒰 for it to be a function, so it cannot be that f(3) = 4 right now, and ten minutes later, f(3) = 7. However, it is not necessary that for every y ∈ 𝒱 that there is a unique x ∈ 𝒰 such that f(x) = y. For example, if we consider χ[0] : R → R then χ[10](3) = 10 and χ[10](7) = 10, and indeed, every point is mapped to 10. Similarly, if we have the polynomial p:R → R defined by p(x) = x², then both p(-1) = p(1) = 1, so two real numbers map to 1. As one final example, given sin:R → R, there is are infinitely many points x such that sin(x) = 0, including ···, -2π, -π, 0, π, 2π,···.

However, some functions f have the property that for each y ∈ 𝒱, there is at most one x such that f(x) = y. Examples include the exponential function exp(x) and the polynomial p where p(x) = x³ + x. Using logic, we can say ∀x₁ ∈ 𝒰 : ∀x₂ ∈ 𝒰 : [(f(x₁) = f(x₂)) → (x₁ = x₂)], or in English, for all x₁ and x₂ in 𝒰, if f(x₁) = f(x₂) then x₁ = x₂.

One-to-one and onto

A function f : 𝒰 → 𝒱 is said to be one-to-one and onto if for every y ∈ 𝒱 there is a unique x ∈ 𝒰 such that f(x) = y. Notice that if f is one-to-one and onto, then we can define an inverse function f ⁻¹: 𝒱 → 𝒰 where f ⁻¹(y) = x where x is that unique value in 𝒰 such that f(x) = y. For example, the polynomial p(x) = x is clearly one-to-one and onto, and its inverse is p⁻¹(y) = x. The polynomial q(x) = x³ is one-to-one and onto, and its inverse is q⁻¹(y) = ³√x.

Now, given 𝒰 = {1, 2, 3, 4} and 𝒱 = {a, b, c, d}, there are 4⁴ = 256 different functions f : 𝒰 → 𝒱 and only 4! = 24 of those are one-to-one and onto (why?). What is the inverse of the function that maps f(1) = c, f(2) = a, f(3) = d and f(4) = b?

6. Cardinality

Given a set 𝒫, we will say that the number of elements in the set is finite if you can count them, and card(𝒫) is the number of elements in that set. When you are counting, you essentially say that one element is the first, another is the second, and so on and so forth. Thus, to formalize the process, we will say that card(𝒫) = n if and only if there is a one-to-one and onto map between 𝒫 and the set {1, 2, ..., n}. If such an integer n exists, then we will say that card(𝒫) is finite. Otherwise, it is infinite.

Two sets have therefore have the same cardinality if there is a one-to-one and onto mapping between the two sets.

If there is a one-to-one and onto mapping between a set and the integers, we will say the set is countable, even if there are infinitely many things, for we can assign each element a unique integer identifying it.

Believe it or not, the real numbers are not countable. There are clearly infinitely many real numbers, but there are also more real numbers than there are integers. If the reader finds this interesting, the reader can easily search YouTube for a demonstration of this proof.

7. Power sets, ordered pairs and Cartesian products

Given a universe of discourse or universal set 𝒰, we have describes sets within this universal set. However, we can also now consider the set of all subsets of 𝒰, or the power set of 𝒰. For example, if our universe of discourse is all single-digit prime numbers {2, 3, 5, 7}, then we can list all subsets of this set: {}, {2}, {3}, {5}, {7}, {2, 3}, {2, 5}, {2, 7}, {3, 5}, {3, 7}, {5, 7}, {2, 3, 5}, {2, 3, 7}, {2, 5, 7}, {3, 5, 7}, {2, 3, 5, 7}. You might notice that as the original set had four elements, the set of all subsets of these four numbers has 16 = 4² different sets. The universe of discourse of the power set is a set of sets, so {{}, {2}, {3}, {5}, {7}, {2, 3}, {2, 5}, {2, 7}, {3, 5}, {3, 7}, {5, 7}, {2, 3, 5}, {2, 3, 7}, {2, 5, 7}, {3, 5, 7}, {2, 3, 5, 7}}

Given our universe of discourse or universal set, we have described sets; however, we can also define an ordered pair (x, y) as a set within our universe. We could simply define an ordered pair, but it would be much more satisfying if we were able to simply have an ordered pair as a set so as to not introduce a new concept. We will therefore define the ordered pair (x, y) to represent the set {{x}, {x, y}}. Thus, (1, 2) is represented by the set {{1}, {1, 2}} and (1, 1) is represented by the set {{1}, {1, 1}} = {{1}, {1}} = {{1}}.

Now, given two different sets 𝒰 and 𝒱, we can define the Cartesian product of these two sets 𝒰 × 𝒱. This is the set of all ordered pairs (x, y) where x ∈ 𝒰 and y ∈ 𝒱. Note that card(𝒰 × 𝒱) = card(𝒰) card(𝒱). You'll notice, however, that the Cartesian product is simply, again, a set of sets of sets, so given 𝒰 = {0, 1}, the Cartesian product 𝒰 × 𝒰 is {(0, 0), (0, 1), (1, 1), (1, 0)} and from the definition of an ordered pair above, it is

{ {{0}}, {{0}, {0, 1}}, {{1}}, {{1}, {0, 1}} }.

You will note this set has four unique elements. What this hints at, and what Russell and Whitehead demonstrate, is that the concepts of logic and sets are sufficient to describe most (if not all) of mathematics. Fortunately, however, today we use concepts such as real numbers, complex numbers, rational numbers, matrices, vectors, etc., to significantly simplify life; however, the basis of mathematics is logic and set thoery.

8. Summary

In summary, this page has introduced you to modern theories of logic by first introducing the axioms of equality. Next, we looked at propositional logic, and then went on to predicate logic and its universal and existential quantifiers. We finished by looking at a generalization of this through set theory and then looking at some ideas about set theory.