avewright/proofwiki-math huggingface dataset:
Theorem: Substitution of Constant yields Primitive Recursive Function

Let $f: \N^{k + 1} \to \N$ be a primitive recursive function.
Then $g: \N^k \to \N$ given by:
:$\map g {n_1, n_2, \ldots, n_k} = \map f {n_1, n_2, \ldots, n_{i - 1}, a, n_i \ldots, n_k}$
is primitive recursive.

Proof:
Let $n = \tuple {n_1, n_2, \ldots, n_{i - 1}, n_i \ldots, n_k}$.
We see that:
:$\map g {n_1, n_2, \ldots, n_k} = \map f {\map {\pr^k_1} n, \map {\pr^k_2} n, \ldots, \map {\pr^k_{i - 1} } n, \map {f_a} n, \map {\pr^k_i} n, \ldots, \map {\pr^k_k} n}$
We have that:
* $\pr^k_j$ is a basic primitive recursive function for all $j$ such that $1 \ne j \le k$
* $f_a$ is a primitive recursive function.
So $g$ is obtained by substitution from primitive recursive functions and so is primitive recursive.
{{qed}}
Category:Primitive Recursive Functions
cei73njoeuk6jhjr1io40rx6qp71l6s
Theorem: Exponentiation is Primitive Recursive

The function $\exp: \N^2 \to \N$, defined as:
:$\map \exp {n, m} = n^m$
is primitive recursive.

