689
правок
Изменения
→Перечислимые числа: все
{{Определение
|definition=
Действительное число <tex> \alpha </tex> называется '''перечислимым снизу''' (recursively enumerable number), если множество <tex> \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо.
}}
=== Свойства ===
Число <tex> \alpha </tex> перечислимо снизу тогда и только тогда, когда существует вычислимая возрастающая последовательность рациональных чисел, пределом которой является <tex> \alpha </tex>.
|proof=
<tex>\Rightarrow</tex>:
Так как <tex> A = \{ a \in \mathbb Q \mid a < \alpha \} </tex> перечислимо, то можно перечислить его элементы в возрастающем порядке, они и дают нам необходимую последовательность, так как ее пределом будет <tex> \lim \limits_{n \to \infty} a_n = \sup A = \alpha </tex>.
<tex>\Leftarrow</tex>:
Построим полуразрешитель для множества <tex> A </tex>:
p(x):
'''for''' n in <tex>1..\infty</tex>:
'''if''' <tex> x < a_n </tex>:
'''return''' 1
Если <tex> x \in A</tex>, то <tex> \alpha - x = t > 0 </tex>, и так как <tex> \exists N:\ \forall n > N |a_n - \alpha| < t </tex>, то программа вернет ответ при <tex> n > N </tex>.
}}
|statement=
Число <tex> \alpha </tex> вычислимо тогда и только тогда, когда оно перечислимо сверху и снизу.
|proof=
Обозначим множества <tex> \{a \in \mathbb Q \mid a < \alpha \} </tex> и <tex> \{a \in \mathbb Q \mid a > \alpha \} </tex> за <tex> A </tex> и <tex> B </tex> соответственно.
Если <tex> \alpha </tex> рационально, то необходимые (полу)разрешатели строятся тривиально.
В противном случае, так как <tex> B = \mathbb Q \setminus A</tex>, то перечислимость множеств <tex> A </tex> и <tex> B </tex> равносильна разрешимости множества <tex> A </tex>, которая, в свою очередь, равносильна вычислимости <tex> \alpha </tex>.
}}
