Alphabeta MathPersonal research
Colourings, embeddings and graph attachments
Develop finite colouring capacity, copy transport, graph operations and labelled attachments for ordinary Ramsey separation, repetition and the recursive induced separator.
1 · Prerequisites
- The Axiom of Union: ∀ x ∃ y ∀ z (z ∈ y ↔ ∃ s (s ∈ x ∧ z ∈ s))
- The Axiom of Extensionality: ∀ x ∀ y (∀ z (z ∈ x ↔ z ∈ y) → x = y)
- The unordered pair {x,y} and the singleton {x} = {x,x}
- For every set x there is exactly one set whose elements are precisely the subsets of x
- Subset x ⊆ y, proper subset x ⊊ y, and the separation notation { z ∈ x : φ(z) }
- If a ∈ A and b ∈ B then (a,b) ∈ P(P(A ∪ B))
- The Axiom Schema of Separation: for each formula φ, ∀ p̄ ∀ x ∃ y ∀ z (z ∈ y ↔ (z ∈ x ∧ φ(z,p̄)))
- The Kuratowski ordered pair (a,b) := {{a},{a,b}}
- Relation, dom R, ran R, fld R, and the specialisations "relation from A to B" and "relation on A"
- (a,b) = (c,d) if and only if a = c and b = d
- The image R[A] and the preimage R⁻¹[B] of a set under a relation
- Inductive set
- The natural numbers exist: a smallest inductive set
- Peano system
- The Axiom of Infinity: there is a set containing a set with no elements and closed under y ↦ y ∪ {y}
- Finite, countably infinite, countable, uncountable
- The pigeonhole principle on ℕ
- Equinumerous sets, A ≈ B and A ⪯ B
- On ℕ the order is membership: m < n ⟺ m ∈ n
- Order on the natural numbers
- Addition of natural numbers
- Addition is cancellative
- Order is compatible with addition
- Discreteness: σ(n) is the immediate successor
- The well-ordering principle
- The sum ∑_i ∈ S aᵢ over a finite index set, and its product form
- A finite sum is unchanged by a permutation of its index range: ∑_k<n a_π(k) = ∑_k<n aₖ for every bijection π : n → n
- Finite sums and finite products of natural numbers, ∑_k<n aₖ and ∏_k<n aₖ in ℕ
- Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ)
- Finite sums and finite products, by recursion
- Laws of finite sums and finite products
- Addition is commutative
- ⌈ m/n ⌉ for naturals m and n ≥ 1: the least q ∈ ℕ with m ≤ n q
- Multiplication is commutative
- Trichotomy of the order on ℕ
- Every nonzero natural number is a successor
- Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Every walk between two vertices contains a path between the same endpoints
- Being joined by a walk or path is the same equivalence relation on the vertex set
- Multiplication of natural numbers
- lvertP(A)| = 2^| A| for finite A
- A bipartite graph and a proper two-colouring of its vertices
2 · Logical flowchart
Arrows show item dependencies. A grouped prerequisite node points to items that use one or more of its members; their exact links are listed above.
3 · Items
Definition
The union ⋃ x of a set, and the binary union a ∪ b := ⋃ {a,b}
Definition
The power set P(x) = { z : z ⊆ x }
Definition
The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }
Definition
A function is a relation f with (a,b) ∈ f and (a,c) ∈ f implying b = c; f : A → B, the value f(a), domain and codomain
Definition
Injection, surjection, bijection
Definition
The natural numbers ℕ (von Neumann)
Theorem
The recursion theorem
Theorem
The principle of mathematical induction
Definition
The cardinality | A| of a finite set
Definition
A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
Definition
Subgraphs, induced subgraphs and spanning subgraphs
Definition
Graph isomorphisms, automorphisms and graph complements
Theorem
A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
Theorem
The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition
Theorem
If | A| > k| B| then every f : A → B has a fibre with more than k elements, and for nonempty B some fibre has at least ⌈ | A| / | B|⌉ elements
Definition
Induced embeddings and induced copies of a graph
Definition
Connected graphs and connected components defined by the existence of vertex paths
Corollary
The connected components of a graph partition its vertex set and are its maximal connected subgraphs
Definition
The complete connection of two disjoint graphs
Theorem
The product rule: | A × B| = | A| | B|, and |∏_i<m Aᵢ| = ∏_i<m| Aᵢ|
Definition
Cliques, independent sets, clique number and independence number
Lemma
G[W]=Ḡ[W] for every vertex set W
Definition
Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
Definition
The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X
Definition