Proof:
We observe that:
:$\map \exp {n, 0} = n^0 = 1$
and that:
:$\map \exp {n, m + 1} = n^\paren {m + 1} = \paren {n^m} \times n = \map {\mathrm {mult} } {\map \exp {n, m}, n}$.
Thus $\exp$ is defined by primitive recursion from the primitive recursive function $\mathrm {mult}$.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
7qq7k8eoxrrblwx2dkli15ih5gcxlp4
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
Work the Euclidean Division Algorithm backwards.
{{qed}}
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $S$ be the set of all positive integer combinations of $a$ and $b$:
:$S = \set {x \in \Z, x > 0: x = m a + n b: m, n \in \Z}$
First we establish that $S \ne \O$.
We have:
{{begin-eqn}}
{{eqn | l = a > 0
      | o = \implies
      | r = \size a = 1 \times a + 0 \times b
      | c = 
}}
{{eqn | l = a < 0
      | o = \implies
      | r = \size a = \paren {-1} \times a + 0 \times b
      | c = 
}}
{{eqn | l = b > 0
      | o = \implies
      | r = \size b = 0 \times a + 1 \times b
      | c = 
}}
{{eqn | l = b < 0
      | o = \implies
      | r = \size b = 0 \times a + \paren {-1} \times b
      | c = 
}}
{{end-eqn}}
As it is not the case that both $a = 0$ and $b = 0$, it must be that at least one of $\size a \in S$ or $\size b \in S$.
Therefore $S \ne \O$.
As $S$ contains only positive integers, $S$ is bounded below by $0$ and therefore $S$ has a smallest element.
Call this smallest element $d$: we have $d = u a + v b$ for some $u, v \in \Z$.
Let $x \in S$.
By the Division Theorem:
: $x = q d + r, 0 \le r < d$
Suppose $d \nmid x$.
Then $x \ne q d$ and so $0 < r$.
But:
{{begin-eqn}}
{{eqn | lo= \exists m, n \in \Z:
      | l = x
      | r = m a + n b
      | c = 
}}
{{eqn | ll= \leadsto
      | l = r
      | r = x - q d
      | c = 
}}
{{eqn | r = \paren {m a + n b} - q \paren {u a + v b}
      | c = 
}}
{{eqn | r = \paren {m - q u} a + \paren {n - q v} b
      | c = 
}}
{{eqn | ll= \leadsto
      | o =
      | r = \paren {r \in S} \land \paren {r < d}
      | c = 
}}
{{end-eqn}}
which contradicts the choice of $d$ as the smallest element of $S$.
Therefore $\forall x \in S: d \divides x$.
In particular:
:$d \divides \size a = 1 \times a + 0 \times b$
:$d \divides \size b = 0 \times a + 1 \times b$
Thus:
: $d \divides a \land d \divides b \implies 1 \le d \le \gcd \set {a, b}$
However, note that as $\gcd \set {a, b}$ also divides $a$ and $b$ (by definition), we have:
{{begin-eqn}}
{{eqn | l = \gcd \set {a, b}
      | o = \divides
      | r = \paren {u a + v b} = d
      | c = Common Divisor Divides Integer Combination
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | o = \divides
      | r = d
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \gcd \set {a, b}
      | o = \le
      | r = d
      | c = 
}}
{{end-eqn}}
Since $d$ is the smallest number in $S$:
:$\gcd \set {a, b} = d = u a + v b$
{{qed}}
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
Consider the Euclidean algorithm in action:
{{begin-eqn}}
{{eqn | l = a
      | r = q_1 b + r_1
      | c = 
}}
{{eqn | l = b
      | r = q_2 r_1 + r_2
      | c = 
}}
{{eqn | l = r_1
      | r = q_3 r_2 + r_3
      | c = 
}}
{{eqn | l = \cdots
      | o = 
      | c = 
}}
{{eqn | l = r_{n - 2}
      | r = q_n r_{n - 1} + r_n
      | c = 
}}
{{eqn | l = r_{n - 1}
      | r = q_{n + 1} r_n + 0
      | c = 
}}
{{end-eqn}}
First it will be established that there exist $x_i, y_i \in \Z$ such that:
:$(1): \quad a x_i + b y_i = r_i$
for $i \in \set{1, 2, \ldots, n - 1}$.
The proof proceeds by induction.
=== Basis for the Induction ===
When $i = 1$, let $x_1 = 1, y_1 = -q_1$.
When $i = 2$, let $x_2 = -q_2, y_2 = 1 + q_1 q_2$.
This is the basis for the induction.
=== Induction Hypothesis ===
Our induction hypothesis is that the integer solutions to $(1)$ have been found for all $i$ such that $i \le k$ where $k < n - 1$.
=== Induction Step ===
We know that:
:$r_{k - 1} = r_k q_{k + 1} + r_{k + 1}$
Thus, by the induction hypothesis:
:$\paren {a x_{k - 1} + b y_{k - 1} } - \paren {a x_k + b y_k} q_{k + 1} = r_{k + 1}$
which can be rewritten as:
:$\paren {x_{k - 1} - x_k q_{k + 1} } a + \paren {y_{k - 1} - y_k q_{k + 1} } b = r_{k + 1}$
Hence we have the following solutions to $(1)$ when $i = k + 1$:
:$x_{k + 1} = x_{k - 1} - x_k q_{k + 1}$
:$y_{k + 1} = y_{k - 1} - y_k q_{k + 1}$
The result follows by the Principle of Mathematical Induction.
{{qed}}
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $J$ be the set of all integer combinations of $a$ and $b$:
:$J = \set {x: x = m a + n b: m, n \in \Z}$
First we show that $J$ is an ideal of $\Z$
Let $\alpha = m_1 a + n_1 b$ and $\beta = m_2 a + n_2 b$, and let $c \in \Z$
Then $\alpha,\beta \in J$ and :
{{begin-eqn}}
{{eqn | l = \alpha + \beta 
      | r = m_1 a + n_1 b + m_2 a + n_2 b 
}}
{{eqn | r = \paren {m_1 + m_2} a + \paren {n_1 + n_2} b
}}
{{eqn | ll= \leadsto
      | l = \alpha + \beta
      | o = \in
      | r = J
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | l = c \alpha
      | r = c \paren {m_1 a + n_1 b}
}}
{{eqn | r = \paren {c m_1} a + \paren {c n_1} b
}}
{{eqn | ll= \leadsto
      | l =  c \alpha
      | o = \in
      | r = J
}}
{{end-eqn}}
Thus $J$ is an integral ideal.
We have that:
{{begin-eqn}}
{{eqn | l = a
      | r = 1 a + 0 b
      | c = 
}}
{{eqn | lo= \land
      | l = b
      | r = 0 a + 1 b
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a, b
      | o = \in
      | r = J
      | c = 
}}
{{end-eqn}}
$a$ and $b$ are not both zero, thus:
:$J \ne \set 0$
By the something {theorem about ideals}:
{{explain|what is "By the something {theorem about ideals}"}}
:$\exists x_0 > 0 : J = x_0 \Z$
:$a \in J \land \set {J = x_0 \Z} \implies x_0 \divides a$
:$b \in J \land \set {J = x_0 \Z} \implies x_0 \divides b$
:$x_0 \divides a \land x_0 \divides b \implies x_0 \in \map D {a, b}$
{{explain|What is $\map D {a, b}$?}}
Furthermore:
:$x_0 \in J \implies \exists r, s \in \Z : x_0 = r a + s b$
Let $x_1 \in \map D {a, b}$.
Then:
{{begin-eqn}}
{{eqn | l = x_1 \in \map D {a, b}
      | o = \leadsto
      | r = x_1 \divides a \land x_1 \divides b
}}
{{eqn | o = \leadsto
      | r = x_1 \divides \paren {r a + s b}
}}
{{eqn | o = \leadsto
      | r = x_1 \vert x_0
}}
{{eqn | o = \leadsto
      | r = \size {x_1} \le \size {x_0} = x_0
}}
{{end-eqn}}
Thus:
:$x_0 = \max \set {\map D {a, b} } = \gcd \set {a, b} = r a + s b$
{{qed}}
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
Let $\gcd \set {a, b} = d$.
Let $\dfrac a d = p$ and $\dfrac b d = q$.
From Integers Divided by GCD are Coprime:
:$\gcd \left\{{p, q}\right\} = 1$
From Integer Combination of Coprime Integers:
:$\exists x, y \in \Z: p x + q y = 1$
The result follows by multiplying both sides by $d$.
{{qed}}
Theorem: Bézout's Identity

Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
:$\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
That is, $\gcd \set {a, b}$ is an integer combination (or linear combination) of $a$ and $b$.
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.

