Graphs
The signature of graphs has no constants or functions, and one binary relation symbol R, where R(x,y) is read as "there is an edge from x to y".
The axioms for the theory of graphs are
- Symmetric: ∀x ∀y R(x,y)→ R(y,x)
- Anti-reflexive: ∀x ¬R(x,x) ("no loops")
The theory of random graphs has the following extra axioms for each positive integer n:
- For any two disjoint finite sets of size n, there is a point joined to all points of the first set and to no points of the second set. (For each fixed n, it is easy to write this statement in the language of graphs.)
The theory of random graphs is ω categorical, complete, and decidable, and its countable model is called the Rado graph. A statement in the language of graphs is true in this theory if and only if it is true with probability 1 for a random graph on a countable number of points.
Read more about this topic: List Of First-order Theories