Definitions & theorems

Changing the order of the numbers does not change the result.
- $a + b = b + a$‬‭‬‭‬‭‬ and ‭$a \cdot b = b \cdot a$‬‭‬‭‬‭‬
- ‭$4 + 2 = 2 + 4$‬‭‬‭‬‭‬ or ‭$3 \cdot 5 = 5 \cdot 3$‬‭‬‭‬‭‬

Changing how numbers are grouped with parentheses does not change the result. It is all about who the numbers associate with first.
- ‭$(a + b) + c = a + (b + c)$‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬ and ‭$(a \cdot b) \cdot c = a \cdot (b \cdot c)$‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬
- ‭$(1 + 2) + 4 = 1 + (2 + 4)$‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬

• Multiplying a single number by a sum inside parentheses is equivalent to multiplying that number by each item inside individually.
• $a \cdot (b + c) = a \cdot b + a \cdot c$‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬
• ‭$3 \cdot (10 + 2) = (3 \cdot 10) + (3 \cdot 2) = 36$‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬‭‬

Let $f$ be a function defined for all $x$ near $a$, except possibly at $a$ itself. We say
$$\lim_{x\to a} f(x)=L$$
if for every number $\varepsilon>0$, there is a number $\delta>0$ such that whenever
$$0<|x-a|<\delta,$$
we have
$$|f(x)-L|<\varepsilon.$$

A proposition (sometimes called a statement) is a sentence that is strictly either true or false. There can be no ambiguity: the truth value must be ascertained without any additional explicit context. A sentence such as "Black is a color." and "$2 + 5 = 7$" are examples of a proposition. A statement such as "$x + 2 = 5$" is not a proposition, because its truth value depends on the explicit value of $x$ and is therefore ambiguous.

An axiom is a primitive statement that mathematicians universally agree to accept as true without proof. By establishing these starting rules at the beginning, axioms provide foundations ensuring that mathematical reasoning works out.

The Rules of Deduction are a system of rules by which we can label certain new statements as “true” or "false".

A proof is a chain of statements leading from the axioms of a system to a new statement that utilize our rules of deduction which allow us to declare the new statement as true. We make these assignments in ways that are truth functional. The truth value of a new proposition depends only on the truth values of its components.

A proposition is a theorem of less importance.

A lemma is a intermittent theorem primarily for use in proving a more important result.

A corollary is a theorem that follows quickly from a previous theorem.

Propositional variables are symbols that represent propositions. They are typically denoted with symbols like $P, Q, R$. We can chain together multiple propositional variables using logical connectives to form more complex propositions.

• Negation ($\neg$): Represents "not p", $\neg p$ means "not $p$."
  • If $p$ represents "It is raining", then $\neg p$ represents "It is not the case that it is raining".
  • Conventions may vary across different disciplines: symbols like $\sim p$, $\~{p}$ or $!p$ are also used to denote the negation of $p$.
  • If $p$ is true, then $\neg p$ is false; if $p$ is false, then $\neg p$ is true.

$$\begin{array}{c|c} p & \sim p \\ \hline T & F\\ F & T \end{array}$$

• Conjunction ($\land$): Represents "$p$ and $q$". $p \land q$ means "$p$ and $q$."
  • If $p$ represents "It is raining" and $q$ represents "It is soggy", then $p \land q$ represents "It is raining and it is soggy."
  • $p$ but $q$ means the same thing as $p \land q$.
  • $p \land q$ is true only if both $p$ and $q$ are true; otherwise, it is false.

$$\begin{array}{cc|c} p & q & p \land q \\ \hline T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \end{array}$$

• Disjunction ($\lor$): Represents "$p$ or $q$". $p \lor q$ means "$p$ or $q$."
  • If $p$ represents "It is raining" and $q$ represents "It is sunny", then $p \lor q$ represents "It is raining or it is sunny."
  • Neither $p$ nor $q$ means the same thing as $\neg p \land \neg q$.
  • We generally interpret "or" in the inclusive sense, meaning that if at least one of $p$ or $q$ is true, then $p \lor q$ is true. Both can be true as well.

$$\begin{array}{cc|c} p & q & p \lor q \\ \hline T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \end{array}$$

