Regularity and non-standard models of arithmetic #PaCE1

regularity_nonstandard.md

Text used in the video

https://youtu.be/UG-evnE3-p0

==== Regularity statement ====

https://en.wikipedia.org/wiki/Axiom_of_regularity

(Classically) $\forall s.\Big(s\neq\emptyset,\to,\exists(x\in s). x\cap s=\emptyset\Big)$

==== History ====

https://en.wikipedia.org/wiki/Zermelo_set_theory (No regularity or replacement)

Excerpt from: Thoralf Skolem - "Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre" (1922) A.k.a. "Some remarks on axiomatized set theory" Also reprinted in a translation in "From Frege to Gödel", 1999, pp. 290-.

1925: von Neumann shills regularity for his ordinals.

==== Least number principle ====

==== von Neumann model ====

https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

Set theoretical Neumann model for PA:

$0$ ... $\emptyset$

$Sx$ ... $x\cup{x}$

So

$1=S0={0}={\emptyset}$

$2=S1={0,1}={\emptyset,{\emptyset}}$

$3=S2={0,1,2}={\emptyset,{\emptyset},{{\emptyset}}}$

$4=S3={0,1,2,3}={\emptyset,{\emptyset},{{\emptyset}},{{{\emptyset}}}}$

$\dots$

$\omega={0,1,2,\dots}$

The Model proves all the axioms of the FOL theory.

$x < y$ ... $x\in y$

E.g.

$2<4\iff{\emptyset}\in{\emptyset,{\emptyset},{{\emptyset}},{{{\emptyset}}}}$

Note:

$n={k\in\omega\mid k < n}$

==== A world without regularity ====

$c={c}$

$c\in c$

(So $c < c$ if we want to use the notation $<$ also for other sets)

$Sc=c\cup{c}=c\cup c=c$

==== As statement in set theory ====

https://en.wikipedia.org/wiki/Taxicab_number

For any property $T$, if any number has the property, then there is a smallest natural with that property.

For a von Neumann natural

$n={k\in\omega\mid k < n}$

$\Theta$ ... ${n\in\omega\mid T(n)}$

$n\in\Theta$ ... $T(n)$

(Classically)

$\Theta\neq\emptyset,\to,\exists (n\in \Theta). n\cap \Theta=\emptyset$

$\exists m.T(m),\to,\exists n.\big(T(n)\land\forall(k < n).\neg T(k)\big)$

https://en.wikipedia.org/wiki/Induction,_bounding_and_least_number_principles

==== Logical definitions and theorems ====

$\forall(z < y).P(z)$ ... $\forall z.\big((z < y)\to P(z)\big)$

(used above)

$\forall x.\neg P(x)\leftrightarrow\neg\exists x.P(x)$

$(A\to\neg B)\leftrightarrow\neg(A\land B)$

$(A\to B)\to(\neg B\to\neg A)$

==== On Q ====

Theory signature/primitives: $S, 0$ and $+, \cdot$

https://en.wikipedia.org/wiki/Robinson_arithmetic

https://ncatlab.org/nlab/show/Robinson%20arithmetic

==== Axioms ====

(Universal closures $\forall x$ and, where applicable, $\forall y$)

$\neg(Sx=0)$

$(Sx=Sy)\to(x=y)$

$x+0=x$

$x+Sy=S(x+y)$

$x\cdot 0=0$

$x\cdot Sy=x\cdot y+x$

But one formula with an existential quantifier:

$y=0\lor\exists z.(Sz=y)$

==== Definitions ====

Here the relation is defined in terms of primitives that aren't relations.

$k < n$ ... $\exists m. k + Sm = n$

==== Some calculations ====

${\mathbb N}$ ... ${0, 1, 2, 3, \dots}$

$\frac{1}{2}0\cdot (0+1) = 0 = 0$

$\frac{1}{2}1\cdot (1+1) = 1 = 0 + 1$

$\frac{1}{2}2\cdot (2+1) = 3 = 0 + 1 + 2$

$\frac{1}{2}3\cdot (3+1) = 6 = 0 + 1 + 2 + 3$

Assume, for any particular $n$ ...

$\sum_{k=1}^n k = \frac{1}{2}n\cdot (n+1)$

then

$\sum_{k=1}^{n+1} k = \big(\sum_{k=1}^{n} k\big)+(n+1) = \frac{1}{2}n\cdot (n+1) + \frac{1}{2} 2 (n+1) = \frac{1}{2}(n+1)(n+2)$

==== Q Models ====

==== Standard model ====

The "intended" "standard" "matchbox" model of the naturals, call it $\mathbb N$.

==== One infinite number ====

The standard model plus one element, $\mathbb N+{c}$.

$x\cdot y=y\cdot x$

$x+y=y+x$

$c\cdot 0=0$

$c+x=c$

E.g. $c+S0=c$.

So $\exists y. c+Sy=c$.

I.e. $c < c$.

==== Certain polynomials ====

Integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial.

(see Wikipedia)

==== On PA ====

https://en.wikipedia.org/wiki/Peano_axioms

$\forall n.\Big(Q(0)\land \forall n.\big(Q(n)\to Q(Sn)\big)\Big),\to,\forall m.Q(m)$

$\bullet$ Induction example:

$\forall(n\in{\mathbb N}). \sum_{k=1}^n k = \frac{1}{2}n\cdot (n+1)$

$\bullet$ Also proves that every number has a predecessor - see the axiom in ${\mathsf Q}$.

$\bullet$ Also e.g. proves that every number is either even or odd.

==== Complete induction ====

Complete induction:

$\forall n. \Big(\big(\forall(k < n).Q(k)\big),\to,Q(n)\Big),\to,\forall m.Q(m)$

Hint for proof from induction:

$\big(\forall(k < Sn).Q(k)\big),,\leftrightarrow,,\big(\forall(k < n).Q(k)\big)\land Q(n)$

==== Contrapositive ====

$\forall n. \Big(\big(\forall(k < n).Q(k)\big),\to,Q(n)\Big),\to,\forall m.Q(m)$

$\neg\forall m.Q(m),\to,\neg\forall n. \Big(\big(\forall(k < n).Q(k)\big),\to,Q(n)\Big)$

$Q$ ... $\neg T$

$\neg\forall m.\neg T(m),\to,\neg\forall n. \Big(\big(\forall(k < n).\neg T(k)\big),\to,\neg T(n)\Big)$

$\big(\neg\neg\exists m.T(m)\big),\to,\neg\neg\exists n.\Big(\big(\forall(k < n).\neg T(k)\big),\land T(n)\Big)$

==== a < a ====

For any relation $R$,

$P_R$ ... $\exists x.\big(x=a\land\forall y.(R(y,a)\to y\neq a)\big)$

$R(a,a)\to\neg P_R$

Least number principle for $R$ equal to $&lt;$ and $T$ equal to $x=a$:

$\big(\neg\neg\exists m.m=a\big),\to,\neg\neg P_{ &lt; }$

This exactly negates that an $a$ would have $a &lt; a$.

==== Decidable T ====

Weakening the antecedant to $\exists m. T(m)$, we can scan the $k &lt; m$ for a lowest element.

As always, adopt Markov's principle if ya like.

==== Non-standard models of PA ====

Note: Countable non-standard models

https://victoriagitman.github.io/images/PAmodel.jpg

(Where the division notation $/$ is division without rest.)

Roughly, ${\mathbb N}+{\mathbb Q}\times{\mathbb Z}$

Indeed we can take $\mathsf Q$ and add a recursive (computable) set of axioms, saying that $c$ is bigger than each standard natural $n$.