Skip to main content
2 of 2
added 3 characters in body
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Disclaimer: I last seriously tackled any papers of Shelah over 20 years ago. There are conventions which puzzle me (and are probably important), but I am not reading the whole paper. Someone who has read it can probably explain the conventions and the reason for them.

Convention one. There are some pairs of symbols like I and I* and D and D* which may be related. One might stand for a subset of another perhaps,, or that there is a containment relationship. For now I pretend they are separate variables standing for subsets of the reals with I variables for intervals.

Convention two: in the key part of the construction, an equation is given for translating an atomic formula with relation symbol R_l, and another for the negation of an atomic formula with relation symbol R_l. However, I read it as saying use the first only if the subscript l is less than 0, and the other only if the subscript l is greater than or equal to zero. Perhaps it is important (since one is dealing with Skolemnization prior to this) to represent a relation in two ways, with a negative and with a positive index. I am unsure.

If I ignore these two conventions, I read the machine as a rather tedious and complex but straightforward transcription. Here is my take on it.

Back a couple pages (Definitions 7.1 and 7.2 for those of you following at home), Shelah defines a couple of families of formulae indexed by a parameter n, in the nomadic theory. Formula n for one family says there are n+1 disjoint sets Y_i which have magical properties in relation to the other sets in the formula. and formula n for the other family includes the formula n for the first family, plus a negation of that same formula but applied to a certain class of supersets. (I am mangling for simplicity; if you know the monadic theory, go read the actual definitions for yourself.)

In doing the construction, Shelah only seems to use members of either family with indices 0,1, and 2. I don't know why. However, much of the time, these members seem stand alone and do not have much to do with the relation symbols present on the relational number theory.

So now we come to the machine. The goal (for the theorem) is to take a sentence of relational number theory and do a Skolem normal form of it so it looks like AE matrix of atomic formulae and their negations with only relation symbols including equality (such as Matt F has provided), and then transform this into a sentence in the monadic theory so that the input is true in a certain model of relational number theory iff the output holds in something, probably a standard model of the monadic theory.

Let me handle the key parts of the machine backwards (and in doing so, attempt an answer to the question asked). Step (3) says write the Skolem form AE matrix as AE newmatrix, where newmatrix is a pattern that follows the pattern of matrix, but using and-or instead of or-and, and for each atomic/negatomic formula in the matrix, using a transformed portion of that piece. There is also a preamble in the formula that suggests to me a C-include file for stdio. (But I digress.)

Step (2) handles the transform negatomic formulae which is the negation of the transform for the atomic formulae. The surprise here is that this is for index l at least zero, where l is the index on the relation symbol.

Step (1) is the key to understand (which I don't) and handles the transform of an atomic formula, but this for relation symbols with negative index l. However, ignoring that, one creates a preamble, and uses psi_2 (from Definition 7.2), and other things which I am shaky on, and set variables that I will type as Qli, which is indexed using both l (for the lth relation) and i (for the ith variable in a relation with arity m(l)).

So I can answer the recent question: how are the transforms different? For the two sentences given above, syntactically because they use different sets of Qli: one uses a set for the S relation, and a different one for the P relation.

Step (0) is a monadic version of equality to stand in for the atomic formula x=y.

There is a lot more to the machine, and seems to depend on a certain precondition, but now I have enough to take a stab at what is going on.

Shelah is replacing relation symbols in the input formula by tuples of specialized variables, and these variables sit in the Q place in the two infinite families. The set Q in earlier lemmata and definitions suggest that there is a perfect set P which avoids Q (or has small intersection with Q) and P stands in a nice relation with other parameters in the formula. I'm thinking that Shelah replaces a relation in rational number theory (which is a subset or sub universe of a power of omega), with a nicely condition subset of (some power, perhaps of) the reals. To get his theorem (relational number theory is recursive in the .indicate theory of order), he chooses the Q to satisfy the preamble and to bear some resemblance to the relations on the number theory model to make the transform true iff the input sentence is true.

While I hope my take is helpful, a serious student of the paper should resolve the two conventions first and take their own stab at Theorem 7.10 and the machinery behind it.

Gerhard "Wants To Keep His Comments" Paseman, 2019.07.07.

(To Matt F : even if they seem disjointed. We can have moderators arbitrate if this is a big issue for you.)

Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63