• Mathematics without infinitely small, continuous mathematical objects. The mathematics of finite sets.

## Propositional calculus⌗

• Comes from the linguistic concept that things can be either true or false.

• We should avoid variables when forming statements, as they may change the logical value.

• $$2=7$$ statement
• $$x=5$$ not a statement
• In logic we do not use the equals sign, we use the equivalence sign $$\equiv$$.

• Logical values (booleans) are denoted by either 0 or 1 (or t, f, etc.).

• When doing logic, we use propositional variables (e.g. p, q, r).

• Can be either true or false.
• The operations done on propositional variables are called propositional connectives.

• Conjunction: $$p \land q$$ is only true if both p and q are true $$(0001)$$
• Disjunction: $$p \lor q$$ is only false if both p and q are false $$(0111)$$
• Implication (material conditional): $$p \implies q$$ is false only if p is true and q is false (truth table $$(1011)$$)
• $$\equiv \neg p \lor q$$
• Not necessarily connectives but unary operations:

• Negation: Denoted by ~, $$\neg$$ or NOT, negates the one input $$(10)$$.
• A (propositional) formula is a “properly constructed” logical expression.

• e.g. $$\neg[(p \lor q)] \land r$$
• $$(p \land)$$ is not a formula, as $$\land$$ requires 2 variables.
• Logical equivalence: $$\phi(p, q, k) \equiv \psi(p, q, k)$$, logical value of $$\phi$$ is equal to logical value of $$\psi$$.
• Commutativity: $$p \land q \equiv q \land p$$
• Associativity: $$(p \land q) \land r \equiv p \land (q \land r)$$
• Distributivity: $$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$$
• Conjunctive normal form: every formula can be written as a conjunction of one or more disjunctions.
• $$\neg(B \lor C)$$ can be written as $$\neg B \land \neg C$$
• Double negation law: $$\neg(\neg p) \equiv p$$

• De Morgan’s laws: $$\neg(p \land q) \equiv \neg p \lor \neg q$$ and $$\neg(p \lor q) \equiv \neg p \land \neg q$$.

• If and only if (iff): $$p \iff p \equiv (p \implies q) \land (q \implies p)$$

• Contraposition law:

