1

Is it true that $\forall n \in \mathbb Z^+ \land \forall i \in \mathbb Z \land i \geqslant 0: n^i \in \mathbb Z^+$?

The reason I ask is because this would allow you to create a countably infinite set $$\forall k \in \mathbb Z \land k \geqslant 0, \{a_k \in \mathbb Z^+ : a_k = 10^k\}$$

This set would contain elements of the form $\{1, 10, 100, 1000, \ldots\}$, i.e. each element $a_k$ of the set would be a $1$ followed by $k$ zeros, up to an infinite amount of zeros. But a natural number cannot have an infinite number of digits, so that would seem to say that the natural numbers are not closed under exponentiation. Am I getting something wrong here?

keluj
  • 13
  • 3
    You could just say, "If $n$ is a positive integer and $i$ is a nonnegative integer then $n^i$ is a positive integer." Clearly this is true. – littleO Feb 12 '21 at 22:52
  • 1
    Please just work with the maths / logic, and don't impose your (potentially wrong) intuitions onto it. We never required k to be infinite. We simply required that for every positive integer m, there exists k such that k is bigger than m. – Benjamin Wang Feb 12 '21 at 22:53
  • 1
    This is like saying that since the natural numbers are infinite, infinity must be a natural numbers... it's not true. The only thing we can say is that for every natural number there is a natural number bigger than it – Riemann'sPointyNose Feb 12 '21 at 23:36

2 Answers2

6

They are closed under exponentiation, the contradiction you gave isn't a real contradiction.

When you say that there can be "up to an infinite amount" of zeroes, that just means that there is no upper bound on the number of trailing zeroes. However any specific number you choose from that set will have some finite number of trailing zeroes.

It's similar to how the natural numbers "go to infinity", even though every natural number you choose will have to be finite.

Karan Elangovan
  • 893
  • 4
  • 9
  • OK, that makes sense. Since the set contains all of the natural numbers in the form ${1, 10, 100, 1000, \ldots }$ is it then possible to sum all of the numbers in the set, being a sum of natural numbers, to get a natural number in the form $1111\cdots$? If it is possible, this number would have an infinite number of digits. If it is not possible, being that the result would just be a natural number since it is a sum of natural numbers and natural numbers are closed under addition, what is the reasoning that prevents it? – keluj Feb 13 '21 at 06:18
  • No, it is not possible. The natural numbers are closed under addition, but only for finite addition. Addition is defined as a binary operation between two numbers, it’s associativity means it makes sense to speak of sums of finite sets. The sum of an infinite set makes no sense under the usual definition of addition (under which we can say the natural numbers are closed) - under the standard definition for infinite sums this sum would diverge. – Karan Elangovan Feb 13 '21 at 10:49
0

Exponentiation is closed on the Natural Numbers. Here’s a formal proof. In this answer I will consider N to be the set of non-negative integers including 0. (Forgive my bad notation, this is just a draft.)

You may recall the recursive definition of exponentiation of natural numbers.

for all a, b in N,

a^b
    := 1        if b = 0
    := a^k * a  if b = k + 1 for some k in N

For example,

a^3
    = a^2 * a
    = (a^1 * a) * a
    = ((a^0 * a) * a) * a
    = 1 * a * a * a

This even works for when a = 0.

0 ^ 5 = 1 * 0 * 0 * 0 * 0 * 0 = 0
0 ^ 0 = 1 (by definition)

Since we can assume multiplication is closed (try a proof of that yourself), and every definition of exponentiation uses multiplication, exponentiation must be closed. Formally, we can prove this via induction.

Given a, b in N, let a = b = 0 for the base case. By the definition above, 0^0 = 1 in N.

For the inductive hypothesis on b, assume a^b in N. Then a^(b+1) = a^b * a by definition, and since a^b in N, we also have that a^b * a in N as well.

Note that it’s not necessary to prove by induction on a because the base and inductive steps of this proof cover all possible values of a.

References:

chharvey
  • 2,612