Set, functions and sequences
“The introduction of suitable abstractions is our only mentail aid to organize and master complexity” — E. W. Dijkstra. 1930-2002
Sets
Proper Subset
Let A and B be sets. A is proper subset of B \(\iff \exists \forall a \in A, a \in B\), but \(\exists\) at least one element of B \(\not\in A\).
Cartesian Product
Given sets \(A_1, A_2, …, A_n\), their Cartesian Product is the set of all ordered n-tuples \((a_1, a_2, …, a_n)\) where \(a_1\in A_1, a_2\in A_2, …, a_n\in A_n\).
Set Identities
- Commutative
- Associative
- Distributive
\[A\cup(B\cap C) = (A\cup B)\cap(A\cup C)\\ A\cap(B\cup C) = (A\cap B)\cup(A\cap C)\\ \]
- Identity
- Complement
- Double Complement
- Idempotent
- Universal Bound Law
- De Morgan’s Laws
\[(A\cap B)^c = A^c \cap B^c\\ (A\cup B)^c = A^c \cup B^c\]
- Absorption Laws
- Complements of \(U\) and \(\emptyset\)
- Set Difference Law
\[A-B = A\cap B^c\]
Equality
To prove \(X = Y\), prove \(X\subseteq Y\) and \(Y\subseteq X\).
Boolean Algebra
Definition
Is a set B together with two operations, \(+\) and \(\cdot\), such that for all \(a, b\in B\) B is closed and
- commutative
- associative
- distributive
- identity
- complement
Properties
- Uniqueness of the Complement Law
- Uniqueness of 0 and 1
- Double Complement Law
- Idempotent Law
- Universal Bound Law
- De Morgan’s Laws
- Absorption Laws
- Complements of 0 and 1
Russell’s paradox and the Halting Problem
From the paradise created for us by Cantor, no one will drive us out. — David Hilbert 1862-1943
The Barber Puzzle
In a certain town there is a male barber who shaves all those men, and only those men, who do not shave themselves.
Does the barber shave himself?
Halting Problem
There is no computer algorithm that will accept any algorithm \(X\) and data set \(D\) as input and then will output, “halts” or “loops forever” to indicate whether \(X\) terminates in a finite number of steps when \(X\) is run with data set \(D\).
Proof
Suppose that such a system did exist. Then you could consider the algorithm \(X\) itself as a dataset of characters…
Functions
\[f: X \rightarrow Y\] \(X\) is the domain and \(Y\) is the codomain. The range of \(f\) is the set of all values reached in the codomain. The two can be equal, but do not have to be. 𐃏
Injective
Let \(F\) be a function from a set \(X\) to a set \(Y\). \(F\) is one-to-one (or injective) if, and only if, for all elements \(x_1\) and \(x_2\) in \(X\), if \(F(x_1) = F(x_2)\), then \(x_1 = x_2\) or, equivalently if \(x_1 \neq x_2\) then \(F(x_1) \neq F(x_2)\). 𐃏
Symbolically, \[F: X\rightarrow \text{is one-to-one} \iff \forall x_1, x_2 \in X, \text{if } F(x_1) = F(x_2) \text{ then } x_1 = x_2\]
Surjective
\[F: X\rightarrow \text{is onto} \iff \forall y \in Y, \exists x\in X \text{ s.t. } F(x) = y\]
Bijective
A one-to-one correspondence (or bijection) from a set \(X\) to a set \(Y\) is a function \(F: X\rightarrow Y\) that is both one-to-one and onto.
Inverse Functions
Theorem: If F is bijective, then an inverse exists: \[F^{-1}(y) = x \iff y = F(x)\]
Composition
\[g\circ f: X\rightarrow Z \implies (g\circ f)(x) = g(f(x))\]
sequences
Backlinks (5)
1. Gödel's Incompleteness Theorem /wiki/mathematics/discrete/incompleteness/
In 1931 a twenty-five-year-old in Vienna published a paper proving that mathematics cannot fully formalise itself: any consistent formal system rich enough to do arithmetic contains true statements it cannot prove, and — worse — cannot even prove its own consistency (Gödel, Kurt, 1931). 𐃏 This page walks the actual argument: what the theorem says precisely, the two technical inventions that power it (Gödel numbering and diagonalisation), and — just as important — the long list of things it does not say.
2. Logic /wiki/mathematics/discrete/logic/
logic is the study of valid inference: which conclusions are forced by which premises, independent of what the premises are about. 𐃏 it splits cleanly into a syntax (formulas, and rules for pushing them around) and a semantics (truth assignments, models), and the deepest theorems in the subject are exactly the ones that say when the two agree (Epp, Susanna S., 2019).
3. Number Theory /wiki/mathematics/discrete/number-theory/
number theory studies the integers on their own terms — divisibility, primes, remainders — and for two millennia it was the purest of pure mathematics, prized precisely because it was useless. 𐃏 then in 1977 the RSA cryptosystem turned euclid, fermat and euler into load-bearing internet infrastructure. this page walks the classical results in dependency order and ends at that payoff (Epp, Susanna S., 2019).
4. Graph Theory /wiki/mathematics/discrete/graph-theory/
graph theory began in 1736 when euler noticed that a walking-tour puzzle about seven bridges in königsberg was really a question about dots and lines — and that the geometry (lengths, positions, the river) was irrelevant. 𐃏 that act of abstraction — keep the incidence structure, discard everything else — is the whole subject. a graph is the minimal mathematical model of “things, some pairs of which are related”, which is why it keeps turning up: networks, molecules, dependencies, state machines, social graphs (Epp, Susanna S., 2019).
5. Discrete Mathematics /wiki/mathematics/discrete/
discrete mathematics is the mathematics of structures that come in separate, countable pieces — integers, truth values, finite sets, graphs — as opposed to the smooth continuum of analysis. 𐃏 no limits, no derivatives; instead: induction, counting, and exact structure. it is the native mathematics of computation — every data structure, algorithm, database query and cryptographic protocol below this page is discrete mathematics wearing a lab coat (Epp, Susanna S., 2019).