• $$(p \implies q) \equiv (\neg q \implies \neg p)$$ prove by contraposition
• $$(p \implies q) \equiv (\neg p \lor q)$$
• $$(\neg q \implies \neg p) \equiv (\neg (\neg q) \lor (\neg p) \equiv (q \lor \neg p) \equiv (\neg p \lor q)$$

• $$p \lor \neg p \equiv 1$$ and $$p \land \neg p \equiv 0$$
• Tautology: $$\phi (p, q, ... r)$$ is a tautology iff $$\phi \equiv 1$$

## Sets⌗

• We will consider subsets of universal set $$\mathbb X$$
• $$2^\mathbb X = \{ A : A \subseteq \mathbb X\}$$
• $$2^\mathbb X = P(\mathbb X)$$
• All 2 object subsets of $$\mathbb X$$: $$P_2(\mathbb X)$$
• $$A \subset B \equiv$$ every element of A is an element of B $$\equiv \{x \in \mathbb X : x \in A \implies x \in B\}$$
• Operations on sets:
• Union - $$\cup$$ - $$A \cup B = \{ x \in \mathbb X : x \in A \lor x \in B \}$$
• Intersection - $$\cap$$ - $$A \cap B = \{ x \in \mathbb X : x \in A \land x \in B \}$$
• Complement - $$A'$$ - $$A' = \{ x \in \mathbb X : \neg (x \in A) \}$$
• If $$x = \{ 1 \}$$ then $$x' = \emptyset$$
• Equality of sets: $$A = B$$ iff $$x \in \mathbb X : (x \in A \iff x \in B)$$
• Difference of sets:
• $$A \setminus B = \{ x \in \mathbb X : x \in A \land x \notin B \} = A \cap B'$$
• Symmetric difference: $$A \div B = (A \setminus B) \cup (B \setminus A)$$
• Laws of set algebra:
• $$A \cup B = B \cup A , A \cap B = B \cap A$$
• $$(A \cup B) \cup C = A \cup (B \cup C), (A \cap B) \cap C = A \cap (B \cap C)$$
• $$(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$$ vice versa
• $$A \cap \emptyset, A \cap \mathbb X = A, A \cup \emptyset = A, A \cup \mathbb X = \mathbb X$$
• $$(A \cup B)' = A' \cap B'$$ vice versa
• $$A \cup A' = \mathbb X, A \cap A' = \emptyset$$
• Note: $$\{ \emptyset \} \neq \emptyset$$, one is a set with one element, one is the empty set, no elements ($$\{ \}$$)
• Quip: $$\{ x \in \mathbb R : x^2 = -1\} = \emptyset$$

## Quantifiers⌗

• $$\phi$$ - prepositional function: yields only true or false value
• $$\forall$$ means “for all” and $$\exists$$ means “there exists”
• $$\forall$$:
• Shorthand for $$\land$$ e.g. $$(\forall x \in \{ 1, 2, ... 10 \}) x > 0 \equiv 1 > 0 \land 2 > 0 \land ... 10 > 0$$
• $$\exists$$:
• Shorthand for $$\lor$$ e.g. $$(\exists x \in \{ 1, 2, ... 10 \}) x > 5 \equiv 1 > 5 \lor 2 > 5 \lor ... 10 > 5$$
• $$\neg \forall \equiv \exists$$, vice versa
• With quantifiers we can write logical statements e.g.
• $$(\forall x \in \mathbb{R}) (\forall y \in \mathbb{R}) x > y$$ is a statement and is false
• $$(\forall x) (\exists y) x > y$$ is true
• shortcut: $$(\exists x, y) \equiv (\exists x) (\exists y)$$
• Quantifiers can be expressed in set language, sort of a definition in terms of sets:
• $$(\forall x \in \mathbb{X}) (\phi(x)) \equiv \{ p \in \mathbb{X} : \phi(p) \} = \mathbb{X}$$
• $$(\exists x \in \mathbb{X}) (\phi(x)) \equiv \{ q \in \mathbb{X} : \phi(q) \} \neq \emptyset$$
• $$(\exists x \in \mathbb{X}) (\neg \phi(x)) \equiv \neg ( \{ p \in \mathbb{X} : \phi(p) \} = \mathbb{X} )$$
• Order of quantifiers matters.

## Relations⌗

• Cartesian product:
• $$A \times B = \{ (p, q) : p \in A \land q \in B \}$$
• Def: A relation $$R$$ on a set $$\mathbb X$$ is a subset of $$\mathbb X \times \mathbb X$$ ($$R \subseteq \mathbb X \times \mathbb X$$)
• Graph of a function $$f()$$: $$\{ (x, f(x) : x \in Dom(f) \}$$
• Properties of:
• Reflexivity: $$(\forall x \in \mathbb X ) (x, x) \in R \equiv (\forall x \in \mathbb X) x R x$$
• Symmetricity: $$[ (\forall x, y \in \mathbb X) (x, y) \in R \implies (y, x) \in R) ] \equiv [ (\forall x, y \in \mathbb X) ( x R y \implies y R x) ]$$
• Transitivity: $$(\forall x, y, z \in \mathbb X) (x R y \land y R z \implies x R z)$$
• Antisymmetricity: $$(\forall x, y \in \mathbb X) (x R y \land y R x \implies x = y)$$
• Equivalence relations:
• Def: $$R \subseteq \mathbb X \times \mathbb X$$ is said to be an equivalence relation iff $$R$$ is reflexive, symmetric and transitive.
• Congruence modulo n: $$p R q \equiv n | p - q$$
• Def R - and equivalence relation of $$\mathbb X$$: The equivalence class of an element $$x \in \mathbb X$$ is the set $$[x]_R = \{ y \in \mathbb X : x R y \}$$
• Every $$x \in \mathbb X$$ belongs to the equivalence class of some element $$a$$.
• $$(\forall x, y \in \mathbb X) ([x] \cap [y] \neq \emptyset \iff [x] = [y])$$
• Partitions
• A partition is a set containing subsets of some set $$\mathbb X$$ such that their collective symmetric difference equals $$\mathbb X$$. A partition of is a set $$\{ A_i: i \in \mathbb I \land A_i \subseteq \mathbb X \}$$ such that:
• $$(\forall x \in \mathbb X) (\exists j \in \mathbb I) (x \in A_j)$$
• $$(\forall i, j \in \mathbb I) (i \neq j \implies A_i \cap A_j = \emptyset)$$
• $$\{ A_i \}_{i \in \mathbb I}$$ is a partition iff there exists an equivalence relation $$R$$ on $$\mathbb X$$ such that:
• $$(\forall i \in \mathbb I) (\exists x \in \mathbb X) A_i = [x]_R$$
• $$(\forall x \in \mathbb X) (\exists j \in \mathbb I) [x] = A_j$$
• The quotient set: $$\mathbb X / R = \{ [a] : a \in \mathbb X \}$$

## Posets⌗

• Partial orders
• $$\mathbb X$$ is a set, $$R \subseteq \mathbb X \times \mathbb X$$
• Def: $$R$$ is a partial order on $$\mathbb X$$ iff $$R$$ is:
• Reflexive
• Antisymmetric
• Transitive
• Def: $$m \in \mathbb X$$ is said to be:
• maximal element in $$(\mathbb X, \preccurlyeq)$$ iff $$(\forall a \in \mathbb X) m \preccurlyeq a \implies m = a$$
• largest iff $$(\forall a \in \mathbb X) (a \preccurlyeq m)$$
• minimal iff $$(\forall a \in \mathbb X) (a \preccurlyeq m \implies a = m)$$
• smallest iff $$(\forall a \in \mathbb X) (m \preccurlyeq a)$$
• Def: A partial order $$R$$ on $$\mathbb X$$ is said to be “total” iff $$(\forall x, y \in \mathbb X) (x R y \lor y R x)$$
• Def: A subset $$B$$ of $$\mathbb X$$ is called a chain “chain” iff $$B$$ is totally ordered by $$R$$
• $$C(\mathbb X)$$ - the set of all chains in $$(\mathbb X, R)$$
• A chain $$D$$ in $$(\mathbb X, R)$$ is called a maximal chain iff $$D$$ is a maximal element in $$(C(\mathbb X), R)$$
• $$K \subseteq \mathbb X$$ is called an antichain in $$(\mathbb X, R)$$ iff $$(\forall p, q \in K) (p R q \lor q R p \implies p = q)$$
• Def: $$R$$ is a partial order on $$\mathbb X$$, $$R$$ is called a well order iff $$R$$ is a total order on $$X$$ and every nonempty subset $$A$$ of $$\mathbb X$$ has the smallest element

## Induction⌗

• If $$\phi$$ is a propositional function defined on $$\mathbb N$$, if:
• $$\phi(1)$$
• $$(\forall n \geq 1) \phi(n) \implies \phi(n+1)$$
• $$(\forall k \geq 1) \phi(k)$$

## Functions⌗

• $$f: \mathbb X \to \mathbb Y$$
• Def: $$f \subseteq \mathbb X \times \mathbb Y$$ is said to be a function if:
• $$(\forall x \in \mathbb X)(\exists y \in \mathbb Y) (x, y) \in f(y = f(x))$$
• $$(\forall a \in \mathbb X)(\forall p, q \in \mathbb Y)((a, p) \in f \land (a, q) \in f \implies p = q)$$
• Types of functions $$f: \mathbb X \to \mathbb Y$$:
• $$f$$ is said to be an injection ( 1 to 1 function) iff $$(\forall x_1, x_2 \in \mathbb X) x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$$
• $$f$$ is said to be a surjection (onto function) iff $$(\forall y \in \mathbb Y)(\exists x \in \mathbb X) f(x) = y$$
• If $$f^{-1}$$ is a function from $$\mathbb Y \to \mathbb X$$ then $$f^{-1}$$ is called the inverse function for $$f$$
• Fact: $$f^{-1}$$ is a function iff $$f$$ is a bijection (1 to 1 and onto)
• For some set $$\mathbb A$$ the image of $$\mathbb A$$ by $$f$$ is $$f(\mathbb A) = \{ f(x) : x \in \mathbb A \}$$. We can also define the inverse of an image even when the function itself isn’t invertible: $$f^{-1}(\mathbb A)$$

## Combinatorics⌗

• $$|\mathbb A|$$ size (number of elements) of $$\mathbb A$$
• If $$\mathbb A, \mathbb B \subseteq \mathbb X$$ and $$|\mathbb A|, |\mathbb B| \in \mathbb N$$ and $$\mathbb A \cap \mathbb B = \emptyset$$ then $$|\mathbb A \cup \mathbb B| = |\mathbb A| + |\mathbb B|$$
• Can be generalized as: $(\forall n ) \mathbb{A}_1, \mathbb{A}_2, ..., \mathbb{A}_n \in \mathbb{X} \land \\ |\mathbb{A}_1|, |\mathbb{A}_2|, ..., |\mathbb{A}_n| \in \mathbb{N} \implies \\ (\forall i, j \in \{1, 2, ..., n \})(i \neq j \implies \mathbb{A}_i \cap \mathbb{A}_j = \emptyset)$
• $$\mathbb{A}, \mathbb{B} \subseteq \mathbb{X}, |\mathbb{A} \times \mathbb{B}| = |\mathbb{A}| \cdot |\mathbb{B}|$$
• Can be generalized as: $(\forall n ) \mathbb{A}_1, \mathbb{A}_2, ..., \mathbb{A}_n \in \mathbb{X} \land |\mathbb{A}_i| \in \mathbb{N} \implies \\ |\mathbb{A}_1 \times \mathbb{A}_2 \times ... \times \mathbb{A}_n| = |\mathbb{A}_1| \cdot |\mathbb{A}_2| \cdot ... \cdot |\mathbb{A_n}|$