Logic and Set Theory
2.1 Reasoning and Logic
Statements
Logic is the study of reasoning itself. How we know whether something is true, and how conclusions follow from other conclusions? To do any of that rigorously, we need to agree on what counts as something that can be true or false in the first place. In mathematics, we call those things statements.
Definition: Statement
A mathematical statement is a complete sentence that is either true or false. Statements in mathematics are usually represented with the letters $p$, $q$, and $r$ but any symbol will do.
Not every sentence is a statement. Questions can't be true or false. Sentences with an unspecified pronoun like "she" or an undefined variable like $x$ could go either way depending on context, they're not definitively true or false until that context is provided. Subjective opinions are also tricky territory.
Example: Identifying Statements
Which of the following are not statements? Explain why or why not.
- She has blue eyes.
- $2 + 3 = 5$
- How are you?
- $x + 7 = 18$
- Lincoln was the best president.
- $2y + 7 > 1$
- If he is over 210 cm tall, then he is over 2 m tall.
- $2(x + y) = 2x + 2y$
Show Solution
- Not a statement. We don't know who "she" is, so it can't be evaluated as true or false.
- Statement. It is true: $2 + 3 = 5$.
- Not a statement. It's a question, questions don't have truth values.
- Not a statement. Without knowing the value of $x$, we can't determine whether it is true or false.
- Not clearly a statement. "Best" is a subjective judgment; there's no objective way to verify it.
- Not a statement. Without knowing $y$, it could be true or false depending on the value.
- Statement. It is true: $210\text{ cm} > 200\text{ cm} = 2\text{ m}$, so being over 210 cm guarantees being over 2 m.
- Statement. It is always true by the distributive property, for any $x$ and $y$.
MyOpenMath: Identifying Statements
Negations and Quantifiers
Negation
Once you have a statement, the most natural thing to do with it is flip it. The negation of a statement is its logical opposite. If the original is true, the negation is false, and vice versa.
Definition: Negation
The negation of a statement $p$, denoted $\sim p$, means "not $p$." If $p$ is true, then $\sim p$ is false. If $p$ is false, then $\sim p$ is true.
A truth table lists all possible truth values a statement can take given a logical operation.
| $p$ | $\sim p$ |
|---|---|
| T | F |
| F | T |
Consider the statement, "It is raining." Its negation is simply "It is not raining." The negation doesn't need to be creative or dramatic. It only needs to be the direct logical opposite.
Example: Negating simple statements
Negate each of the following statements.
- $2 + 3 = 5$
- A hexagon has six sides.
Show Solution
- $2 + 3 \neq 5$
- A hexagon does not have six sides.
Quantifiers
Things get trickier when a statement uses words like "all," "some," or "none." These are quantifiers. Quantifies tell us how many elements of a set are being described.
Definition: Quantifier
In logic, a quantifier gives information about "how many" in the statements in which they occur. Common quantifiers include: all, some, every, there exists, and none.
- Universal quantifiers make claims about every element of a set: all, every, no.
- Existential quantifiers make claims about at least one element: some, there exists, at least one.
Fact: Negating Quantifiers
Negating statements with quantifiers requires care. The negation of all is not all, which in natural English is best said as some are not. The negation of some is not some or none.
| Statement | Negation |
|---|---|
| Some A's are B's. | No A's are B's. |
| Some A's are not B's. | All A's are B's. |
| All A's are B's. | Some A's are not B's. |
| No A is B. | At least one A is B. |
A classic mistake is to negate "Some A are B" as "Some A are not B." But those two statements don't actually contradict each other, both could be true at the same time! The real negation of "Some A are B" is "No A are B," which directly contradicts the original. In general it is best to simply negate the quantifier and translate that into better english afterwards. Some becomes not some, which sounds akward so we change it to none. The most important part of negation is to make the statment the logical opposite.
Example: Negating quantified statements
Negate each of the following.
- All students like hamburgers.
- Some people like mathematics.
- There exists a natural number such that $3n = 6$.
- For all natural numbers $n$, $3n = 3n$.
- Some prime numbers are not odd numbers.
Show Solution
- I would start by saying "Not all students like hamburgers", which then sounds nicer as "some students do not like hamburgers". Both are logically equivalent and acceptable.
- Some becomes not some, which probably sounds best as "No people like mathematics".
- There does not exist a natural number such that $3n = 6$. (Equivalently: for all natural numbers $n$, $3n \neq 6$.)
- There exists a natural number $n$ such that $3n \neq 3n$.
- "Not some of them are not odd" is all kinds of bad english (but OK logically). Better to say "All prime numbers are odd numbers".
MyOpenMath: Negations and Quantifiers
Compound Statements: And / Or
A Puzzle to Start
Before we define anything formally, consider this puzzle. It showcases exactly why "and" and "or" behave the way they do in logic.
Example: The Prisoner's Dilemma
A prisoner is given a choice to leave through one of two doors. Each door has a sign, and the prisoner knows that exactly one of the signs is true.
- Door 1: In this room there is the way to freedom, and in the other room there is a tiger.
- Door 2: In one of these rooms there is the way to freedom, and in the other is a tiger.
Which door should the prisoner take?
Show Solution
Assume Door 1 is true: then both "there is a lady here" and "there is a tiger next door" must hold. But that means Door 2, which says the same thing slightly differently, would also be true. We were told exactly one sign is true, so this is a contradiction.
Therefore Door 1 must be false. Since exactly one sign is true, Door 2 is true. Working through what Door 1 being false means: it's not the case that both freedom is here and a tiger is next door. Combined with Door 2 being true, we conclude that freedom is behind Door 2. The prisoner should take Door 2.
Conjunction and Disjunction
The puzzle above turns on how "and" works in logic. These are the two most fundamental ways to build compound statements.
Definition: Compound Statement: Conjunction and Disjunction
A compound statement is formed by joining two or more statements with a logical operator.
The conjunction ("and"), written $p \land q$, is true only when both $p$ and $q$ are true.
| $p$ | $q$ | $p \land q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The disjunction ("or"), written $p \lor q$, is true when at least one of $p$ or $q$ is true.
| $p$ | $q$ | $p \lor q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Note that "or" in logic is inclusive, it includes the case where both parts are true. This differs from everyday usage, where "soup or salad?" implies you pick exactly one.
Example: Evaluating compound statements
Let $p$ be "$2+3=5$," $q$ be "$2 \cdot 3 = 6$," and $r$ be "$5+3=9$." Classify each of the following as true or false.
- $p \land q$
- $\sim p \lor r$
- $\sim(p \land q)$
- $q \lor r$
- $\sim p \land \sim q$
- $(p \land q) \lor \sim r$
Show Solution
First establish the truth values: $p$ is true, $q$ is true, and $r$ is false (since $5+3=8$, not 9).
- $p \land q$: T $\land$ T = True
- $\sim p \lor r$: F $\lor$ F = False
- $\sim(p \land q)$: $\sim$(T) = False
- $q \lor r$: T $\lor$ F = True
- $\sim p \land \sim q$: F $\land$ F = False
- $(p \land q) \lor \sim r$: T $\lor$ T = True
MyOpenMath: Negations and Quantifiers
Tautologies and Contradictions
Some compound statements are always true or always false, no matter what truth values the individual parts take.
Example: A tautology
Make a truth table for $p \lor \sim p$.
Show Solution
| $p$ | $\sim p$ | $p \lor \sim p$ |
|---|---|---|
| T | F | T |
| F | T | T |
No matter what $p$ is, $p \lor \sim p$ is always true.
Fact: Tautologies and Contradictions
A statement that is always true is called a tautology. A statement that is always false is called a contradiction. For example: $p \lor \sim p$ is a tautology, while $p \land \sim p$ is a contradiction.
Logical Equivalence and De Morgan's Laws
Two statements are logically equivalent if their truth tables are identical, they have the same truth value in every possible case.
Definition: Logically Equivalent
Two statements are logically equivalent if their truth values match for all possible input values. We write $p \equiv q$.
Example: De Morgan's First Law for Logic
Show that $\sim(p \land q) \equiv \sim p \lor \sim q$.
Show Solution
Build a truth table with a column for each piece:
| $p$ | $q$ | $p \land q$ | $\sim(p \land q)$ | $\sim p$ | $\sim q$ | $\sim p \lor \sim q$ |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
The bolded columns are identical in every row, so $\sim(p \land q) \equiv \sim p \lor \sim q$. This is De Morgan's First Law.
MyOpenMath: Compound Statements and Truth Tables
Conditional and Biconditional Statements
The Conditional
The conditional is arguably the most important logical form in all of mathematics. Every theorem is, at its core, an "if-then" statement.
Definition: Conditional Statement
A conditional statement has the form "If $p$, then $q$," written $p \rightarrow q$ and read "$p$ implies $q$." The statement $p$ is called the hypothesis and $q$ is called the conclusion.
| $p$ | $q$ | $p \rightarrow q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
The truth table may feel strange at first. For example, why is the conditional true when the hypothesis is false? Think of it as a promise.
Fact: Understanding the Conditional Truth Table
Think of $p \rightarrow q$ as the promise: "If you mow my grass, I will pay you."
| Case | $p$ | $q$ | $p \rightarrow q$ | Result |
|---|---|---|---|---|
| You mow; I pay. | T | T | T | Promise kept |
| You mow; I do not pay. | T | F | F | Promise broken |
| You don't mow; I pay anyway. | F | T | T | Promise kept |
| You don't mow; I don't pay. | F | F | T | Promise kept |
The conditional is only false when a true hypothesis leads to a false conclusion. If the hypothesis is never triggered, the promise cannot be broken.
True or False: If pigs can fly then man has walked on mars.
Answer: who cares? Pigs can't fly. No need to check the conclusion. The statement is true.
Forms of the Conditional
Every conditional $p \rightarrow q$ has three related statements worth knowing.
Definition: Forms of the Conditional
Given the conditional $p \rightarrow q$:
- Converse: $q \rightarrow p$
- Inverse: $\sim p \rightarrow \sim q$
- Contrapositive: $\sim q \rightarrow \sim p$
In everyday terms, the converse changes the order of the conditional. The inverse negates both statements. The contrapositive does both.
Example: Converse, inverse, and contrapositive
Write the converse, inverse, and contrapositive of: "If I am in San Francisco, then I am in California."
Show Solution
Let $p$ = "I am in San Francisco" and $q$ = "I am in California."
- Converse ($q \rightarrow p$): If I am in California, then I am in San Francisco. (False, I could be in Los Angeles.)
- Inverse ($\sim p \rightarrow \sim q$): If I am not in San Francisco, then I am not in California. (False, same reason.)
- Contrapositive ($\sim q \rightarrow \sim p$): If I am not in California, then I am not in San Francisco. (True.)
The original conditional and its contrapositive are always logically equivalent. The converse and inverse are equivalent to each other, but not to the original.
Example: The conditional and contrapositive are equivalent
Use a truth table to show $p \rightarrow q \equiv \sim q \rightarrow \sim p$.
Show Solution
| $p$ | $q$ | $\sim p$ | $\sim q$ | $p \rightarrow q$ | $\sim q \rightarrow \sim p$ |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
The two rightmost columns are identical, confirming the equivalence.
This is an important fact that is used in mathematics quite often. The conditional and its contrapositive are logically equivalent. Sometimes its easier to understand the statement in one form or the other and changing between them can help. Heres another simple one:
"If today is Thursday, then we're having fried chicken" is exactly the same as saying "If we're not having fried chicken, then today is not Thursday."
The Biconditional
Definition: Biconditional Statement
A biconditional statement has the form "$p$ if and only if $q$," written $p \leftrightarrow q$. It is true exactly when $p$ and $q$ have the same truth value.
| $p$ | $q$ | $p \leftrightarrow q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
The biconditional is equivalent to $(p \rightarrow q) \land (q \rightarrow p)$, both directions of the implication holding simultaneously.
Example: Biconditional via truth table
Build a truth table for $(p \rightarrow q) \land (q \rightarrow p)$ and compare it to $p \leftrightarrow q$.
Show Solution
| $p$ | $q$ | $p \rightarrow q$ | $q \rightarrow p$ | $(p \rightarrow q) \land (q \rightarrow p)$ | $p \leftrightarrow q$ |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | T | F | F | F |
| F | F | T | T | T | T |
The columns are identical, confirming $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$.
MyOpenMath: Conditional and Biconditional Statements
Valid Reasoning
Arguments and Syllogisms
We've been building a vocabulary for logic. Now let's use it to evaluate arguments. An argument is what happens when I get accused of leaving the door open and letting the dogs out but I didn't. Just kidding, arguments are structured collections of statements designed to establish a conclusion.
An argument is a series of statements (called premises) used to establish a final claim (the conclusion). An argument is valid if the conclusion necessarily follows from the premises regardless of whether the premises themselves are actually true in the real world.
Definition: Syllogism
A syllogism is a form of reasoning in which a conclusion is drawn from two premises, usually involving quantifiers.
Take any introductory philosophy course and they'll hit you with this famous syllogism:
| Statement | Logical Form |
|---|---|
| Socrates is a man. | A is B. |
| All men are mortal. | B is C. |
| Therefore, Socrates is mortal. | A is C. |
The conclusion feels obvious because we accept the premises. But the key point is that it is also logically forced. If the premises are true, the conclusion cannot be false.
Euler Diagrams
Leonard Euler developed a visual method for checking argument validity called Euler diagrams. The idea is to represent sets as circles, mark specific elements as points, and then check whether the conclusion is forced by the picture.
The four basic set relationships used in Euler diagrams are:
- No A are B: the A and B circles are completely separate.
- Some A are B: the circles overlap; mark an X in the overlapping region.
- All A are B: circle A is entirely inside circle B.
- Some A are not B: the circles overlap; mark an X inside A but outside B.
To test validity: draw the diagram that must be true given the premises. If the conclusion holds in every possible valid drawing, the argument is valid. If you can draw a picture where the premises hold but the conclusion fails, the argument is invalid.
Example: Socrates is mortal
Determine whether the following argument is valid using an Euler diagram.
- All men are mortal.
- Socrates is a man.
- Therefore, Socrates is mortal.
Show Solution
"All men are mortal" forces the men circle to sit entirely inside the mortals circle. "Socrates is a man" places the dot for Socrates somewhere inside men. Since men is completely inside mortals, Socrates's dot must also be inside mortals, there is no other choice. The conclusion is forced. The argument is valid.
Example: Dave the bear
Determine whether the following argument is valid using an Euler diagram.
- Some bears are brown.
- Dave is a bear.
- Therefore, Dave is brown.
Show Solution
"Some bears are brown" means the bears and brown things circles overlap, but neither is fully inside the other. "Dave is a bear" places the dot for Dave somewhere inside bears, but we have freedom to choose exactly where. We can place Dave inside bears but outside brown things and still satisfy both premises. Since the conclusion doesn't hold in every valid diagram, the argument is invalid.
Example: Charlie can fly
Determine whether the following argument is valid using an Euler diagram.
- No fish can fly.
- Charlie can fly.
- Therefore, Charlie is not a fish.
Show Solution
"No fish can fly" forces the fish circle and the things that fly circle to be completely separate, they don't overlap at all. "Charlie can fly" places Charlie inside things that fly, which sits entirely outside fish. Charlie cannot possibly be inside the fish circle. The conclusion is forced, the argument is valid.