The Setting
A basic structure, a structure of the kind the paper studies, is handled through its normal form, which has a linear order as its base order. Lemma 3.4 bounds the size of , and the question it answers is one about linear orders: how many points can a linear order have when each of its closed intervals is countable? The rationals are such an order with points, and , ordered lexicographically, is one with .
Intervals and Normal Forms
Let be a linear order. For , the closed interval and the closed initial segment are the sets (1) A locally countable linear order is a linear order in which every closed interval is countable.
A tuple from a set is an injective map for some , a finite sequence of distinct elements of .✦
Array data consist of a nonempty index set , a nonempty base order that is a dense, locally countable linear order without endpoints, and a bit for every tuple from , every and every .✦
The Claim
Theorem 1. Let be a linear order.
(i) If is nonempty and every closed interval of is countable, then (2)✦
(ii) If every closed initial segment of is countable, then (3)✦
(iii) If is the base order of array data , then (4)✦
In the paper, the result reads: every order in a basic structure has cardinality at most .
What Is Checked
The bounds (2) and (3) are stated over a linear order , nonempty with countable closed intervals or with countable closed initial segments (1), and the bound (4) over array data , whose bits are indexed by tuples from .