indiscernible sequence?
Morley sequence?
Ramsey theorem?
Erdos-Rado theorem?
Ehrenfeucht-Fraïssé games (back-and-forth games)
The countable random graph, also known as the Rado graph, is the “generic finite graph”: it contains every finite graph as an induced subgraph, models the almost-sure first-order theory of the class of finite graphs, and is axiomatized by the extension property: given any two finite subsets of vertices, there exists a vertex not in either subset which is connected to all the points in one subset and disconnected from the other.
The usual probabilistic construction is given by taking a countably infinite set of vertices and percolating the edges: for any pair of vertices, connect them with probability $\frac{1}{2}$; almost surely the end result will be the countable random graph, which is unique up to isomorphism.
The extension property implies that every formula in the random graph has infinite Vapnik–Chervonenkis dimension?.
Here is an example of a way that the automorphisms of a first-order structure are not generally captured by its theory: a finite graph will almost surely have no nontrival automorphisms while the countable random graph is $\omega$-categorical and thus has infinitely many nontrivial automorphisms.
Last revised on May 19, 2017 at 03:13:26. See the history of this page for a list of all contributions to it.