A tautology is a propositional statement that is always true, regardless of the truth values of its components. An example of a tautology is the statement $p \lor \neg p$, which states that either $p$ is true or $p$ is not true. This statement is always true because one of the two possibilities must hold.

A contradiction is a propositional statement that is always false, regardless of the truth values of its components. An example of a contradiction is the statement $p \land \neg p$, which states that $p$ is both true and not true at the same time. This statement is always false because it is impossible for both conditions to hold simultaneously.

$$p \land q \equiv q \land p$$

$$p \lor q \equiv q \lor p$$

$$(p \land q) \land r \equiv p \land (q \land r)$$

$$(p \lor q) \lor r \equiv p \lor (q \lor r)$$

$$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$$

$$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$$

$$p \land t \equiv p$$

$$p \lor c \equiv p$$

$$p \land \neg p \equiv c$$

$$p \lor \neg p \equiv t$$

$$\neg t \equiv c$$

$$\neg c \equiv t$$

$$\neg (\neg p) \equiv p$$

$$p \land p \equiv p$$

$$p \lor p \equiv p$$

$$p \land c \equiv c$$
$$p \lor t \equiv t$$

$$p \land (p \lor q) \equiv p$$

$$p \lor (p \land q) \equiv p$$

• Implication ($\to$): Represents "If $p$, then $q$". $p \to q$ means "If $p$, then $q$."
  • We call statements of this form conditional statements or implications, as the value of $q$ is conditional on the value of $p$.
  • If $p$ represents "It is raining" and $q$ represents "The ground is wet", then $p \to q$ represents "If it is raining, then the ground is wet."
  • We say "$p$ implies $q$".
  • $p$ only if $q$ means the same thing as $p \to q$. We say that $q$ is a necessary condition for $p$, and $p$ is sufficient for $q$.
  • $p \to q$ is false only if $p$ is true and $q$ is false; otherwise, it is true. This may seem counterintuitive at first, but remember that if $p$ is false, then the implication $p \to q$ is considered true regardless of the truth value of $q$. Such statements are considered to be vacuously true. Thus, $p \to q$ is only false when a true premise leads to a false conclusion

$$\begin{array}{cc|c} P & Q & P \implies Q \\ \hline \text{T} & \text{T} & \text{T} \\ \text{T} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{T} \\ \text{F} & \text{F} & \text{T} \end{array}$$

If we have a statement from $p \implies q$, the contrapositive is the statement $\neg q \implies \neg p$. The contrapositive is logically equivalent to the original conditional statement. This means that if $p \implies q$ is true, then $\neg q \implies \neg p$ is also true, and vice versa. Sometimes, the contrapositive might be easier to prove or work with than the original implication. This usage is a fundamental concept in logic and is often used in mathematical proofs and reasoning.

The converse of an implication $p \implies q$ is the statement form $q \to p$. The converse is not logically equivalent to the original conditional statement.

The inverse is the statement $\neg p \to \neg q$. The inverse is also not logically equivalent to the original conditional statement

An argument is a sequence of propositions, where the last proposition is the conclusion. An argument form is a sequence of logical forms, called premises, where the last form is the conclusion. An argument can be valid or invalid. Please note, that the validity of an argument does not depend on the propositions involved, but rather on the structure of the argument itself.

We can use truth tables and rules of inference to deduce the validity of an argument.

A common rule of inference is Generalization. It states that if we have a statement $p$ that is true, then we can conclude that $p \lor q$ is also true, for any proposition $q$. The form of Generalization is as follows: $p$ therefore $p \lor q$. We can also inference $q$ therefore $p \lor q$. The inclusive or allows us to infer the disjunction from either of its components as the statement will be true as long as at least one of the components is true.

Another common rule of inference is Specialization. It states that if we have a statement $p \land q$ that is true, then we can conclude that $p$ and $q$ is also true. The form of Specialization is as follows: $p \land q$ therefore $p$, and $p \land q$ therefore $q$. This rule allows us to infer the truth values of the individual components of a conjunction from the conjunction itself. As we know that for a conjunction to be true, both components must be true.

