B.6: Відносини та функції

Last updated
Save as PDF

Page ID: 52748

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Коли ми визначили набір об'єктів (наприклад, натуральні числа або приємні терміни) індуктивно, ми також можемо визначити відносини на цих об'єктах шляхом індукції. Наприклад, розгляньте наступну ідею: приємний термін$t_1$ є субтерміном приємного терміна,$t_2$ якщо він зустрічається як його частина. Давайте використаємо для нього символ:$t_1 \sqsubseteq t_2$. Кожен приємний термін є підтерміном самого себе, звичайно:$t \sqsubseteq t$. Ми можемо дати індуктивне визначення цього співвідношення наступним чином:

Визначення$\PageIndex{1}$

Відношення приємного терміна,$t_1$ що є субтерміном$t_2$$t_1 \sqsubseteq t_2$, визначається індукцією$t_2$ наступним чином:

Якщо$t_2$ буква, то$t_1 \sqsubseteq t_2$ iff$t_1 = t_2$.
Якщо$t_2$ є$[s_1 \circ s_2]$, то$t_1 \sqsubseteq t_2$ iff$t = t_2$$t_1 \sqsubseteq s_1$, або$t_1 \sqsubseteq s_2$.

Це визначення, наприклад, скаже нам про це$\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]$. Для (2) говорить, що$\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]$ iff$\mathrm{a} = [\mathrm{b} \circ \mathrm{a}]$, або$\mathrm{a} \sqsubseteq b$, або$\mathrm{a} \sqsubseteq \mathrm{a}$. Перші два є помилковими:$\mathrm{a}$ явно не ідентичні$[\mathrm{b} \circ \mathrm{a}]$, і по (1),$\mathrm{a} \sqsubseteq \mathrm{b}$ iff$\mathrm{a} = \mathrm{b}$, що також є помилковим. Однак також по (1),$\mathrm{a} \sqsubseteq \mathrm{a}$ iff$\mathrm{a} = \mathrm{a}$, що вірно.

Важливо зазначити, що успіх цього визначення залежить від факту, який ми ще не довели: кожен приємний термін$t$ - це або сама по собі буква, або є однозначно визначені приємні терміни$s_1$ і$s_2$ такі, що $t = [s_1 \circ s_2]$. «Однозначно визначається» тут означає, що якщо$t = [s_1 \circ s_2]$ це не також$= [r_1 \circ r_2]$ з$s_1 \neq r_1$ або$s_2 \neq r_2$. Якби це було так, то пункт (2) може вступити в конфлікт з самим собою: читання,$t_2$ як$[s_1 \circ s_2]$ ми могли б отримати$t_1 \sqsubseteq t_2$, але якщо ми читаємо,$t_2$ як$[r_1 \circ r_2]$ ми можемо отримати не$t_1 \sqsubseteq t_2$. Перш ніж ми доведемо, що цього не може статися, давайте розглянемо приклад, де це може статися.

Визначення$\PageIndex{2}$

Визначте бездужкові терміни індуктивно

Кожна буква - це термін без дужки.
Якщо$s_1$ і$s_2$ є бездужковими термінами, то$s_1 \circ s_2$ це термін без дужки.
Ніщо інше не є бездужним терміном.

Терміни без брекеток є, наприклад,$\mathrm{a}$,$\mathrm{b} \circ \mathrm{d}$,$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$. Тепер, якби ми визначили «підтермін» для термінів без дужки так, як ми зробили вище, другий пункт буде читати

Якщо$t_2 = s_1 \circ s_2$, то$t_1 \sqsubseteq t_2$ iff$t_1 = t_2$$t_1 \sqsubseteq s_1$, або$t_1 \sqsubseteq s_2$.

Тепер$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$ має форму$s_1 \circ s_2$ з

\[s_1 = \mathrm{b} \quad\text{ and }\quad s_2 = \mathrm{a} \circ \mathrm{b}.\nonumber\]

Він також має форму$r_1 \circ r_2$ з

\[r_1 = \mathrm{b} \circ \mathrm{a} \quad\text{ and }\quad r_2 = \mathrm{b}.\nonumber\]

Тепер$\mathrm{a} \circ \mathrm{b}$ є субтерміном$\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}$? Відповідь - так, якщо ми йдемо до першого читання, і ні, якщо ми йдемо за другим.

Властивість, що так, як хороший термін будується з інших приємних термінів є унікальним називається унікальною читаністю. Оскільки індуктивні визначення відносин для таких індуктивно визначених об'єктів є важливими, ми маємо довести, що вони мають місце.

