Codex Wiki
OurBigBook.com
Site
Source code
Foundations of mathematics
Home
Mathematics
Area of mathematics
OurBigBook.com
Words: 10k
Articles: 404
Table of contents
10k
404
Set theory
Foundations of mathematics
2k
106
Von Neumann hierarchy
Set theory
45
1
Rank of a set
Von Neumann hierarchy
19
Transitive set
Set theory
20
Well-founded relation
Set theory
23
Extensional relation
Set theory
12
Set
Set theory
243
17
Empty set
Set
6
Singleton set
Set
7
Distinct elements
Set
7
Generating set
Set
20
Subset
Set
17
Set union
Set
17
Set intersection
Set
15
Pair
Set
22
2
Ordered pair
Pair
Unordered pair
Pair
Partially ordered set
Set
64
2
Maximal element of a partially ordered set
Partially ordered set
30
Minimal element of a partially ordered set
Partially ordered set
16
Total order
Set
56
3
Empty order
Total order
11
Greatest element
Total order
18
Initial segment
Total order
11
Binary relation
Set theory
84
4
Reflexive relation
Binary relation
17
Symmetric relation
Binary relation
15
Transitive relation
Binary relation
19
Equivalence relation
Binary relation
19
Function
Set theory
151
9
Identity function
Function
13
Piecewise-linear function
Function
23
Bounded function
Function
30
1
Unbounded function
Bounded function
12
Constant function
Function
10
Real-valued function
Function
27
1
Global maximum
Real-valued function
17
Bijection
Function
19
Periodic function
Function
17
Zorn lemma
Set theory
20
Class in set theory
Set theory
164
4
Proper class
Class in set theory
14
Transitive class
Class in set theory
123
2
Basic set-theoretic axioms inherited by a transitive class
Transitive class
48
Formula relativization to a class
Transitive class
44
Axiom schema of replacement
Set theory
27
Axiom of foundation
Set theory
54
1
Epsilon induction
Axiom of foundation
40
Axiom of power set
Set theory
19
Cumulative hierarchy
Set theory
125
4
Transitive closure
Cumulative hierarchy
81
2
Hereditarily countable set
Transitive closure
47
1
Reasonable set
Hereditarily countable set
23
Hereditarily finite set
Cumulative hierarchy
28
Axiom schema of specification
Set theory
65
1
Relativized closure criterion for separation
Axiom schema of specification
31
Axiom of choice
Set theory
139
4
Choice function
Axiom of choice
23
Well-ordering theorem
Axiom of choice
62
1
Choice-function well-ordering construction
Well-ordering theorem
48
Cardinal comparability principle
Axiom of choice
36
Hartogs theorem
Set theory
17
Tarski cardinal-square theorem
Set theory
62
Image and preimage of a function
Set theory
18
Cartesian product
Set theory
19
Disjoint union
Set theory
14
Fiber product of sets
Set theory
20
Cantor diagonal argument
Set theory
22
Cardinal number
Set theory
356
8
Uncountable set
Cardinal number
17
Initial ordinal
Cardinal number
50
1
Aleph number
Initial ordinal
28
Cardinal arithmetic
Cardinal number
252
3
Product-sum comparison lemma
Cardinal arithmetic
145
Infinite cardinal arithmetic
Cardinal arithmetic
26
König theorem for cardinal numbers
Cardinal arithmetic
51
Cantor-Schröder-Bernstein theorem
Cardinal number
18
Ordinal
Set theory
706
29
Successor ordinal
Ordinal
9
Countable ordinal
Ordinal
9
Order type
Ordinal
26
1
Mostowski collapse theorem
Order type
13
Limit ordinal
Ordinal
23
Transfinite recursion
Ordinal
15
Transfinite induction
Ordinal
20
Ordinal addition
Ordinal
61
2
Associativity of ordinal addition
Ordinal addition
17
Commuting ordinal addition
Ordinal addition
32
Ordinal multiplication
Ordinal
28
Ordinal exponentiation
Ordinal
18
Derived-set iteration of a well-order
Ordinal
88
1
Derived sets of an ordinal
Derived-set iteration of a well-order
22
Ordinal interval
Ordinal
17
First uncountable ordinal
Ordinal
26
1
Tail of the first uncountable ordinal
First uncountable ordinal
14
Cantor normal form
Ordinal
122
3
Leading term of an ordinal
Cantor normal form
106
2
Greatest power of omega below an ordinal
Leading term of an ordinal
35
Leading exponent of an ordinal product
Leading term of an ordinal
50
Indecomposable ordinal
Ordinal
156
4
Additively closed ordinal
Indecomposable ordinal
41
Division by an additively indecomposable ordinal
Indecomposable ordinal
49
Multiplicatively closed ordinal
Indecomposable ordinal
56
1
Multiplicative closure criterion for a power of omega
Multiplicatively closed ordinal
40
Hessenberg natural sum
Ordinal
71
2
Shuffle bound for ordinal partitions
Hessenberg natural sum
48
1
Ordinal partition bound
Shuffle bound for ordinal partitions
27
Mathematical logic
Foundations of mathematics
1k
37
Propositional logic
Mathematical logic
236
8
Soundness theorem for propositional logic
Propositional logic
16
Deductively closed set of formulae
Propositional logic
19
Consistent set of formulae
Propositional logic
25
Finitary set of formulae
Propositional logic
23
Increasing union of deductively closed sets
Propositional logic
31
Maximal consistent set in propositional logic
Propositional logic
44
Propositional compactness theorem
Propositional logic
78
1
Compactness obstruction to expressing totality over an infinite codomain
Propositional compactness theorem
46
First-order logic
Mathematical logic
806
27
First-order language
First-order logic
47
1
Finite language support
First-order language
29
Free variable
First-order logic
19
First-order sentence
First-order logic
22
First-order theory
First-order logic
177
6
First-order axiomatizable class
First-order theory
41
Consistent first-order theory
First-order theory
38
1
Monotonicity of inconsistency
Consistent first-order theory
17
Finite character of formal proofs
First-order theory
17
Universal first-order theory
First-order theory
58
1
Finite forbidden-pattern axiomatization
Universal first-order theory
38
First-order structure
First-order logic
207
6
Model of a first-order theory
First-order structure
16
Automorphism of a first-order structure
First-order structure
172
4
First-order axiomatization of an automorphism
Automorphism of a first-order structure
33
Faithful automorphism action
Automorphism of a first-order structure
30
Rigid first-order structure
Automorphism of a first-order structure
90
1
Compactness transfer of finite nonrigidity
Rigid first-order structure
59
Soundness theorem for first-order logic
First-order logic
15
Godel completeness theorem
First-order logic
24
Compactness theorem
First-order logic
144
3
Syntactic proof of first-order compactness
Compactness theorem
32
Compactness obstruction to axiomatizing finitely many maximal elements
Compactness theorem
41
Compactness obstruction to an exclusive disjunction of infinitude
Compactness theorem
53
Lowenheim-Skolem theorem
First-order logic
133
2
Upward Lowenheim-Skolem theorem
Lowenheim-Skolem theorem
65
Downward Lowenheim-Skolem theorem
Lowenheim-Skolem theorem
51
Computability theory
Foundations of mathematics
1k
39
Register machine
Computability theory
243
5
String register machine
Register machine
206
4
Characteristic-function register machine
String register machine
163
3
One-register separation for equal block lengths
Characteristic-function register machine
49
String register-machine suffix test
Characteristic-function register machine
41
Complementing a characteristic-function register machine
Characteristic-function register machine
41
Primitive recursive function
Computability theory
141
7
Initial function of recursion theory
Primitive recursive function
49
3
Zero function
Initial function of recursion theory
18
Successor function
Initial function of recursion theory
5
Projection function
Initial function of recursion theory
12
Function composition in recursion theory
Primitive recursive function
18
Primitive recursion
Primitive recursive function
20
Composition-only recursive function
Primitive recursive function
39
Diagonal argument
Computability theory
18
Recursively enumerable set
Computability theory
86
1
Domain and range characterizations of a nonempty computably enumerable set
Recursively enumerable set
60
Recursion theorem
Computability theory
21
Many-one reduction
Computability theory
77
3
Many-one degree
Many-one reduction
14
Computable reduction by staged enumeration
Many-one reduction
23
Many-one complete set
Many-one reduction
23
Index set
Computability theory
129
5
Extensional property of programs
Index set
14
Rice theorem
Index set
14
Infinite-domain index set
Index set
63
1
Infinite-domain range-restriction index set
Infinite-domain index set
46
Cofinite index set
Index set
12
Padding lemma
Computability theory
17
Dovetailing
Computability theory
16
S-m-n theorem
Computability theory
37
Partial computable function
Computability theory
141
3
Unbounded minimization
Partial computable function
53
Total computable function
Partial computable function
14
Truncated computation function
Partial computable function
49
Arithmetical hierarchy
Computability theory
119
3
Sigma-1 set
Arithmetical hierarchy
29
Pi-2 set
Arithmetical hierarchy
76
1
Totality problem
Pi-2 set
36
Formal language theory
Foundations of mathematics
2k
56
Regular expression
Formal language theory
43
1
Kleene theorem
Regular expression
21
Formal grammar
Formal language theory
379
13
Variable-based grammar
Formal grammar
365
12
Unreachable nonterminal
Variable-based grammar
27
Nonproductive nonterminal
Variable-based grammar
32
Regular grammar
Variable-based grammar
127
5
Sentential form of a right-linear regular grammar
Regular grammar
33
Accessible variable of a regular grammar
Regular grammar
13
Looping variable of a regular grammar
Regular grammar
16
Terminable variable of a regular grammar
Regular grammar
13
Accessible looping terminable variable criterion
Regular grammar
27
Concatenation grammar
Variable-based grammar
147
3
Regular concatenation grammar
Concatenation grammar
89
1
Failure of the regular concatenation construction for a nonregular grammar
Regular concatenation grammar
42
Concatenation grammar need not be regular
Concatenation grammar
27
Context-free language
Formal language theory
395
13
Context-free grammar
Context-free language
326
9
Grammar derivation
Context-free grammar
34
Parse tree
Context-free grammar
43
Equivalent grammar
Context-free grammar
52
1
Isomorphic grammar
Equivalent grammar
41
Chomsky normal form
Context-free grammar
154
4
Epsilon production
Chomsky normal form
14
Unit production
Chomsky normal form
14
Chomsky-normal-form derivation length
Chomsky normal form
29
Weak Chomsky normal form
Chomsky normal form
46
Context-free grammar for even palindromes
Context-free language
12
Closure of context-free languages under regular intersection
Context-free language
25
Nested-count context-free grammar
Context-free language
19
Pumping lemma for context-free languages
Formal language theory
58
1
Three-block context-free pumping obstruction
Pumping lemma for context-free languages
29
Deterministic finite automaton
Formal language theory
192
7
Extended transition function of a deterministic finite automaton
Deterministic finite automaton
18
Accessible state of a deterministic finite automaton
Deterministic finite automaton
21
Indistinguishable states of a deterministic finite automaton
Deterministic finite automaton
64
1
Quotient deterministic finite automaton by indistinguishable states
Indistinguishable states of a deterministic finite automaton
38
Irreducible deterministic finite automaton
Deterministic finite automaton
74
2
Minimal deterministic finite automaton
Irreducible deterministic finite automaton
56
1
Accessible unary deterministic finite automaton
Minimal deterministic finite automaton
30
Nondeterministic finite automaton
Formal language theory
188
5
Extended transition of a nondeterministic finite automaton
Nondeterministic finite automaton
55
1
Witnessing sequence for a nondeterministic automaton
Extended transition of a nondeterministic finite automaton
32
Powerset construction
Nondeterministic finite automaton
31
Brzozowski automaton
Nondeterministic finite automaton
75
1
Irreducibility of the accessible subset automaton
Brzozowski automaton
45
Regular language
Formal language theory
20
Pumping lemma for regular languages
Formal language theory
32
Myhill-Nerode theorem
Formal language theory
53
1
Myhill-Nerode equivalence
Myhill-Nerode theorem
32
Closure properties of formal languages
Formal language theory
21
Computably enumerable language
Formal language theory
132
4
Halting problem
Computably enumerable language
116
3
Diagonal halting set
Halting problem
101
2
Many-one completeness of the halting problem
Diagonal halting set
72
1
Distinct representative of the halting many-one degree
Many-one completeness of the halting problem
19
Graph theory
Foundations of mathematics
3k
123
Binomial random graph
Graph theory
144
3
Clique count in a binomial random graph
Binomial random graph
24
Triangle count in a binomial random graph
Binomial random graph
29
Triangle with an attached leaf in a binomial random graph
Binomial random graph
68
Graph
Graph theory
60
4
Vertex of a graph
Graph
13
Isomorphic graphs
Graph
12
Triangle in a graph
Graph
27
1
Triangle-free graph
Triangle in a graph
7
Graph colouring
Graph theory
186
6
Chromatic number
Graph colouring
41
1
Brooks' theorem
Chromatic number
23
Edge chromatic number
Graph colouring
21
Chromatic polynomial
Graph colouring
101
2
Deletion-contraction recurrence for the chromatic polynomial
Chromatic polynomial
47
Chromatic polynomial after attaching a leaf
Chromatic polynomial
27
Independent set
Graph theory
25
Leaf of a graph
Graph theory
8
Edge of a graph
Graph theory
20
Path in a graph
Graph theory
51
2
Long path from minimum degree
Path in a graph
18
Erdos-Gallai path edge bound
Path in a graph
15
Subgraph
Graph theory
85
2
Induced subgraph
Subgraph
22
Three-colourable two-thirds subgraph lemma
Subgraph
42
Complete graph
Graph theory
58
2
Clique
Complete graph
24
Adjacency-matrix quadratic relation for a complete graph
Complete graph
20
Graph Laplacian
Graph theory
49
1
Laplacian spectrum of a complete graph
Graph Laplacian
24
Minimum-cost flow
Graph theory
40
Extremal graph theory
Graph theory
160
6
Extremal number
Extremal graph theory
34
1
Mantel theorem
Extremal number
12
Turan theorem
Extremal graph theory
126
3
Quadratic Turan edge bound
Turan theorem
9
Rhombus-free edge bound
Turan theorem
85
1
Triangular prism graph
Rhombus-free edge bound
32
Flow network
Graph theory
111
2
Max-flow min-cut theorem
Flow network
85
1
Parametric maximum flow with one source capacity
Max-flow min-cut theorem
40
Eulerian graph
Graph theory
54
1
Euler circuit criterion
Eulerian graph
41
Line graph
Graph theory
46
1
Line graph of a regular graph is Eulerian
Line graph
24
Planar graph
Graph theory
87
3
Euler formula for a connected planar graph
Planar graph
71
2
Planar graph edge bound
Euler formula for a connected planar graph
12
Planar girth edge bound
Euler formula for a connected planar graph
23
Crossing number
Graph theory
70
1
Crossing lemma
Crossing number
37
Graph neighbourhood
Graph theory
35
1
Common neighbour
Graph neighbourhood
14
Degree of a vertex
Graph theory
34
1
Locally finite graph
Degree of a vertex
11
Cut of a graph
Graph theory
180
5
Maximum cut
Cut of a graph
13
Unfriendly partition of a graph
Cut of a graph
143
3
Unfriendly partition theorem for a finite graph
Unfriendly partition of a graph
32
Unfriendly partition theorem for a countable locally finite graph
Unfriendly partition of a graph
40
Random unfriendly partition of a countable infinite-degree graph
Unfriendly partition of a graph
48
Bipartite graph
Graph theory
60
2
Complete bipartite graph
Bipartite graph
21
Two-colourability criterion for bipartite graphs
Bipartite graph
20
Directed graph
Graph theory
108
4
Directed edge
Directed graph
16
Directed walk
Directed graph
33
1
Closed directed walk
Directed walk
12
Adjacency matrix of a directed graph
Directed graph
49
Adjacency matrix of a graph
Graph theory
54
1
Walk count from powers of an adjacency matrix
Adjacency matrix of a graph
35
Graph distance
Graph theory
74
2
Graph diameter
Graph distance
59
1
Linear independence of adjacency powers up to the diameter
Graph diameter
45
Graph eigenvalue
Graph theory
13
Bipartite adjacency matrix
Graph theory
47
1
Perfect matching from a nonzero determinant
Bipartite adjacency matrix
32
Matching in a graph
Graph theory
227
8
Perfect matching
Matching in a graph
9
Maximal matching
Matching in a graph
37
Matching number
Matching in a graph
16
Hall marriage theorem
Matching in a graph
78
2
Hall induction through a tight set
Hall marriage theorem
39
Regular bipartite graph has a perfect matching
Hall marriage theorem
23
Regular-graph matching bound from unmatched vertices
Matching in a graph
58
1
Disjoint union of triangles as a sharp matching example
Regular-graph matching bound from unmatched vertices
25
Antichain
Graph theory
13
Ramsey theorem
Graph theory
239
8
Diagonal Ramsey number
Ramsey theorem
34
1
Binomial upper bound for a Ramsey number
Diagonal Ramsey number
13
Graph Ramsey number
Ramsey theorem
191
5
Off-diagonal graph Ramsey number
Graph Ramsey number
44
1
Clique-path Ramsey number
Off-diagonal graph Ramsey number
16
Ramsey number of a star
Graph Ramsey number
31
Paw graph
Graph Ramsey number
72
1
Ramsey number of the paw graph
Paw graph
62
Dirac theorem
Graph theory
15
Longest-path rotation
Graph theory
109
1
Neighbourhood bound for a square-free bipartite graph
Longest-path rotation
61
Strongly regular graph
Graph theory
17
Moser spindle
Graph theory
12
Random graph
Graph theory
287
8
Isolated vertex
Random graph
6
Erdős-Rényi model
Random graph
268
6
Isolated vertices in the Erdős-Rényi model
Erdős-Rényi model
75
1
Isolated-vertex threshold in the Erdős-Rényi model
Isolated vertices in the Erdős-Rényi model
40
Connectivity threshold in the Erdős-Rényi model
Erdős-Rényi model
44
Expected subgraph count in the Erdős-Rényi model
Erdős-Rényi model
131
2
Sparse clique-count concentration
Expected subgraph count in the Erdős-Rényi model
48
Vertex-disjoint sparse clique copies
Expected subgraph count in the Erdős-Rényi model
43
Complement graph
Graph theory
24
Menger theorem
Graph theory
239
10
Vertex separator
Menger theorem
26
Internally vertex-disjoint paths
Menger theorem
13
Set version of Menger theorem
Menger theorem
29
Linked graph
Menger theorem
26
Vertex connectivity
Menger theorem
64
2
Dirac circumference theorem
Vertex connectivity
43
1
Longest-cycle attachment argument
Dirac circumference theorem
30
Edge connectivity
Menger theorem
14
Whitney inequalities for graph connectivity
Menger theorem
37
1
Connectivity realization construction
Whitney inequalities for graph connectivity
31
Bipartite vertex cover
Graph theory
16
Statistical learning theory
Foundations of mathematics
844
33
Bounded differences inequality
Statistical learning theory
25
Uniform stability of a learning algorithm
Statistical learning theory
27
Hypothesis class
Statistical learning theory
40
1
Sign function
Hypothesis class
19
Empirical risk minimization
Statistical learning theory
32
1
Squared-loss empirical risk for linear prediction
Empirical risk minimization
17
Regression tree
Statistical learning theory
91
1
Conditional variance of a fixed regression-tree partition
Regression tree
39
Shattering coefficient
Statistical learning theory
180
7
Shattering coefficient of a union
Shattering coefficient
30
VC dimension
Shattering coefficient
142
5
Sauer-Shelah lemma
VC dimension
26
1
Sauer-Shelah growth bound
Sauer-Shelah lemma
19
VC dimension bound for lower orthants
VC dimension
42
VC dimension of interval indicators
VC dimension
31
VC dimension of intervals and their complements
VC dimension
24
VC dimension of a vector space
Statistical learning theory
125
3
VC dimension upper bound for Euclidean balls
VC dimension of a vector space
33
Quadratic feature map
VC dimension of a vector space
17
Growth bound for homogeneous linear classifiers
VC dimension of a vector space
23
Growth bound for signs of m-term linear combinations
Statistical learning theory
72
1
Growth bound for a single-hidden-layer sign network
Growth bound for signs of m-term linear combinations
33
AdaBoost
Statistical learning theory
63
1
Exponential classification risk
AdaBoost
26
Rademacher complexity
Statistical learning theory
177
7
Massart finite-class lemma
Rademacher complexity
20
Rademacher bound for bounded weighted indicators
Rademacher complexity
39
Rademacher complexity of a convex hull
Rademacher complexity
24
Rademacher contraction lemma
Rademacher complexity
20
Frobenius norm Rademacher calculation
Rademacher complexity
13
Rademacher complexity of quadratic forms
Rademacher complexity
21
Expected excess-risk bound for empirical risk minimization
Rademacher complexity
23
Hinge loss
Statistical learning theory
12
Mathematical proof
Foundations of mathematics
75
3
Counterexample
Mathematical proof
19
Structural induction
Mathematical proof
24
Probability-preserving bijection
Mathematical proof
18
Ancestors
(3)
Area of mathematics
Mathematics
Home
Codex Wiki