A layperson looks at this and sees an incomprehensible mess. A mathematician looks at this and says, "Well, yeah, obviously." A layperson or mathematician who doesn't want to admit they don't comprehend this will also shrug and say, "Well, yeah, obviously." But I don't want you to be one of those people. The problem is that symbolic logic, if you're unfamiliar with it, can be really intimidating on the surface. But I promise you that at the end of this short video, you'll understand everything that's going on here and agree that yes, this is obviously true.
This video is intended as a primer on first-order logic to help students who are learning this subject for the first time. If it's something that you're already familiar with, this might not be the video for you. Or maybe you'll see a fresh perspective, new ways of thinking about, or new ways to teach the material that you'd never considered before. I probably shouldn't discourage people from watching my own video, but I just want to be upfront about what this video entails.
Mathematical logic is the study of the truth of mathematical statements, which we call propositions. Much of what we'll learn today can be applied in non-mathematical contexts as well. A proposition is a claim that can either be true or false. So if I take a number like x and I make the claim "x equals 1," then this is a proposition because x is either one or it is not one—it's true or false. If y is also a number, then "x is less than y" is also a proposition; it's a claim that's either true or false.
Propositions can be true or false but never both—that's known in logic as the law of non-contradiction. Propositions must either be true or false; there is no middle ground. That's a law known as the law of excluded middle because there's no middle territory. The other law that you'll find at the foundation of logic is the law of identity, which says that for any entity x, x is always equal to x.
I should note here that propositions should not be subjective, and it sometimes depends on how the terms are defined. For example, for the proposition "I like pi" to be valid and non-subjective, it depends on how the terms are defined. Am I talking about the number π or am I talking about the food pie? Either way, the proposition is true because who doesn't like π and who doesn't like pie?
Fortunately, mathematical propositions rarely stray into that kind of subjective territory. The worst that can happen is something like stating "zero is a natural number." There's no broad consensus as to whether zero is included in the natural numbers, so it's really up to the author. Another example might be "one is prime," which we would all say is false, but I spent a whole video discussing how sometimes it is and sometimes it isn't.
Just like how in algebra I can let x and y be numbers and then combine them with the usual operations to create new numbers, I can also do the same with propositions. So if I let p and q be propositions, then I have some operations I can do to combine these to make new propositions.
The first one is "or." P or Q is true whenever P is true, Q is true, or if they're both true. It's only false when both P and Q are false. I can actually draw up all the combinations of true and false here to show you exactly when this is true in something called a truth table.
For example, if I say "x is greater than 2 or y is less than 5," then this overall statement is true if one or both of these conditions hold. Let's look at the case where x is 3 and y is 6. Then it is true that either x is greater than 2 or y is less than 5, because one of them holds.
"And" is in contrast to "or." The proposition "P and Q" is true if both P and Q are true, and false otherwise. If I go back to the earlier example and change this from an "or" to an "and," now I'm saying "x is greater than 2 and y is less than 5." This overall statement with these numbers is now false because it requires both conditions to be satisfied to be true overall.
It's common in symbolic logic to use a V-shaped symbol for "or" and an inverted V-shape for "and." This is my personal way of remembering which is which—the inverted V looks like the letter N in "and." In fact, in the UK, it's common to use "n" as an abbreviation for "and" in terms like "fish n chips" (or maybe that's just up north where none of us talk proper).
These concepts should align with your intuition. If I made a statement like "the bus was late and it was raining," then your mind automatically paints a picture of both conditions—me standing in the rain and mildly upset that the bus hasn't arrived yet. Or if you know me personally, you're picturing me more than a little mildly upset at the current state of UK public transportation services.
"Or" should align with your intuition as well. If I said "I'd like to drink tea or I'd like to drink coffee," then you suppose that I'd be happy drinking tea, that I'd be happy drinking coffee, or that I'd be happy with both drinks (though probably not simultaneously). What might perturb your intuition a little bit is that an "or" statement is true if one of the input statements is true, and we don't really care which one. A classic (and I use the term generously) joke is: a logician gives birth and is asked "Is it a boy or a girl?" and they respond "Yes."
Another logical operator is "not" or negation. If P is a proposition, then "not P" is true exactly when P is false, and false exactly when P is true. For example, if P is the proposition "x is equal to 1," then "not P" would be the proposition "x is not equal to 1." If P is the proposition "x is greater than 1," then "not P" is the proposition "x is not greater than 1"—and of course, the usual way to say this is "x is less than or equal to 1." Don't forget about the "or equal to!" We use this symbol (¬) for negation, and I have no idea why. Maybe because whoever first used it felt really sorry for that one key on the keyboard that's used for literally nothing else.
The final logical connective, and one that's crucial to the study of mathematics, is "implies." This encodes the notion that one statement follows logically from another. "P implies Q" is often read as "if P then Q."
Now, brace yourself, because the first time you see this, it might look a bit strange, but it does make sense—I promise. "P implies Q" is true whenever:
- P and Q are both true, or
- P is false The only situation in which "P implies Q" is false is if P is true yet Q is false.
Hopefully, that should feel intuitive because it doesn't really make sense for Q to follow logically from P if we can possibly have a situation in which P is true yet Q is still false.
This might seem a little bit strange. Usually, people are comfortable with the idea that if P implies Q, then when P is true, Q must be true. But surely Q couldn't be true even when P is false if this is supposed to be following logically? Let me convince you a few different ways why this is indeed the case.
One way to think about it is this: if P is true, then Q should automatically be true if Q follows logically from P. But in situations where P is false, we can't conclude anything about Q.
Consider this: "Greg is a cat" implies "Greg is a mammal." That seems to follow because if the first statement is true and Greg is a cat, then we know it's definitely a mammal because every cat is a mammal. But think about these other situations: imagine if Greg is not a cat. Well, then we can't conclude anything about its nature as a mammal. Greg could be:
- A non-cat non-mammal (like an octopus or a house)
- A non-cat mammal (like a platypus) It's a one-way implication—cat implies mammal, but non-cat doesn't necessarily imply non-mammal.
A mathematical example might be "x is a multiple of 4" implies "x is even." That definitely follows because every multiple of 4 is even. But if x is not a multiple of 4, so this first statement is false, then we can't say anything about x's parity. X could be:
- Not a multiple of 4 and odd (like 5 or 7)
- Not a multiple of 4 and still even (like 2 or 10) So "multiple of 4" implies "even," but "not multiple of 4" doesn't imply "odd" or "even"—both situations are valid.
A visual way to think about implications is like this: imagine this board represents all possible situations—everything that could possibly happen, or ever happen, or will happen, or has happened is represented by some position on this board. Inside this blob are the situations in which P is true. If this is a situation outside the blob, P is false; if it's inside this P space, then P is true.
Now, let's think about what it looks like if P implies Q. Since whenever P is true, Q is automatically true, how are we going to draw the blob representing Q? The only real way to do it is to draw a blob where P is nested inside Q. That way, whenever P is true, Q is automatically true—whenever we're inside the P space, we're automatically inside the Q space.
Look at what this tells us:
- If P is true (we're inside the P space), Q is automatically true (we're automatically inside the Q space)
- If P is false (we're outside the P space), we don't know anything about whether Q is true—we could be inside the Q space or outside the Q space
- The only impossible situation is if P is true yet Q is false (being inside the P space yet outside the Q space)
This visual representation is beneficial because we also use implications to describe when one set is a subset of another. If we say that this small circle is the set A and it's contained within the set B, logically we say "A is a subset of B" or "A is contained in B" if "x is in A" implies "x is in B." If x is an element of A, it should automatically be an element of B, but if x is not a member of A, we don't really care about whether it's in B.
When thinking about subsets, it's worth noting that most often in mathematics, we're dealing with situations in which we know the first statement is true. When writing a proof, for example, we often either know P is true or we assume P to be true, and we string together implications to conclude that the consequences are also true.
Let me show you a classic example where we know the first statement is false. This is proving that the empty set is a subset of any set A. This works because A is a subset of B if this implication holds: "x is in the empty set" implies "x is in A." This implication is always true because the first statement is always false—"x is in the empty set" is always false, as the empty set is defined as the set that contains no elements. Since this is always false, this implication is always true, so by definition, the empty set is always a subset of any given set A. This kind of implication is known as a vacuous implication, where the first statement is always false—not often encountered in mathematics, but sometimes.
Something magic happens when we're in the situation that P implies Q and Q implies P. We often nest these situations together with a special symbol (⟺), a double arrow, and we read this as "P if and only if Q." This is true whenever both statements are true or whenever both are false. We say that P and Q are logically equivalent because the exact circumstances under which P is true are identical to the circumstances under which Q is true—they're effectively both saying the same thing.
-
The Factor Theorem: If a is a root of a polynomial f(x), then (x - a) is a factor of that polynomial. To have a root and to have a linear factor are one and the same—if you have a root a, then you know (x - a) is a factor, and if you have a factor (x - a), then you know that a is a root.
-
Matrix Invertibility: If M is a matrix, M is invertible if and only if the determinant of M is not zero. They mean the same thing—if M is invertible, it will have non-zero determinant, and if it has non-zero determinant, it will be invertible.
-
Pythagorean Theorem: We all learn at school that if a triangle is right-angled, then a² + b² = c² will hold true (where c is the length of the hypotenuse). But actually, the other way round works as well—if you happen to have a triangle in which a² + b² = c², then it must be a right-angled triangle.
A common error that students make is assuming that if an implication holds in one direction, then the implication holds in the other direction. But this isn't true. The statement "P implies Q" and its converse "Q implies P" are two different things. We've seen some examples of implications working in both directions, like in the Factor Theorem or the Pythagorean Theorem, but it's not always the case. In fact, I would say most of the time it isn't.
-
"x is a multiple of 4" implies "x is even" is true, but "x is even" does not imply "x is a multiple of 4" because it could be an even non-multiple of 4 like 6.
-
"x is greater than 10" implies "x is greater than 5." However, the other direction doesn't hold—"x is greater than 5" does not necessarily mean "x is greater than 10" because x could be a number like 6 or 7 or τ.
-
Lagrange's Theorem for Groups: If H is a subgroup of G, then the order of H divides the order of G. But not the other way around—if I have a subset H of G where the cardinality of H happens to divide the cardinality of G, that does not necessarily mean that H is a subgroup of G.
-
In real analysis: If a function is differentiable, then it's continuous, but not every continuous function is differentiable.
We use blackboard bold notation to represent different sets of numbers:
- ℕ for natural numbers (positive integers, sometimes including zero)
- ℤ for integers (whole numbers)
- ℚ for rational numbers (fractions)
- ℝ for all real numbers
- ℂ for complex numbers
- 𝔸 for algebraic numbers
- ℍ for quaternions
Let's examine two different types of propositions:
- "n is an integer and n² = 4"
- "n is an integer and 1 is a factor of n"
The key difference is that the first one is only true for certain values of n, whereas the second one is true regardless of which integer n we choose.
The backwards E (∃) stands for "there exists." The statement "∃n ∈ ℤ : n² = 4" claims "there exists an integer n with n² equal to 4." This is true because such an integer does exist (n = 2 or n = -2). We only need one example to prove an existential claim.
The inverted A (∀) means "for all" or "for every." The statement "∀n ∈ ℤ : 1|n" claims "for all integers n, 1 is a factor of n." This requires an algebraic proof since it's making a claim about every possible integer—we can't just list examples.
The order of quantifiers matters. Consider these statements:
-
"∀x ∈ ℝ ∃y ∈ ℝ : x < y" means "for all real numbers x, there exists a real number y with x less than y." This is true because for any x, we can always find a larger y (e.g., x + 1).
-
"∃x ∈ ℝ ∀y ∈ ℝ : x < y" means "there exists a real number x that is less than all real numbers y." This is false because no such x exists—for any x, we can find a smaller number (e.g., x - 1).
Adding an exclamation mark to the existential quantifier (∃!) means "there exists a unique." For example:
- "∃!n ∈ ℤ : n² = 4" is false because both 2 and -2 satisfy this.
- "∃!n ∈ ℤ : n² = 0" is true because 0 is the only integer with this property.
Now that you understand all these concepts, you can see why the original statement is true—for all real numbers x, if x is not zero, then there exists a unique real number y such that xy = 1. Every non-zero real number has exactly one reciprocal that multiplies with it to give 1.
Thank you for watching. During the writing process for this video, my patrons and I were trying to come up with propositions that could act as hooks for this video. Why not try flexing your logical muscles and prove them true or false? Let me know your answers in the comments.
A huge thank you to my patrons for your continued support—you're really keeping the channel alive. If you'd like to support the channel and help me in the writing process for upcoming projects, you'll find my link to Patreon below.
This has been another Proof Under Another Roof. So long and/or farewell!