Пропозиція$\PageIndex{1}$

Припустимо,$t$ це хороший термін. Тоді або$t$ є лист сам по собі, або є однозначно визначені приємні терміни$s_1$,$s_2$ такі, що$t = [s_1 \circ s_2]$.

Доказ. Якщо$t$ це лист сам по собі, умова виконується. Так що припустимо, що$t$ це не лист сам по собі. Ми можемо сказати з індуктивного визначення, що потім$t$ повинні бути форми$[s_1 \circ s_2]$ для деяких приємних термінів$s_1$ і$s_2$. Залишається показати, що ці однозначно визначаються, тобто якщо$t = [r_1 \circ r_2]$, то$s_1 = r_1$ і$s_2 = r_2$.

Так припустимо,$t = [s_1 \circ s_2]$ а також$t = [r_1 \circ r_2]$ для приємних умов$s_1$$s_2$,$r_1$,,$r_2$. Ми повинні показати, що$s_1 = r_1$ і$s_2 = r_2$. По-перше,$s_1$ і$r_1$ повинен бути ідентичним, бо в іншому випадку один є правильним початковим відрізком іншого. Але за пропозицією B.5.2, це неможливо, якщо$s_1$ і обидва$r_1$ приємні умови. Але якщо$s_1 = r_1$, то явно теж$s_2 = r_2$. ◻

Ми також можемо визначити функції індуктивно: наприклад, ми можемо визначити функцію,$f$ яка відображає будь-який приємний термін на максимальну глибину вкладеного$[\dots]$ в нього наступним чином:

Визначення$\PageIndex{3}$

Глибина приємного терміна визначається$f(t)$ індуктивно наступним чином:\[f(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(f(s), f(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

Наприклад\[\begin{aligned} f([\mathrm{a} \circ \mathrm{b}]) & = \max(f(\mathrm{a}),f(\mathrm{b})) + 1 = \\ &= \max(0, 0) + 1 = 1, \text{ and}\\ f([[\mathrm{a} \circ \mathrm{b}] \circ \mathrm{c}]) & = \max(f([\mathrm{a} \circ \mathrm{b}]), f(\mathrm{c})) + 1 = \\ & = \max(1,0) + 1 = 2.\end{aligned}\]

Тут, звичайно, ми припускаємо, що$s_1$ an$s_2$ є хорошими термінами, і використовуємо той факт, що кожен приємний термін є або буквою, або формою$[s_1 \circ s_2]$. Знову ж таки важливо, що вона може бути такої форми тільки одним способом. Щоб зрозуміти, чому, знову розглянемо терміни без дужки, які ми визначили раніше. Відповідним «визначенням» було б:

\[g(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(g(s), g(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

Тепер розглянемо бездужковий термін$\mathrm{a} \circ \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}$. Його можна прочитати більш ніж одним способом, наприклад, як$s_1 \circ s_2$ з

\[s_1 = \mathrm{a} \quad\text{ and }\quad s_2 = \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}, \nonumber\]

або як$r_1 \circ r_2$ з

\[r_1 = \mathrm{a} \circ b \quad\text{ and }\quad r_2 = \mathrm{c} \circ \mathrm{d}.\nonumber\]

Обчислення$g$ відповідно до першого способу читання це дало б

\ [\ почати {вирівняний} г (s_1\ circ s_2) & =\ max (g (\ mathrm {a}), g (\ mathrm {b}\ circ\ mathrm {c}\ circ\ mathrm {d}) + 1 =\\
& =\ max (0,2) + 1 = 3\ кінець {вирівняний}\]

тоді як згідно з іншим читанням ми отримуємо

\ [\ почати {вирівняний} g (r_1\ circ r_2) & =\ max (g (\ mathrm {a}\ circ\ mathrm {b}), g (\ mathrm {c}\ circ\ mathrm {d}) + 1=\\
& =\ max (1,1) + 1 = 2\ кінець {вирівняний}\]

Але функція завжди повинна давати унікальне значення; тому наше «визначення» взагалі$g$ не визначає функцію.

Проблема$\PageIndex{1}$

Дайте індуктивне визначення функції$l$, де$l(t)$ - кількість символів у приємному терміні$t$.

Проблема$\PageIndex{2}$

Доведіть структурною індукцією на приємних умовах$t$, що$f(t) < l(t)$ (де$l(t)$ кількість символів в$t$ і$f(t)$ є глибиною,$t$ як визначено у визначенні$\PageIndex{3}$).