Proof:
We have that Integers are Euclidean Domain, where the Euclidean valuation $\nu$ is defined as:
:$\map \nu x = \size x$
The result follows from Bézout's Identity on Euclidean Domain.
{{qed}}
Theorem: Predecessor Function is Primitive Recursive

The '''predecessor function''' $\operatorname{pred}: \N \to \N$ defined as:
:$\map {\operatorname{pred} } n = \begin{cases}
0 & : n = 0 \\
n-1 & : n > 0
\end{cases}$
is primitive recursive.

Proof:
We can use Primitive Recursion on One Variable to find $g: \N^2 \to \N$ and $h: \N \to \N$ such that:
:$\map h n = \begin{cases}
\map {\operatorname{zero} } n & : n = 0 \\
\map g {n - 1, \map h {n - 1} } & : n > 0 
\end{cases}
$
By setting:
:$\map g {n, m} = \map {\pr^2_1} {n, m}$
we see that setting $h = \operatorname{pred}$ fits the pattern.
We have that the $\pr^2_1$ and $\operatorname{zero}$ functions are basic primitive recursive functions.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
25ojqvqeunyb0o6nbmg3a2595p6sq31
Theorem: Cut-Off Subtraction is Primitive Recursive

The partial subtraction function, defined as:
:<nowiki>$\forall \tuple {n, m} \in \N^2: n \mathop {\dot -} m = \begin{cases}
0 & : n < m \\
n - m & : n \ge m
\end{cases}$</nowiki>
is primitive recursive.

Proof:
We see that:
:<nowiki>$n \mathop {\dot -} \paren {m + 1} = \begin{cases}
0 & : n \mathop {\dot -} m = 0 \\
\paren {n \mathop {\dot -} m} - 1 & : n \mathop {\dot -} m > 0
\end{cases}$</nowiki>
Hence we can define partial subtraction as:
:<nowiki>$n \mathop {\dot -} m = \begin{cases}
n & : m = 0 \\
\operatorname{pred} \paren {n \mathop {\dot -} \paren {m - 1} } & : m > 0
\end{cases}$</nowiki>
This is a definition by primitive recursion from the primitive recursive function $\operatorname{pred}$.
Hence the result.
{{qed}}
Theorem: Maximum Function is Primitive Recursive

The maximum function $\max: \N^2 \to \N$, defined as:
:<nowiki>$\map \max {n, m} = \begin{cases}
m: & n \le m \\
n: & m \le n
\end{cases}$</nowiki>
is primitive recursive.

Proof:
We see that:
:$\map \max {n, m} = \paren {n \ \dot - \ m} + m$
where $\dot -$ denotes the partial subtraction because:
:$(1):\quad n > m \implies \paren {n \ \dot - \ m} + m = n - m + m = n$
:$(2):\quad n < m \implies \paren {n \ \dot - \ m} + m = 0 + m = m$
:$(3):\quad n = m \implies \paren {n \ \dot - \ m} + m = 0 + m = m = n$
Hence we see that $\max$ is obtained by substitution from $\dot -$.
The result follows from Cut-Off Subtraction is Primitive Recursive.
{{qed}}
Category:Max Operation
Category:Primitive Recursive Functions
ayqymxqczfh2i545irq455nhol2z6c6
Theorem: Sum of Maximum and Minimum

