January 12, 1999
January 26, 1999
The notion of bisimulation seems to be relevant as a notion of similarity whenever ill-foundedness occurs. We will see definitions and elementary applications in such diverse fields as Modal Logic, Computer Science, (non-well-founded) Set theory, Game Theory and Graph Theory, among others.
There are many properties of the nonnegative integers which are not known to be theorems, or non-theorems, of natural weak systems of arithmetic such as the axiom system I Delta0, whose main axiom is the schema of induction restricted to bounded quantifier formulas. Any nonstandard model M of such axioms has a corresponding field F of fractions, playing the role of rational numbers. An interesting question is the extent to which these axioms of bounded arithmetic need to be augmented in order that various properties of the standard question is the extent to which these axioms of bounded arithmetic need to be augmented in order that various properties of the standard rationals must also be true of F.
An example is the local-global principle (also known as the Hasse-Minkowski principle) which gives a necessary and sufficient condition for the existence of a nontrivial solution in rational numbers to quadratic form equations. This principle is of particular significance, firstly because it generalizes questions considered by other researchers, and secondly because having enough of the local-global principle available seems to be the main extra ingredient required to make Julia Robinson's first order definition of the natural numbers within the rational field work. The presence of such a definition allows a change of perspective, in which the field F is regarded as fundamental, and the underlying model M is recovered as the elements satisfying the definition.