Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-23/4/c/solution

Use the one-relation language and the total orders
where the second is the order sum: every point in its natural-number block lies below every point in its integer block.
To show II wins every finite Ehrenfeucht-Fraïssé game, use the interval threshold strategy for discrete linear orders. With rounds left, corresponding open intervals and end rays between already matched points have either the same size below , or both have at least elements. Their sizes may be infinite. The chosen-point correspondence is order preserving. Initially the unique interval is infinite in both orders, so the invariant holds.
If I chooses a repeated point, II repeats its counterpart. If I chooses in a short interval, II chooses the point with the same finite rank in the matching interval. In a long interval, let . If one side of the chosen point has fewer than elements, reproduce that size in the other interval; the opposite sides then both have at least elements. Otherwise choose a response having at least elements on each side. Such a response exists because the interval has at least elements. The endpoint and successor/predecessor properties of these two discrete orders allow the finite small-side counts to be reproduced. This establishes the invariant with rounds left and gives a finite-game winning strategy. Therefore II wins the timed game.
In the infinite Ehrenfeucht-Fraïssé game, I first chooses a point in the integer block of . It has infinitely many predecessors. II must respond with some , which has exactly predecessors. I then chooses distinct predecessors of . To preserve order and equality, II would need distinct points below , which is impossible. Thus
I chooses the required finite length only after seeing II's first response, which explains why this does not contradict the timed-game result.

New to topics? Read the docs here!