Лекция 2. Арифметика Пеано

Арифметика Пеано PA (формулировка как теории 1-го порядка). Доказательства простейших свойств натуральных чисел в PA. Доказуемо тотальные функции в теориях 1-го порядка, теорема о консервативном расширении новым функциональным символом для такой функции (псевдотермы). Деление с остатком в PA. Две леммы о взаимной простоте: $\mathrm{PA} \vdash a, b > 1 \wedge a, b \text{ вз. просты} \to \exists x, y \, (ax + 1 = by)$ и $\mathrm{PA} \vdash p \text{ простое} \wedge p \mid a b \to p \mid a \vee p \mid b$.