Bijection and Natural elements

Question

I'm trying to establish that the set of $L_{PA}$ terms and $p$ an element of the $N[x_1,\ldots,x_n]$ where $N$ = naturals, for some $n$ in the Naturals are in a bijection.

Well, the $L_{PA}$ terms really contain the class of successors, addition and zero.

Your question is really hard to understand. What does $N[x_1,\ldots,x_n]$ mean? Is $L_{PA}$ the language of Peano arithmetic? — MJD, Mar 13 '13 at 17:05
Here is a tutorial about formatting mathematics on this site. — MJD, Mar 13 '13 at 17:07
N[x] is the set of polynomials in x with coefficients in N, the Naturals — mary, Mar 13 '13 at 21:35
Is it enough to show that both sets are countable, or are you looking for a bijection with some special property? — MJD, Mar 13 '13 at 21:38
And are you going to tell us what the special property is, or is it a secret? — MJD, Mar 14 '13 at 02:55
Its not a secret; the special property is that LPA maps into some polynomials with natural coefficients. So I am not concerned on cardinality, but rather would like a mapping — mary, Mar 14 '13 at 04:53
@mary Whenever you are looking for a bijection between sets, you should be concerned about cardinality! They amount to the same thing. — Alex Kruckman, Mar 22 '13 at 04:20

score 2 · Answer 1 · answered Mar 22 '13 at 04:16

Let's recall the definition of a term in first-order logic.

Every constant symbol is a term.
Every variable (from a countable supply $x_1,x_2,x_3\dots$) is a term.
If $f$ is an $n$-ary function symbol and $t_1,\dots,t_n$ are terms, then $f(t_1,\dots,t_n)$ is a term.

Our language $L_{PA}$ has a single constant symbol $0$, a unary function symbol $S$, and two binary function symbols, $+$ and $*$. Sometimes $L_{PA}$ also comes with a binary relation symbol $<$, but that isn't relevant to us, because we're just thinking about terms.

Here are some examples of $L_{PA}$-terms:

$0$
$S(S(S(0))) + S(0)$
$x_5$
$x_1*(x_1*x_1) + ((S(S(0))*x_2)*(x_3+S(x_1)))$

Now your question asks to show that the set of $L_{PA}$-terms is in bijection with the set of polynomials with coefficients in $\mathbb{N}$ and variables from $x_1,x_2,x_3,\dots$ There are two reasonable ways to interpret this. I hope the explanation clarifies some of the comments your question received.

Literally, you just want a bijection between the sets $\{t\,|\,t\text{ is an }L_{PA}\text{-term}\}$ and $\mathbb{N}[x_1,x_2,\dots]$. A bijection between two sets is just a one-to-one correspondence between the two sets. Now given any two countable sets, there is a bijection between them. Why? Because to say $X$ is countable means that there is a one-to-one correspondence $X\cong \mathbb{N}$. So if $X$ and $Y$ are both countable, then $X\cong\mathbb{N}\cong Y$, that is, they are both in one-to-one correspondence with $\mathbb{N}$, so they are in one-to-one correspondence with each other.

Now the two sets above ($\{t\,|\,t\text{ is an }L_{PA}\text{-term}\}$ and $\mathbb{N}[x_1,x_2,\dots]$) are both countable, so there is a bijection $f:\{t\,|\,t\text{ is an }L_{PA}\text{-term}\}\rightarrow \mathbb{N}[x_1,x_2,\dots]$. But we haven't actually said anything about what the function does, and it probably isn't very interesting - given a term $t$, $f(t)$ will probably be a polynomial that's not related to $t$ in any special way.

But there's a better way to relate $L_{PA}$-terms to polynomials. When we look at an $L_{PA}$-term, we can "simplify" it, just using the usual rules of arithmetic. For example, the four example terms I gave above simplify to $0$, $4$, $x_5$, and $x_1^3 + 2x_2x_3 + 2x_1x_2 + 2x_2$. By simplification we can turn any $L_{PA}$-term into a polynomial in $\mathbb{N}[x_1,x_2,\dots]$: replace all instances of $S$ with $+1$, and expand until you get a polynomial. Conversely, every polynomial in $\mathbb{N}[x_1,x_2,\dots]$ can be expressed as an $L_{PA}$-term. In this way, $L_{PA}$-terms are "the same as" polynomials.

But this doesn't give a bijection between the set of $L_{PA}$-terms and the set of polynomials. This is because lots of $L_{PA}$-terms can simplify to the same polynomial. For example, $S(S(x_1)) + S(x_1)$ and $S(S(0))*x_1 + S(S(S(0)))$ both simplify to $2x_1 + 3$.

But $PA$ proves all the usual properties of arithmetic: the associative and commutative properties of addition and multiplication, the distributive property, etc. So if we can simplify two terms to the same polynomial, $PA$ will also prove that they are equal. That is, $PA\vdash S(S(x_1)) + S(x_1) = S(S(0))*x_1 + S(S(S(0)))$.

We say that two $L_{PA}$-terms $t_1$ and $t_2$ are equivalent, $t_1\equiv t_2$, if $PA$ proves that they are equal: $PA\vdash t_1 = t_2$. This relation $\equiv$ is an equivalence relation on the set of $L_{PA}$-terms, and each equivalence class corresponds to a polynomial in $\mathbb{N}[x_1,x_2,\dots]$. So we can say that we have exhibited a bijection between the set of polynomials with coefficients in $\mathbb{N}$ and the set of $L_{PA}$-terms modulo equivalence.

Bijection and Natural elements

1 Answers1