For all numbers $a, b$ where $a, b$ in $\N, \Z, \Q$ or $\R$:
:$a + b = \max \set {a, b} + \min \set {a, b}$

Proof:
From the definitions of max and min:
:<nowiki>$\max \set {a, b} = \begin{cases}
b: & a \le b \\
a: & b \le a
\end{cases}$</nowiki>
and
:<nowiki>$\min \set {a, b} = \begin{cases}
a: & a \le b \\
b: & b \le a
\end{cases}$</nowiki>
Let $a < b$.
Then:
:$\max \set {a, b} + \min \set {a, b} = b + a$
Let $a > b$.
Then:
:$\max \set {a, b} + \min \set {a, b} = a + b$
Finally, let $a = b$.
Then:
:$\max \set {a, b} = \min \set {a, b} = a = b$
Hence:
:$\max \set {a, b} + \min \set {a, b} = 2a = 2b = a + b$
{{qed}}
Note that this result does not apply to $a, b \in \C$ as there is no concept of ordering on the complex numbers $\C$.
Category:Algebra
ohabrdl0ay9ed7gvm2duv6uogu6k8ka
Theorem: Minimum Function is Primitive Recursive

The minimum function $\min: \N^2 \to \N$, defined as:
:$\map \min {n, m} = \begin{cases}
n: & n \le m \\
m: & m \le n
\end{cases}$
is primitive recursive.

Proof:
From Sum Less Maximum is Minimum we have that:
:$\map \min {n, m} = n + m  - \map \max {n, m}$.
As $n + m \ge \map \max {n, m}$, we have that:
:$\map \min {n, m} = n + m \ \dot - \ \map \max {n, m}$
Hence we see that $\min$ is obtained by substitution from:
* the primitive recursive function $n \ \dot - \ m$
* the primitive recursive function $\map \max {n, m}$.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
lkwpx0cl2046a1jei83s1v0a3777i76
Theorem: Absolute Difference Function is Primitive Recursive

The '''absolute difference''' function $\operatorname {adf}: \N^2 \to \N$, defined as:
:$\map {\operatorname {adf} } {n, m} = \size {n - m}$
where $\size a$ is defined as the absolute value of $a$, is primitive recursive.

Proof:
We note that:
:$\size {n - m} = \paren {n \mathop {\dot -} m} + \paren {m \mathop {\dot -} n} = \map {\operatorname {add} } {\paren {n \mathop {\dot -} m}, \paren {m \mathop {\dot -} n} }$
Next we note that:
:$m \mathop {\dot -} n = \map {\pr^2_2} {n, m} \mathop {\dot -} \map {\pr^2_1} {n, m}$
where $\pr^2_k$ is the projection function.
Then:
{{begin-eqn}}
{{eqn | l = \map {\operatorname {adf} } {n, m}
      | r = \size {n - m}
      | c = 
}}
{{eqn | r = \paren {n \mathop {\dot -} m} + \paren {m \mathop {\dot -} n}
      | c = 
}}
{{eqn | r = \map {\operatorname {add} } {\paren {n \mathop {\dot -} m}, \paren {m \mathop {\dot -} n} }
      | c = 
}}
{{eqn | r = \map {\operatorname {add} } {\paren {n \mathop {\dot -} m}, \paren {\map {\pr^2_2} {n, m} \mathop {\dot -} \map {\pr^2_1} {n, m} } }
      | c = 
}}
{{end-eqn}}
Hence we see that $\operatorname {adf}$ is obtained by substitution from:
:the primitive recursive function $n \mathop {\dot -} m$
:the primitive recursive function $\map {\operatorname {add} } {n, m}$
:the projection function.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
80gkgdqvx01gp9gkqlv41rm4j7i8s6b
Theorem: Primitive Recursive Set is URM Computable

Every primitive recursive set is URM computable.

Proof:
This follows immediately from:
* a set is primitive recursive if its characteristic function is primitive recursive
* the fact that every Primitive Recursive Function is URM Computable.
{{qed}}
Theorem: Set Containing Only Zero is Primitive Recursive

The subset $\left\{{0}\right\} \subset \N$ is primitive recursive.

