Рациональное отношение N0 x N0

[VorobeY1326]

Доброго вам дня!

Дано отношение $\alpha \subseteq \mathbb{N}_0 \times \mathbb{N}_0$.
$u \alpha v \leftrightarrow \exists k \in \mathbb{N} (u/k \in \mathbb{N} , v = u + k + u/k + 1 )$.

Проверить, является ли отношение $\alpha$ рациональным.

Эта тема сильно связана с темой topic30731.html , по моему та тема создана человеком, учившимся у того же преподавателя :)

Но, в отличие от той ситуации, у меня $\alpha$ не подмножество $A^* \times B^*$, а подмножество двух произвольных моноидов.

У нас рациональным множеством считается:

Xaositect в сообщении #292796 писал(а):

Цитата из Брауэра:

Определение 8.4.9. Множество $Rat(X, Y)$ рациональных подмножеств произведения $F(X)\times F(Y)$ есть наименьшее подмножество $\mathcal{R}$ булеана $\mathcal{B}(F(X)\times F(Y))$, обладающее следующими свойствами:
1) $\varnothing\in\mathcal{R}$, $\{(x, \Lambda)\}\in\mathcal{R}$ и $\{(\Lambda, y)\}\in\mathcal{R}$ для всех $x\in X$ и $y\in Y$;
2) Если $U$ и $V$ — множества из $\mathcal{R}$, то множества $U\cup V$ и $U\cdot V = \{u\cdot v|u\in U, v\in V\}$ (произведение) также принадлежат $\mathcal{R}$;
3) Если $U\in \mathcal{R}$, то $\mathcal{R}$ содержит также и порожденный множеством $U$ подмоноид $U^{*}$ моноида $(F(X)\times F(Y), \cdot)$, т. е. множество $U^{*} = U^0\cup U^1\cup U^2\cup\dots$.

[Xaositect]

Хинт: представьте отношение в виде объединения отношений, соответствующих различным натуральным $k$.

[VorobeY1326]

То есть представить $\alpha$, как:
$\alpha = \alpha_1 \cup \alpha_2 \cup ... $ , где $\alpha_i$ - аналогично $\alpha$, но для фиксированного $k = i$.

И тогда по каждому $\alpha_i$ нужно построить автомат, чтобы доказать, что $\alpha_i$ рационален. Тогда $\alpha$ будет рациональным, как объединение рациональных.

А автомат для $\alpha_i$ будет, я так понимаю, просто 2 вершины, одна стартовая, вторая конечная, и из первой во вторую переходы по $(n , n + i + n/i + 1)$ для всех $n$, который делят $i$.

Я правильно рассуждаю?)

[Xaositect]

Направление правильное, на последнем шаге не все так просто - получается бесконечное число переходов. Если $n$ делит $i$, то $n = ir$, $n + i + n/i + 1 = \dots$, и дальше уже явно видно, как это представить с помощью одной операции "звездочка".

[VorobeY1326]

Не до конца понял идею со 'звездочкой'.

Вроде бы можно представить множество всех пар, которые удовлетворяют $\alpha_i$ , как $( i , i + 1)^* + (0 , i + 1)$, этим выражением как раз задается $(i , i + i + 1 + 1) , (2i, 2i + i + 2 + 1) , (3i, 3i + i + 3 + 1), ...$ .

А как совместить это выражение и то, что должно быть записано на стрелках автомата, задающего $\alpha_i$ ?

[Xaositect]

Так, посмотрев на задачу еще раз, я что-то начал сомневаться, что такое счетное объединение пройдет. У Вас в курсе была лемма о накачке или вообще какие-нибудь методы для доказательства того, что отношение не является регульярным?

[VorobeY1326]

Я разобрался, как устроен автомат для $\alpha_i$ )

А почему счетное объединение может не пройти?
Ну была лемма о накачке, да.
Сейчас попробую через неё придти к противоречию, но точно ли нельзя доказывать через счетное объединение?) А то все норм сходится так.