Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 8 / c

Table of contents
- Solution c

Solution

Combine a minimum with an adjacent pair in a linear order:

ξ = (\exists m \forall x \neg (x < m)) \land \exists u \exists v (u < v \land \neg\exists w (u < w \land w < v)) .

In

[0, 1] \cup [2, 3]

, choose

m = 0, u = 1, v = 2

. The minimum and the adjacent pair in a linear order both exist. In

[0, 1]

, the dense order property rules out such an adjacent pair. In

Z

, adjacent pairs exist, but no minimum exists: for any

m

, the integer

m - 1

is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.

Figure 1.
A minimum and an adjacent pair distinguish the two-interval order from a closed interval and the integers
. Orange highlights the consecutive domain members $1$ and $2$ in the two-interval order. The dotted arrow crosses points absent from that domain. A closed real interval has intervening domain members; the integers have adjacent pairs but no minimum. Details.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version