Proof:
We note that:
:$1 \mathop {\dot -} n = \begin{cases}
1 & : n = 0 \\
0 & : n > 0
\end{cases}$
and so the characteristic function $\chi_{\left\{{0}\right\}}$ is given by $\chi_{\left\{{0}\right\}} \left({n}\right) = 1 \mathop {\dot -} n$.
So $\chi_{\left\{{0}\right\}}$ is obtained by substitution from the primitive recursive function $1 \mathop {\dot -} n$ using constants, which are primitive recursive.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
89z90wvo7yu203urczj8d1365qzgprg
Theorem: Set of Non-Zero Natural Numbers is Primitive Recursive

Let $\N^*$ be defined as $\N^* = \N \setminus \set 0$.
The subset $\N^* \subset \N$ is primitive recursive.

Proof:
We have that the characteristic function $\chi_{\set 0}$ of $\set 0$ is primitive recursive.
We note that:
:If $n = 0$ then $\map {\chi_{\set 0} } n = 1$ therefore $\map {\chi_{\set 0} } {\map {\chi_{\set 0} } n} = 0$.
:If $n > 0$ then $\map {\chi_{\set 0} } n = 0$ therefore $\map {\chi_{\set 0} } {\map {\chi_{\set 0} } n} = 1$.
Thus $\map {\chi_{\set 0} } {\map {\chi_{\set 0} } n} = \map {\chi_{\N^*} } n$.
So $\chi_{\N^*}$ is obtained by substitution from the primitive recursive function $\chi_{\set 0}$.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
081mlesy45jics6p73g232vrudxn6fj
Theorem: Signum Function is Primitive Recursive

Let $\sgn: \N \to \N$ be defined as the signum function.
Then $\sgn$ is primitive recursive.

Proof:
By Signum Function on Natural Numbers as Characteristic Function, $\map \sgn n = \chi_{\N^*}$, where $\N^* = \N \setminus \set 0$.
By Set of Non-Zero Natural Numbers is Primitive Recursive, $\N^*$ is primitive recursive.
Thus $\sgn$ is primitive recursive by definition of Primitive Recursive Set.
{{qed}}
Category:Signum Function
Category:Primitive Recursive Functions
f96z01t8er7bfpqn1zn6vvj3m0hqfvd
Theorem: Set of Natural Numbers is Primitive Recursive

The set of natural numbers $\N$ is primitive recursive.

Proof:
The characteristic function $\chi_\N: \N \to \N$ is defined as:
:$\forall n \in \N: \chi_\N \left({n}\right) = 1$.
So:
: $\chi_\N \left({n}\right) = f^1_1 \left({n}\right)$
The constant function $f^1_1$ is primitive recursive.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
Category:Natural Numbers
10vvk2mb2nm8d17tlbp91j9l7rcdjpc
Theorem: Complement of Primitive Recursive Set

Let $S \subseteq \N$ be primitive recursive.
Then its relative complement $\N \setminus S$ of $S$ in $\N$ is primitive recursive.

Proof:
By definition, we have that the characteristic function $\map {\chi_{\N \mathop \setminus S} } n = 1$ {{iff}} $\map {\chi_S} n = 0$.
So:
:$\map {\chi_{\N \mathop \setminus S} } n = \map {\chi_{\set 0} } {\map {\chi_S} n}$
Thus $\chi_{\N \mathop \setminus S}$ is obtained by substitution from $\chi_{\set 0}$ and $\chi_S$.
The result follows from Set Containing Only Zero is Primitive Recursive.
{{qed}}
Category:Primitive Recursive Functions
Category:Relative Complement
k85v4ymy7xbjsbotm0x3acr35d0c5fo
Theorem: Intersection of Primitive Recursive Sets

Let $A, B \subseteq \N$ be subsets of the set of natural numbers $\N$.
Let $A$ and $B$ both be primitive recursive.
Then $A \cap B$, the intersection of $A$ and $B$, is primitive recursive.

Proof:
$A$ and $B$ are primitive recursive, therefore so are their [Definition:Characteristic Function of Set|characteristic functions]] $\chi_A$ and $\chi_B$.
Let $n \in \N$ be a natural number.
From Characteristic Function of Intersection: Variant 1:
:$\chi_{A \cap B} \left({n}\right) = \chi_A \left({n}\right) \times \chi_B \left({n}\right)$
So:
: $\chi_{A \cap B} \left({n}\right) = \operatorname{mult} \left({\chi_A \left({n}\right), \chi_B \left({n}\right)}\right)$
Thus $A \cap B$ is defined by substitution from the primitive recursive functions $\operatorname{mult}$, $\chi_A$ and $\chi_B$.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
Category:Set Intersection
f9dru7looqz6dy9n09w241yqb5xr2du
Theorem: Union of Primitive Recursive Sets

