Article contents
Encoding orders and trees in binary relations
Published online by Cambridge University Press: 26 February 2010
Extract
In Section 1 below I describe two measures of the complexity of a binary relation. J The theorem says that these two measures never disagree very much. Both measures of complexity arose in connection with Saharon Shelah's notion [5] of a stable firstt order theory; Shelah showed in effect that one measure is finite, if, and only if, the other is finite too. This follows trivially from the theorem below. I confess my main aim was not to get the extra information which the theorem provides, but to eliminate Shelah's use of uncountable cardinals, which seemed strangely heavy machinery for proving a purely finitary result. Section 2 below explains the modeltheoretic setting.
MSC classification
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 1981
References
- 5
- Cited by