introductory mathematical logic and proofs
go home
prerequisites:
table of contents:
a lot of the math you've learned up to this point is about learning computation techniques, but how were these techniques
created? and more importantly, how do we know that they actually work?
this page will introduce you to a logical system that mathematicians use to justify (and invent) math!
intro to formal logic
first, we need to define the rules of the logical system we will be working under; we will refer to these unbreakable rules as the laws of traditional logic, and they are:- law of identity: objects are always identical to themselves.
- law of non-contradiction: contradictions cannot exist.
- law of excluded middle: propositions are truth-apt.
these laws may be a bit unclear at the moment, so let's clear these up a bit.
to clarify the law of identity: in math, an object can be defined as any concept that could be thought of, so long as it is:
- logically consistent: does not break the laws of traditional logic (either directly, or by causing some other object to do so).
- unambiguous: able to be objectively and clearly defined (we always know exactly what it is)
so, the law of identity means that any object (for example, the number \(12\)) is equal to itself (i.e., \(12=12\)).
this may seem obvious, but it's a foundational rule to clarify what is allowed to be called an "object"; we'll see a few examples of non-objects later.
we will define what a contradiction actually is later to clarify the law of non-contradiction, but now let's talk about the law of excluded middle.
a proposition is a truth-apt declarative sentence.
- truth-apt: capable of being true (\(T\)) or false (\(F\)), but not both, niether, or some secret third thing (by the law of excluded middle).
- declarative: defines a relationship or asserts a specific state.
so basically, propositions are sentences which proclaim something and are objectively true or false.
-
"\(6>7\)" is a proposition:
- proclaims that the value \(6\) is strictly greater than the value \(7\).
- its truth value (i.e. "trueness" or "falseness") can be objectively verified using known mathematical facts.
-
"\(>\)" is not a proposition:
- this doesn't proclaim anything.
- since it isn't declarative, it also doesn't make sense to assign a truth value to it.
as a shorthand, we can denote propositions with letters.
for example: $$ P=\text{Philadelphia is located in the USA}\\ Q=\text{Mexico City is located in China} $$ we can combine propositions using connectives to form more complex propositions:
- "and"/conjunction (denoted by the wedge symbol \(\wedge\)):$$P\wedge Q$$
- "or"/disjunction (denoted by the vee symbol \(\vee\)):$$P\vee Q$$
- "not"/negation (denoted by the symbol \(\neg\)):$$\neg P$$
- \(P\wedge Q\) is true if both \(P\) and \(Q\) are true.
- \(P\vee Q\) is true if either \(P\) or \(Q\) is true (or if both are true).
- \(\neg P\) is true if \(P\) is false.
we can summarize all possible output truth values for different input truth values using truth tables: $$ \begin{array}{|c|c|}\hline P & Q & P\wedge Q \\ \hline T & T & T \\ \hline T & F & F \\ \hline F & T & F \\ \hline F & F & F \\ \hline \end{array} \qquad \begin{array} {|c|c|}\hline P & Q & P\vee Q \\ \hline T & T & T \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & F \\ \hline \end{array} $$ we can check if two propositions are logically equivalent (denoted by the triple bar symbol \(\equiv\)) by using a truth table to check if their outputs are the same for all possible inputs.
for example: $$ \begin{array} {|c|c|}\hline P & Q & \neg(P\wedge Q) \\ \hline T & T & F \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array} \quad\text{matches}\quad \begin{array} {|c|c|}\hline P & Q & \neg P\vee\neg Q \\ \hline T & T & F \\ \hline T & F & T \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array} $$ so we know that \(\neg(P\wedge Q)\equiv\neg P\vee\neg Q\)!
some more formal language:
- premise: a proposition that is assumed to be true (for the sake of argument).
- argument: a series of logical steps based on the initial premises (used to form a conclusion).
-
conclusion: (supposedly) the result of an argument.
- i say "supposedly" because if you make a mistake during an arugment, the conclusion you draw would be invalid. if the argument is solid, the conclusion is valid.
to present the conclusion at the end of an argument, we can use the word "therefore" (denoted by the this symbol \(\therefore\), called the ergo symbol (meaning "therefore" in Latin!)).
consider this symbolic example: $$ \begin{array}{l} P\vee Q \\ \neg Q \\ \hline \therefore P \end{array} $$ here, \(P\) and \(Q\) are both propositions, and \(P\vee Q\) and \(\neg Q\) are premises.
we first assume that our premises are true: $$ \begin{array}{l} P\vee Q\text{ is true}\equiv(P\text{ is true})\vee(Q\text{ is true})\qquad\text{by the definition of disjunction}\\ \neg Q\text{ is true}\equiv Q\text{ is false}\qquad\text{by the definition of negation} \end{array} $$ the argument:
- as shown above, we use the definitions of disjunction and negation to "transform" our premises into something we can work with.
- since we know that \(Q\) is false by our second premise, then by our first premise, \(P\) must be true.
so that's our conclusion, and we write "\(\therefore P\)."
in case it isn't already clear, we don't have to write "is true" or "is false" after every proposition:
- \(P\equiv\) "\(P\) is true"
- \(\neg P\equiv\) "\(\neg P\) is true" \(\equiv\) "\(P\) is false"
the same way that numbers and operations have laws that tell you how you are allowed to manipulate expressions, so do propositions and connectives!
-
idempotent laws:
- \(P\wedge P=P\)
- \(P\vee P=P\)
-
double negation law:
- \(\neg(\neg P)=P\)
-
commutative laws:
- \(P\wedge Q\equiv Q\wedge P\)
- \(P\vee Q\equiv Q\vee P\)
-
associative laws:
- \(P\wedge (Q\wedge R)\equiv(P\wedge Q)\wedge R\)
- \(P\vee (Q\vee R)\equiv(P\vee Q)\vee R\)
-
distributive laws:
- \(P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)\)
- \(P\vee(Q\wedge R)\equiv(P\vee Q)\wedge(P\vee R)\)
-
DeMorgan's laws:
- \(\neg(P\wedge Q)\equiv\neg P\vee\neg Q\)
- \(\neg(P\vee Q)\equiv\neg P\wedge\neg Q\)
-
absorption laws:
- \(P\wedge(P\vee Q)\equiv P\)
- \(P\vee(P\wedge Q)\equiv P\)
a proposition which is always true is called a tautology (denoted by the top symbol \(\top\)): $$P\vee\neg P\equiv\top$$ and a proposition which is always false is called a contradiction (denoted by the bot symbol \(\bot\)): $$P\wedge\neg P\equiv\bot$$ since tautologies and contradictions are just propositions with an unchanging truth value, connecting them to other propositions \(P\) reduces it to a single proposition:
- \(P\vee\top\equiv\top\)
- \(P\wedge\top\equiv P\)
- \(P\vee\bot\equiv P\)
- \(P\wedge\bot\equiv\bot\)
- \(\neg\top\equiv\bot\)
- \(\neg\bot\equiv\top\)
now, to finally clarify the law of non-contradiction: contradictions should not be allowed to exist in any argument, so if we do stumble upon one, that usually means that one of our initial premises (which we assumed to be true) is actually false.
there's a couple more connectives we should discuss.
the conditional connective (denoted with a single-bar arrow \(\rightarrow\)) connects propositions via an "if ..., then ..." statement: $$P\rightarrow Q$$ there are a few different ways to say \(P\rightarrow Q\) in words:
- "if \(P\), then \(Q\)"
- "\(P\) implies \(Q\)"
- "\(P\) is sufficient for \(Q\)"
- "\(Q\) is necessary for \(P\)"
the arrow can also face the other way: \(Q\leftarrow P\equiv P\rightarrow Q\).
here is its truth table: $$ \begin{array} {|c|c|}\hline P & Q & P\rightarrow Q \\ \hline T & T & T\\ \hline T & F & F \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array} $$ the first two rows of this truth table should align with the intuitive idea of an "if ..., then ..." statement:
- "\(2>1\) (true) \(\rightarrow 2>0\) (true)" is a true statement
- "\(2>1\) (true) \(\rightarrow 2>3\) (false)" is a false statement
but what's going on with the last two rows?
- "\(2>3\) (false) \(\rightarrow 2>0\) (true)" is a true statement
- "\(2>3\) (false) \(\rightarrow 2>4\) (false)" is a true statement
it may seem strange, but yes, both these statements are true; in fact, they are called vacuously true!
think about it this way: false premises can imply anything, since nothing can go against them.
as an informal example, consider this proposition: $$\text{if Beethoven was alive today, then he would enjoy heavy metal music.}$$ since Beethoven is not alive today, you cannot definitively say that he wouldn't enjoy metal music, so this statement is a vacuous truth.
here is something to interesting to note, called the conditional law: $$ \begin{array} {|c|c|}\hline P & Q & \neg P\vee Q \\ \hline T & T & T\\ \hline T & F & F \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}\quad\text{matches}\quad \begin{array} {|c|c|}\hline P & Q & P\rightarrow Q \\ \hline T & T & T\\ \hline T & F & F \\ \hline F & T & T \\ \hline F & F & T \\ \hline \end{array}\\\\ \therefore P\rightarrow Q\equiv\neg P\vee Q\ $$ using this law, we can show another extremely important result called the contrapositive law: $$ \begin{array}{l} P\rightarrow Q \\ \equiv\neg P\vee Q\qquad\text{by conditional law}\\ \equiv\neg P\vee \neg(\neg Q)\qquad\text{by double negation law}\\ \equiv\neg(\neg Q)\vee \neg P\qquad\text{by commutative law}\\ \equiv \neg Q\rightarrow\neg P\qquad\text{by conditional law}\\ \end{array}\\\\ \therefore P\rightarrow Q\equiv\neg Q\rightarrow\neg P $$ \(Q\equiv\neg Q\rightarrow\neg P\) is called the contrapositive of \(P\rightarrow Q\).
keep in mind that \(P\rightarrow Q\not\equiv Q\rightarrow P\):
- \(Q\rightarrow P\) is called the converse of \(P\rightarrow Q\).
also, \(P\rightarrow Q\not\equiv \neg P\rightarrow \neg Q\):
- \(\neg P\rightarrow \neg Q\) is called the inverse of \(P\rightarrow Q\).
if you combine a conditional statement with its converse, you get a biconditional statement: $$P\leftrightarrow Q\equiv(P\rightarrow Q)\wedge(Q\rightarrow P)$$ in words:
- "\(P\) implies \(Q\) and \(Q\) implies \(P\)"
- "\(P\) is necessary and sufficient for \(Q\)"
-
"\(P\) if and only if \(Q\)"
- "if and only if" is often abbreviated to "iff"
here is its truth table: $$ \begin{array} {|c|c|}\hline P & Q & P\leftrightarrow Q \\ \hline T & T & T\\ \hline T & F & F \\ \hline F & T & F \\ \hline F & F & T \\ \hline \end{array} $$ notice how \(P\leftrightarrow Q\) is only true when \(P\) and \(Q\) have the same truth value!
lastly, $$ \begin{array}{l} P\leftrightarrow Q \\ \equiv(P\rightarrow Q)\wedge(Q\rightarrow P)\qquad\text{by definition of a biconditional statement}\\ \equiv(\neg P\vee Q)\wedge(\neg Q\vee P)\qquad\text{by conditional law}\\ \equiv((\neg P\vee Q)\wedge\neg Q)\vee((\neg P\vee Q)\wedge P)\qquad\text{by distributive law}\\ \equiv(\neg Q\wedge(\neg P\vee Q))\vee(P\wedge(\neg P\vee Q))\qquad\text{by commutative law}\\ \equiv((\neg Q\wedge\neg P)\vee(\neg Q\wedge Q))\vee((P\wedge\neg P)\vee(P\wedge Q))\qquad\text{by distributive law}\\ \equiv((\neg Q\wedge\neg P)\vee\bot)\vee(\bot\vee(P\wedge Q))\qquad\text{by definition of contradiction}\\ \equiv(\neg Q\wedge\neg P)\vee(P\wedge Q)\\ \equiv(P\wedge Q)\vee(\neg Q\wedge\neg P)\qquad\text{by commutative law}\\ \end{array}\\\\ \therefore P\leftrightarrow Q\equiv(P\wedge Q)\vee(\neg P\wedge\neg Q) $$ if you think this whole section has felt like a bunch of abstract philosophy, that's because it is!
a lot of important math is directly based on this logical system we have described, so it is important that we clearly define it; we'll see later how this system is used to prove conclusions in math.
sets
a foundational type of object which we will be exploring and utilizing a lot is called a set, defined as an unordered collection of distinct objects, where each object in the set is called an element (or member) of it.sets are denoted by putting braces around a list of its elements, like this set \(S\) of the objects \(1\), \(2\), and \(3\): $$S=\{1,2,3\}$$ since sets are unordered, \(\{1,2,3\}=\{3,1,2\}\), and since each element of a set must be distinct, no set can contain 2 of the same element.
to say that an object is in a set, we use the symbol \(\in\). $$1\in\{1,2,3\}$$ to say that an object is not in a set, just put a slash through the in symbol: \(\notin\). $$a\notin\{1,2,3\}$$ important side note: we'll be defining and using multiple other symbols to represent relationships between mathematical objects, so just know that putting slash through a symbol \(S\) generally means \(\neg S\).
if we don't want to list all the elements of the set to denote it, we can instead denote it with set builder notation: $$S=\{\textcolor{red}{x}:\textcolor{#0049ff}{M(x)}\}$$
- the red part denotes the members of the set
- the colon symbol \(:\) (generally) means "such that"
- the blue part, (said as "\(M\) of \(x\)"), is called the membership statement, which is a proposition about some arbitrary object \(x\), such as: \(M(x)=x\text{ is a real number greater than }0\).
altogether, \(\{\textcolor{red}{x}:\textcolor{#0049ff}{M(x)}\}\) is said as "the set of all \(\textcolor{red}{x}\) such that \(\textcolor{#0049ff}{M(x)}\)."
for example, \(\{\textcolor{red}{x^2+y^2}:\textcolor{#0049ff}{0\leq x^2+y^2\leq 1}\}\) is "the set of all \(\textcolor{red}{x^2+y^2}\) such that \(\textcolor{#0049ff}{0\leq x^2+y^2\leq 1}\)", which, if you think of \(x\) and \(y\) as coordinates of the plane, is the unit disk!
here is some very important notation for commonly used sets of numbers in mathematics:
- \(\mathbb{R}=\text{the set of all real numbers}\)
- \(\mathbb{Q}=\text{the set of all rational numbers}\)
- \(\mathbb{Z}=\text{the set of all integers}\)
-
\(\mathbb{N}=\text{the set of all natural numbers (i.e. integers greater than }0\text{)}\)
- by the way, in other math textbooks/lectures/resources, you might sometimes find that \(\mathbb{N}\) is defined as all the non-negative integers, which includes \(\textit{0}\). people can't seem to agree on a standard definition for \(\mathbb{N}\), but on this site, \(\mathbb{N}\) will always only denote the integers greater than \(0\).
we'll actually define these sets of numbers formally later!
\(\emptyset\) denotes a set known as the empty set or null set, which is the set containing no elements: $$\emptyset=\{\}$$ keep in mind that sets can contain any object, including other sets, so: $$ \emptyset\neq\{\emptyset\}\\ \{\}\neq\{\{\}\}\\ \text{the set containing no objects}\neq\text{the set containing }\emptyset $$ similar to numbers, we can do operations on sets (say \(A\) and \(B\)):
- intersection (denoted by the cap symbol \(\cap\)):$$A\cap B=\{x:x\in A\wedge x\in B\}$$
- union (denoted by the cup symbol \(\cup\)):$$A\cup B=\{x:x\in A\vee x\in B\}$$
- difference (denoted by the backslash symbol \(\backslash\)):$$A\backslash B=\{x:x\in A\wedge x\notin B\}$$
for example, with \(A=\{a,b,c,d\}\) and \(B=\{c,d,e,f\}\): $$ A\cap B=\{c,d\}\qquad A\cup B=\{a,b,c,d,e,f\}\qquad A\backslash B=\{a,b\} $$ we can also form other operations by combining these!
for example, the symmetric difference (denoted by the capital Greek letter Delta \(\Delta\)): $$A\Delta B=(A\cup B)\backslash(A\cap B)$$ it can be helpful to visualize these operations using Venn diagrams, where each set is represented by a circle.
$$\textcolor{red}{A}\cap\textcolor{#0049ff}{B}$$
$$\textcolor{red}{A}\cup\textcolor{#0049ff}{B}$$
$$\textcolor{red}{A}\backslash\textcolor{#0049ff}{B}$$
$$\textcolor{red}{A}\Delta\textcolor{#0049ff}{B}$$
suppose that all the elements of \(A\) are also elements of \(B\); then,
- \(A\) is called a subset (denoted by the symbol \(\subseteq\)) of \(B\)
- \(B\) is called a superset (denoted by the symbol \(\supseteq\)) of \(A\)
$$
\begin{array}{c}
A=\{a,b\} \\
B=\{a,b,c,d\} \\
\hline
\therefore A\subseteq B,B\supseteq A
\end{array}
$$
$$\textcolor{red}{A}\subseteq\textcolor{#0049ff}{B}\\ \textcolor{#0049ff}{B}\supseteq\textcolor{red}{A}$$
note that if two sets are exactly the same, then they are both subsets/supersets of each other, since they still satisfy the definitions above; a subset/superset is called strict if some BUT NOT ALL of the elements of the subset are included in the superset, denoted \(\subset\) and \(\supset\).
- generally, we will stick to using the non-strict subset and superset symbols, unless strictness is actually required.
\(A\) is disjoint from \(B\) if \(A\cap B=\emptyset\) (i.e. they do not share any elements).
$$\textcolor{red}{A}\cap\textcolor{#0049ff}{B}=\emptyset$$