I'm trying to understand Shelah's prototypical example of DOP here on page 26, item (c). It would be a very nice example if correctly understood.However, there is some strange mixture in the definition of $P^M$. It says after decoding
$P^M=\{(s,t,(s,t,\alpha)):$for some $\alpha \}$
What is weird for me is the nested usage of "(" here. What is the arity of $P^M$? Is his definition of $P^M$ correct?
Moreover, I do not understand his claim on how $R$ can be defined in $M_{I,R}$, and why this definition is not first order. Is this due to the word uncountable? This last paragraph is certainly my misunderstanding.
I agree that what Shelah writes here is somewhat confusing. Here's what he means: Let $I$ be an infinite set. Now to each ordered pair $(i,j)\in I^2$, we want to attach an infinite set $X_{i,j}$. I think the easiest way to accomplish this is to include a second sort $K$ and a pair of projection functions $\pi_1\colon K\to I$ and $\pi_2\colon K\to I$, so that $X_{i,j} = \{x\in K\mid \pi_1(x) = i\text{ and } \pi_2(x) = j\}$ (note that $X_{i,j}$ is definable from the parameters $i$ and $j$). What Shelah does instead is to make the domain of his model $I \cup K$ and include a $3$-ary relation $P$ so that $P(i,j,x)$ holds iff $x\in X_{i,j}$ (in his notation, the elements $x\in K$ are thought of as triples $(i,j,\alpha)$ where the first two coordinates are the $(i,j)$ such that $x\in X_{i,j}$ and the third coordinate is an ordinal - but this is an unnecessary confusion).
So pick either way of encoding this situation. The upshot is that our theory $T$ will say that every element is either in $I$ or $K$, $I$ is an infinite set, and for every pair $(i,j)$, we have an infinite definable set $X_{i,j}$, and all the $X_{i,j}$ are disjoint and disjoint from $I$. That information axiomatizes a complete theory. Note that I haven't said anything about countable or uncountable (or the relation $R$) yet: $T$ is a first-order theory, so it can't express these notions.
Now the relation $R$ comes in when we consider the models of $T$. Let $R$ be an arbitrary binary relation on an infinite set $I$. We construct the model $M_{I,R}\models T$ as follows: take the $I$ sort to be $I$, and for each pair $(i,j)\in I^2$, make $X_{i,j}$ countable if $(i,j)\in R$ and make $X_{i,j}$ have size $\aleph_1$ if $(i,j)\notin R$. Now $M_{I,R}$ encodes the binary relation $R$ in the sense that $M_{I,R}\cong M_{I,R'}$ if and only if $(I,R)\cong (I,R')$.
The point is that $T$ has the maximum number of models in all uncountable cardinalities, and this is because of the DOP ("dimensional order property"). If $I$ is uncountable of size $\kappa$, we have $|M_{I,R}| = |I| = \kappa$, and there are $2^\kappa$ many binary relations (already $2^\kappa$ many linear orders - this is why "order property" appears in the name of the DOP) on a set of size $\kappa$ up to isomorphism.
But despite this, $T$ is a nice stable theory. This is because the possibly nasty binary relations $R$ are not first-order definable, so $T$ can't "see" them. They're encoded into models of $T$ via dimensions (in this case, "dimension" just means the sizes of the infinite sets $X_{i,j}$).
Finally, if you're learning about DOP, you might be interested in John Goodrick's blog post Demystifying DOP and the references given there.