Let $A, B \subseteq \N$ be subsets of the set of natural numbers $\N$.
Let $A$ and $B$ both be primitive recursive.
Then $A \cup B$, the union of $A$ and $B$, is primitive recursive.

Proof:
$A$ and $B$ are primitive recursive, therefore so are their characteristic functions $\chi_A$ and $\chi_B$.
Let $n \in \N$ be a natural number.
Then $n \in A \cup B \iff \map {\chi_A} n + \map {\chi_B} n > 0$.
So:
{{begin-eqn}}
{{eqn | l = \map {\chi_{A \cup B} } n
      | r = \map \sgn {\map {\chi_A} n + \map {\chi_B} n}
      | c = Signum Function is Primitive Recursive
}}
{{eqn | r = \map \sgn {\map \Add {\map {\chi_A} n, \map {\chi_B} n} }
      | c = Addition is Primitive Recursive
}}
{{end-eqn}}
Thus $A \cup B$ is defined by substitution from the primitive recursive functions $\sgn$, $\Add$, $\chi_A$ and $\chi_B$.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
Category:Set Union
l8ux1fck6t4xft0thv9m8qfriy9y7ia
Theorem: Set of Even Numbers is Primitive Recursive

Let $E \subseteq \N$ be the set of all even natural numbers.
Then $E$ is primitive recursive.

Proof:
If $n \in E$ then $n$ is of the form $n = 2 k$ where $k \in \N$.
We have that:
* if the characteristic function $\map {\chi_E} n = 1$ then $\map {\chi_E} {n + 1} = 0$.
* if the characteristic function $\map {\chi_E} n = 0$ then $\map {\chi_E} {n + 1} = 1$.
So $\chi_E$ can be defined by:
:<nowiki>$\map {\chi_E} n = \begin{cases}
1 & : n = 0 \\
\map {\overline \sgn} {\map {\chi_E} {n-1} } & : n > 0
\end{cases}$</nowiki>
So $\chi_E$ is obtained by primitive recursion from the constant function $1$ and the signum function.
The result follows from Constant Function is Primitive Recursive and the Signum Function is Primitive Recursive.
{{qed}}
Category:Primitive Recursive Functions
cvhzjrhh3ylgcscz1hjosd787elbu8i
Theorem: Primitive Recursive Relation is URM Computable

Every primitive recursive relation is URM computable.

Proof:
This follows immediately from:
* a relation is primitive recursive if its characteristic function is a primitive recursive
* the fact that every Primitive Recursive Function is URM Computable.
{{qed}}
Theorem: Equality Relation is Primitive Recursive

The relation $\operatorname{eq} \subseteq \N^2$, defined as:
:$\map {\operatorname {eq} } {n, m} \iff n = m$
is primitive recursive.

Proof:
We note that:
:$n = m \iff \size {n - m} = 0$
:$n \ne m \iff \size {n - m} > 0$
So it can be seen that the characteristic function of $\operatorname{eq}$ is given by:
:$\map {\chi_{\operatorname {eq} } } {n, m} = \overline {\map \sgn {\map {\operatorname {adf} } {n, m} } }$.
So $\map {\chi_{\operatorname {eq} } } {n, m}$ is defined by substitution from:
:the primitive recursive function $\overline \sgn$
:the primitive recursive function $\operatorname {adf}$.
Thus $\chi_{\operatorname {eq} }$ is primitive recursive.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
3mhxju2w14zy60wrzqxyz4rmrvauwcf
Theorem: Sylow Subgroup is Hall Subgroup

Let $G$ be a group.
Let $H$ be a Sylow $p$-subgroup of $G$.
Then $H$ is a Hall subgroup of $G$.

Proof:
Let $p$ be prime.
Let $G$ be a finite group such that $\order G = k p^n$ where $p \nmid k$.
By definition, a Sylow $p$-subgroup $H$ of $G$ is a subgroup of $G$ of order $p^n$.
By Lagrange's Theorem, the index of $H$ in $G$ is given by:
:$\index G H = \dfrac {\order G} {\order H}$
So in this case:
:$\index G H = \dfrac {k p^n} {p^n} = k$
As $p \nmid k$ it follows from Prime not Divisor implies Coprime that $k \perp p$.
The result follows from the definition of Hall subgroup.
{{qed}}
Category:Sylow p-Subgroups
Category:Hall Subgroups
m6tcippqglz4o46bqw2svf79j7noq7g