If have a disjunction $p \lor q$ and we know that one of the components is false, we can conclude that the other component must be true. This rule is known as Elimination. The form of Elimination is as follows: $p \lor q$, not $p$ therefore $q$, and $p \lor q$, not $q$ therefore $p$. This rule allows us to infer the truth of one component of a disjunction when we know that the other component is false, as for the disjunction to be true, at least one of the components must be true.

If $p \to q$ and $q \to r$, we can conclude that $p \to r$. This rule is known as Transposition. The form of Transposition is as follows: If $p$ then $q$, if $q$ then $r$ therefore if $p$ then $r$. This rule allows us to chain conditionals together to derive new conditionals.

Suppose we know that $p \lor q$ is true and we also know that if $p$ is true then $r$ is true. Suppose we also know that if $q$ is true then $r$ is true. We can conclude that $r$ is true. This rule is known as Division by Cases. The form of Division by Cases is as follows: $p \lor q$, if $p$ then $r$, if $q$ then $r$ therefore $r$. This rule allows us to infer the truth of a statement based on the truth of a disjunction and the implications of its components. As we know that either $p$ or $q$ is true and both lead to $r$ being true, we can conclude that $r$ must be true.

One of the most common rules of inference is Modus Ponens. It states that if we have a conditional statement $p \to q$ and we know that $p$ is true, then we can conclude that $q$ is also true. The form of Modus Ponens is as follows: If $p$ then $q$, $p$ therefore $q$.

$$\begin{array}{|c|c|c|c|} \hline p & q & p \to q & \text{Conclusion } (q) \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{F} \\ \hline \end{array}$$

In this truth table, we can see that in the first row, where both $p$ and $q$ are true, the conclusion is also true. In the second row, where $p$ is true and $q$ is false, the conclusion is false. In the third and fourth rows, where $p$ is false, the conclusion is not applicable. Therefore, Modus Ponens is a valid rule of inference.

Another important rule of inference is Modus Tollens. It states that if we have a conditional statement $p \to q$ and we know that $q$ is false, then we can conclude that $p$ is also false. The form of Modus Tollens is as follows: If $p$ then $q$, not $q$ therefore not $p$. This follows from the contrapositive of the conditional statement.

$$\begin{array}{|c|c|c|c|} \hline p & q & p \to q & \text{Conclusion } (\neg p) \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{F} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F} \\ \mathrm{F} & \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} \\ \hline \end{array}$$

A sample space $\Omega$ is the set of outcomes in a mathematical model. An event is an allowed subset of $\Omega$: the event occurs when the realized outcome belongs to that subset. For a finite sample space, we allow every subset as an event. For real-valued outcomes, we will use intervals and other measurable sets; Lesson 2 explains why an event collection is part of the model.

In a finite weighted model, assign numbers $w(\omega)\geq0$ whose sum is $1$. Define

$$P(A)=\sum_{\omega\in A}w(\omega).$$

An event collection $\mathcal F$ is the collection of subsets of $\Omega$ that contains $\Omega$ itself and is closed under complements and countable unions. Such a collection is known as a $\sigma$-algebra. A countable union combines a sequence $A_1,A_2,\ldots$ of events, each $A_i\in\mathcal F$. Intersections also belong to the collection because

$$\bigcap_i A_i=\left(\bigcup_i A_i^c\right)^c.$$

A probability measure is a finite real-valued assignment $P$ on $\mathcal F$ satisfying:

1. $P(A)\geq0$ for every event $A\in\mathcal F$.
2. $P(\Omega)=1$.
3. If $A_1,A_2,\ldots\in\mathcal F$ are pairwise disjoint, then
   $$P\left(\bigcup_{i=1}^{\infty}A_i\right)=\sum_{i=1}^{\infty}P(A_i).$$

For integers $0\leq k\leq n$, an ordered selection of $k$ distinct objects from a set of $n$ is a list of length $k$, drawn from that set, with no repetition. A permutation of all $n$ objects is an ordered selection with $k=n$.

For integers $0\leq k\leq n$, a combination of size $k$ from a set of $n$ objects is a $k$-element subset of it. The number of such subsets is written $$\binom nk,$$ read "$n$ choose $k$", and is known as the binomial coeffecient.