Sum of 2ᵏ, or of k/(2ᵏ) for k∈ℕ∩[1,n]

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} 2+2^2+2^3+\cdots +2^n=2^{n+1}-2 \end{aligned}$$

Proof by Mathematical Induction:

We are asked to prove that for every natural number $n$,

$$ 2 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 2 $$

---

Step 1: Base Case

Let’s check the base case $n = 1$.

Left-hand side (LHS):

$$ 2 = 2 $$

Right-hand side (RHS):

$$ 2^{1+1} - 2 = 2^2 - 2 = 4 - 2 = 2 $$

✅ The base case holds.

---

Step 2: Inductive Hypothesis

Assume that the formula holds for some natural number $k$, i.e.,

$$ 2 + 2^2 + 2^3 + \cdots + 2^k = 2^{k+1} - 2 $$

---

Step 3: Inductive Step

We need to prove that the formula holds for $k + 1$, i.e.,

$$ 2 + 2^2 + 2^3 + \cdots + 2^k + 2^{k+1} = 2^{(k+1)+1} - 2 $$

Start from the left-hand side for $k+1$:

$$ \left(2 + 2^2 + 2^3 + \cdots + 2^k\right) + 2^{k+1} $$

Apply the inductive hypothesis to the first part:

$$ (2^{k+1} - 2) + 2^{k+1} $$

Combine like terms:

$$ 2^{k+1} + 2^{k+1} - 2 = 2 \cdot 2^{k+1} - 2 $$

Simplify the exponent:

$$ 2^{k+2} - 2 $$

Check the right-hand side formula for $k+1$:

$$ 2^{(k+1)+1} - 2 = 2^{k+2} - 2 $$

✅ Matches exactly.

---

Conclusion:

By the principle of mathematical induction, the formula

$$ 2 + 2^2 + 2^3 + \cdots + 2^n = 2^{n+1} - 2 $$

holds for all natural numbers $n$.

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} \dfrac{1}{2}+\dfrac{2}{2^2}+\dfrac{3}{2^3}+\cdots +\dfrac{n}{2^n}=2-\dfrac{n+2}{2^n} \end{aligned}$$

Proof by Mathematical Induction:

We are asked to prove that for every natural number $n$,

$$ \frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \cdots + \frac{n}{2^n} = 2 - \frac{n+2}{2^n} $$

---

Step 1: Base Case

Check the base case $n = 1$.

Left-hand side (LHS):

$$ \frac{1}{2} = 0.5 $$

Right-hand side (RHS):

$$ 2 - \frac{1+2}{2^1} = 2 - \frac{3}{2} = 2 - 1.5 = 0.5 $$

✅ The base case holds.

---

Step 2: Inductive Hypothesis

Assume that the formula holds for some natural number $k$, i.e.,

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k} = 2 - \frac{k+2}{2^k} $$

---

Step 3: Inductive Step

Prove that the formula holds for $k + 1$, i.e.,

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k}{2^k} + \frac{k+1}{2^{k+1}} = 2 - \frac{(k+1) + 2}{2^{k+1}} $$

Start from the left-hand side for $k+1$:

Apply the inductive hypothesis to the first part:

$$ \left(2 - \frac{k+2}{2^k}\right) + \frac{k+1}{2^{k+1}} $$

Express $\frac{k+1}{2^{k+1}}$ with denominator $2^{k}$ to combine terms:

$$ 2 - \frac{k+2}{2^k} + \frac{k+1}{2^{k+1}} $$

Express $\frac{k+1}{2^{k+1}}$ as:

$$ \frac{k+1}{2 \cdot 2^{k}} = \frac{k+1}{2^{k} \cdot 2} = \frac{k+1}{2^{k+1}} $$

It doesn't directly combine, so use a common denominator $2^{k+1}$ for the fractions.

Express $2$ with denominator $2^{k+1}$:

$$ 2 = \frac{2 \cdot 2^{k+1}}{2^{k+1}} = \frac{2^{k+2}}{2^{k+1}} $$

Express $\frac{k+2}{2^k}$ with denominator $2^{k+1}$:

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

Now write the entire left-hand side over denominator $2^{k+1}$:

$$ \frac{2^{k+2} - 2(k+2) + (k+1)}{2^{k+1}} $$

Compute the numerator:

$$ 2^{k+2} - 2(k+2) + (k+1) $$

Compute step by step:

• $2^{k+2}$ stays as is.
• $-2(k+2) = -2k - 4$
• $+(k+1)$

Sum:

$$ 2^{k+2} - 2k - 4 + k +1 = 2^{k+2} - k -3 $$

The numerator becomes:

$$ 2^{k+2} - (k +3) $$

Now express the right-hand side formula for $k+1$:

Check if it matches:

$$ 2 - \frac{(k+1)+2}{2^{k+1}} = 2 - \frac{k+3}{2^{k+1}} = \frac{2\cdot 2^{k+1}}{2^{k+1}} - \frac{k+3}{2^{k+1}} $$

Compute numerator:

$$ 2 \cdot 2^{k+1} = 2^{k+2} $$

So numerator:

$$ 2^{k+2} - (k+3) $$

Indeed, matches exactly.

---

Conclusion:

By the principle of mathematical induction, the formula

$$ \frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{n}{2^n} = 2 - \frac{n+2}{2^n} $$

holds for every natural number $n$.

Sum of products of consecutive naturals, and sum of the reciprocals of such products

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} 1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n\cdot (n+1)=\dfrac{n(n+1)(n+2)}{3} \end{aligned}$$

Let's prove the statement by mathematical induction.

---

Statement:

For every natural number $n \geq 1$:

$$ 1\cdot 2 + 2\cdot 3 + 3\cdot 4 + \cdots + n\cdot (n+1) = \frac{n(n+1)(n+2)}{3} $$

---

Step 1: Base Case

Test for $n = 1$.

Left-hand side (LHS):

$$ 1\cdot 2 = 2 $$

Right-hand side (RHS):

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

✅ The base case holds.

---

Step 2: Inductive Hypothesis

Assume the formula holds for $n = k$, i.e.,

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

---

Step 3: Inductive Step

Show it holds for $n = k + 1$.

Left-hand side for $n = k + 1$:

$$ \left(1\cdot 2 + 2\cdot 3 + \cdots + k\cdot (k+1)\right) + (k+1)(k+2) $$

Using the inductive hypothesis:

$$ \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) $$

Factor out $(k+1)(k+2)$:

$$ (k+1)(k+2)\left( \frac{k}{3} + 1 \right) $$

Combine the terms inside the parentheses:

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

Rearrange:

$$ \frac{(k+1)(k+2)(k+3)}{3} $$

This matches the RHS for $n = k+1$.

---

✅ Conclusion:

By mathematical induction, the formula holds for all natural numbers $n \geq 1$:

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

Prove, using induction, that for every natural number n: $$\displaystyle \begin{aligned} \dfrac{1}{1\cdot 2}+\dfrac{1}{2\cdot 3}+\cdots +\dfrac{1}{n\cdot (n+1)}=\dfrac{n}{n+1} \end{aligned}$$

Let's prove this formula using mathematical induction.

---

Statement:

For every natural number $n \geq 1$:

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

---

Step 1: Base Case

Test for $n = 1$.

Left-hand side (LHS):

$$ \frac{1}{1\cdot 2} = \frac{1}{2} $$

Right-hand side (RHS):

$$ \frac{1}{1+1} = \frac{1}{2} $$

✅ The base case holds.

---

Step 2: Inductive Hypothesis

Assume the formula holds for $n = k$, i.e.,

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

---

Step 3: Inductive Step

Show it holds for $n = k + 1$.

Left-hand side for $n = k + 1$:

$$ \left(\frac{1}{1\cdot 2} + \cdots + \frac{1}{k\cdot (k+1)}\right) + \frac{1}{(k+1)(k+2)} $$

Apply the inductive hypothesis:

$$ \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} $$

Get a common denominator:

$$ \frac{k(k+2) + 1}{(k+1)(k+2)} $$

Compute the numerator:

$$ k(k+2) + 1 = k^2 + 2k + 1 = (k+1)^2 $$

So the sum becomes:

$$ \frac{(k+1)^2}{(k+1)(k+2)} $$

Cancel one $(k+1)$ from numerator and denominator:

$$ \frac{k+1}{k+2} $$

This matches the RHS for $n = k + 1$:

$$ \frac{k+1}{(k+1)+1} = \frac{k+1}{k+2} $$

---

✅ Conclusion:

By mathematical induction, the formula holds for all natural numbers $n \geq 1$:

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

Proof that all and only perfect squares have an odd number of different factors

Show that a natural number has an odd number of different factors if, and only if, it is a perfect square.

Proof: A natural number has an odd number of different factors if and only if it is a perfect square.

---

Step 1: Prime Factorization Approach

Let’s express a natural number $n$ in terms of its prime factorization:

$$ n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} $$

where $p_1, p_2, \dots, p_k$ are distinct prime numbers and $a_1, a_2, \dots, a_k$ are non-negative integers.

---

Step 2: Total Number of Factors Formula

The total number of positive factors of $n$ is given by the formula:

$$ \text{Number of factors} = (a_1 + 1)(a_2 + 1) \dots (a_k + 1) $$

---

Step 3: When is the Number of Factors Odd?

The product of numbers $(a_1 + 1)(a_2 + 1) \dots (a_k + 1)$ is odd if and only if each $(a_i + 1)$ is odd, because the product of odd numbers is odd, and if any factor is even, the whole product is even.

A number $(a_i + 1)$ is odd if and only if $a_i$ is even (since an even number plus 1 is odd).

---

Step 4: Link to Perfect Squares

• If all exponents $a_i$ are even, then the number is a perfect square, because:

$$ n = (p_1^{a_1/2} p_2^{a_2/2} \dots p_k^{a_k/2})^2 $$

• Conversely, if the number is a perfect square, then all exponents in its prime factorization must be even.

---

Step 5: Conclusion

• A natural number has an odd number of positive divisors if and only if it is a perfect square.

✔️ Q.E.D.

Why is the number of factors $(a_1 + 1)(a_2 + 1) \dots (a_k + 1)$?

Excellent question! Let’s break down why the number of factors of a natural number is given by:

$$ (a_1 + 1)(a_2 + 1) \dots (a_k + 1) $$

✅ Reasoning:

Suppose a natural number $n$ has prime factorization:

$$ n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} $$

🔍 How do we form a factor of $n$?

A factor of $n$ is a number that divides $n$ exactly. To construct a factor, you can choose:

• Any exponent for $p_1$ between $0$ and $a_1$ (inclusive),
• Any exponent for $p_2$ between $0$ and $a_2$ (inclusive),
• ...
• Any exponent for $p_k$ between $0$ and $a_k$ (inclusive).

🔢 Counting the choices:

• For prime $p_1$, there are $(a_1 + 1)$ choices (exponents $0, 1, 2, \dots, a_1$).
• For prime $p_2$, there are $(a_2 + 1)$ choices.
• ...
• For prime $p_k$, there are $(a_k + 1)$ choices.

🔗 Total number of distinct factors:

Each choice of exponent is independent, so the total number of different factors is the product:

$$ (a_1 + 1)(a_2 + 1) \dots (a_k + 1) $$

---

📜 Example to illustrate:

Let’s take $n = 12$.

• Prime factorization: $12 = 2^2 \times 3^1$.
• Number of factors:

$$ (2+1)(1+1) = 3 \times 2 = 6 $$

• The factors are: $1, 2, 3, 4, 6, 12$ — 6 factors.

✔️ The formula holds perfectly.

---

🚩 Conclusion:

The formula works because forming a divisor is about independently choosing each exponent from its possible range $0$ to $a_i$ for every prime factor.

Would you like me to visualize this with a tree diagram or table?

Proof that, ∀n∈ℕ, there are n consecutive composite numbers

Prove that, for every natural number n, there are n consecutive composite numbers.

Proof: For every natural number $n$, there are $n$ consecutive composite numbers.

---

Step 1: Construct the sequence.

Consider the number:

$$ N = (n+1)! $$

where $(n+1)!$ is the factorial of $n+1$, meaning:

$$ (n+1)! = (n+1) \cdot n \cdot (n-1) \cdots 2 \cdot 1 $$

Step 2: Build the sequence of $n$ consecutive numbers:

$$ N + 2, N + 3, N + 4, \dots, N + (n+1) $$

This is a sequence of $n$ consecutive numbers (from $N + 2$ to $N + (n+1)$).

Step 3: Prove each number is composite.

Consider any number in the sequence:

$$ N + k \quad \text{where} \quad k = 2, 3, 4, \dots, n+1 $$

Note that $(n+1)!$ is divisible by $k$ because $k \leq n+1$ and the factorial contains every integer up to $n+1$ as factors.

Therefore:

$$ N + k = (n+1)! + k $$

is divisible by $k$ (since $(n+1)!$ is divisible by $k$).

Check whether this number is composite:

• It is greater than $k$ (because $(n+1)! \geq (n+1) \cdot n \cdot \dots \cdot 2 \cdot 1$, which is obviously larger than $k$ for all $n \geq 1$).
• It has $k$ as a divisor other than 1 and itself.

Thus, every number in the sequence is composite.

Step 4: Conclusion.

For every natural number $n$, there exists a sequence of $n$ consecutive composite numbers — specifically the numbers:

$$ (n+1)! + 2, (n+1)! + 3, \dots, (n+1)! + (n+1) $$

This proves the statement. $\blacksquare$

Bertrand postulate proof sketch

Prove that ∀n∈ℕ(n>1⟹∃p∈ℙ(n<p<2n)).

Below is a classical proof of

$$ \forall n\in\Bbb N,\;n>1\;\Longrightarrow\;\exists\,p\in\Bbb P\text{ with }n<p<2n, $$

first conjectured by Bertrand in 1845 and proved (independently) by Chebyshev in 1852. It is often called Bertrand’s postulate.

---

1. Chebyshev’s θ-function

Define

$$ \theta(x)\;=\;\sum_{\substack{p\le x\\p\;\text{prime}}}\ln p. $$

Chebyshev showed by completely elementary means (bounding factorials via products) that there are absolute constants $A,B>0$ such that for all $x\ge2$,

$$ A\,x\;\le\;\theta(x)\;\le\;B\,x. $$

One may take for instance

$$ 0.92\,x\;\le\;\theta(x)\;\le\;1.11\,x, $$

for every $x\ge2$. (The proof is a straightforward—but somewhat lengthy—analysis of the prime‐power factors of $n!$.)

---

2. From θ to “a prime in $(n,2n)$”

Observe that

$$ \theta(2n)\;-\;\theta(n)\;=\;\sum_{\,n< p\le 2n}\ln p. $$

If there were no prime in the open interval $(n,2n]$, then $\theta(2n)-\theta(n)=0$. But by Chebyshev’s bounds,

$$ \theta(2n)-\theta(n)\;\ge\;0.92\,(2n)\;-\;1.11\,n \;=\;(1.84-1.11)\,n \;=\;0.73\,n \;>\;0 \quad(\forall n>1). $$

Hence

$$ \sum_{\,n<p\le 2n}\ln p>0, $$

so there must be at least one prime $p\in(n,2n]$. This completes the proof.∎

---

Historical remarks

• Chebyshev’s original 1852 proof bounds factorials $\;n!\approx\sqrt{2\pi n}\,(n/e)^n$ from above and below elementarily, then translates those bounds into $\;A\,x\le\theta(x)\le B\,x$.
• In 1932, Erdős found a shorter “combinatorial” proof using properties of the central binomial coefficient $\binom{2n}{n}$.
• The statement is often referred to as Bertrand’s postulate, though it is now a theorem.

Proof that ∀n∈ℕ(n>2⟹∃p∈ℙ(n<p<n!))

Prove that, for every natural number n greater than 2, there is a prime number between n and n!.

Proof: For every natural number $n > 2$, there is a prime number between $n$ and $n!$.

---

Step 1: Understand the problem.

We are asked to show that for any integer $n > 2$, there exists at least one prime $p$ such that:

$$ n < p < n! $$

---

Step 2: Use a classical approach based on divisor arguments.

Consider the number:

$$ N = n! - 1 $$

Let's analyze the prime factors of $N$.

---

Step 3: Key observation.

• For any integer $k$ with $2 \leq k \leq n$, $k$ divides $n!$ (by the definition of factorial).
• But $k$ does not divide $n! - 1$ because:

$$ n! \equiv 0 \pmod{k} \implies n! - 1 \equiv -1 \not\equiv 0 \pmod{k} $$

This means none of the integers $2, 3, \dots, n$ divides $N = n! - 1$.

---

Step 4: Consequence.

• Any prime divisor of $N$ must be greater than $n$.

---

Step 5: Conclusion.

• $N = n! - 1$ is either prime itself (in which case it's a prime greater than $n$) or composite.
• If it's composite, it must have a prime factor greater than $n$, since none of the primes $\leq n$ divide it.

Thus, there exists a prime $p > n$ such that $p$ divides $n! - 1$.

Since $n! - 1 < n!$, this prime $p$ satisfies:

$$ n < p < n! $$

---

✅ Therefore, for every integer $n > 2$, there is a prime number between $n$ and $n!$.

---

This proof uses an idea similar to Euclid's proof of the infinitude of primes but applied to the interval $(n, n!)$.

Proof that 3,5,7 are the only 3 primes separated by 2

Suppose that p, p + 2, and p + 4 are prime numbers. Prove that p = 3.

Proof that if $p$, $p + 2$, and $p + 4$ are all prime numbers, then $p = 3$.

---

Step 1: Understand the problem

We are told that $p$, $p+2$, and $p+4$ are all prime numbers, and asked to prove that the only possible value for $p$ is $3$.

---

Step 2: Consider modulo 3 behavior

Any integer is congruent to one of 0, 1, or 2 modulo 3.

Check how this applies to the numbers $p$, $p+2$, and $p+4$.

---

Step 3: Check modulo 3 cases

• If $p \equiv 0 \pmod{3}$, then $p = 3$ is the only prime satisfying this (since 3 is the only prime divisible by 3).

Test it:

• $p = 3$
• $p+2 = 5$ (prime)
• $p+4 = 7$ (prime)

✔️ Works.

Check whether any other options exist.

---

• If $p \equiv 1 \pmod{3}$, then

• $p+2 \equiv 3 \equiv 0 \pmod{3}$

This means $p+2$ is divisible by 3.

The only prime divisible by 3 is 3 itself, but $p+2 > p \geq 1$, so $p+2 > 3$, and the only possibility is if $p+2=3$, leading to $p=1$, but 1 is not prime.

So in this case, $p+2$ would be composite for any $p \equiv 1 \pmod{3}$ with $p > 3$.

Contradicts the assumption that $p+2$ is prime.

---

• If $p \equiv 2 \pmod{3}$, then

• $p+4 \equiv (2+4) \equiv 6 \equiv 0 \pmod{3}$

This means $p+4$ is divisible by 3.

Again, unless $p+4=3$ (impossible because $p+4 > p \geq 2$), this means $p+4$ is composite.

Contradicts the assumption that $p+4$ is prime.

---

Step 4: Conclusion

The only possible value where neither $p+2$ nor $p+4$ are divisible by 3 is when $p\equiv 0\pmod{3}$, i.e., $p=3$.

Test:

• $3, 5, 7$ — all prime ✔️

No other $p$ works.

Therefore, the only possible prime number $p$ such that $p$, $p+2$, and $p+4$ are all primes is

$$ p = 3 $$

✔️ QED.

Smallest prime where the successor of the product of primes up to it is not prime

Find a prime number p such that the number (2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅⋅⋅ p) + 1 is not prime.

Let's break this problem down step by step.

Problem restatement:

Find a prime number $p$ such that the number

$$ (2 \cdot 3 \cdot 5 \cdot 7 \cdots p) + 1 $$

is not prime.

This is the product of all primes up to $p$ (the primorial of $p$) plus 1. You're being asked for the smallest prime $p$ where this is not prime (i.e., composite).

---

Step 1: Test Small Values of $p$

Let's compute $(2 \cdot 3 \cdot 5 \cdots p) + 1$ for successive primes until it's not prime.

1. $p = 2$:

$$ 2 + 1 = 3 \text{ (prime)} $$

2. $p = 3$:

$$ 2 \cdot 3 + 1 = 6 + 1 = 7 \text{ (prime)} $$

3. $p = 5$:

$$ 2 \cdot 3 \cdot 5 + 1 = 30 + 1 = 31 \text{ (prime)} $$

4. $p = 7$:

$$ 2 \cdot 3 \cdot 5 \cdot 7 + 1 = 210 + 1 = 211 \text{ (prime)} $$

5. $p = 11$:

$$ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2310 + 1 = 2311 \text{ (test primality)} $$

Test 2311:

• Not divisible by 13 (2311/13 = 177.76)
• Not divisible by 17, 19, ... (test shows 2311 is prime)

6. $p = 13$:

$$ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30030 + 1 = 30031 $$

Test 30031: Check divisibility:

• 30031 divided by 59:

$$ 30031 / 59 = 509 $$

Check:

$$ 59 \cdot 509 = 30031 \text{ ✅ } $$

So 30031 is composite.

✅ Therefore, the smallest prime $p$ such that $(2 \cdot 3 \cdot 5 \cdots p) + 1$ is not prime is

$$ \boxed{13} $$

Denumerability of Subsets

Given an enumeration \( a_1, a_2, \ldots, a_n, \ldots \) of a denumerable set \( A \), and an enumeration \( b_1, b_2, \ldots, b_n, \ldots \) of a denumerable set \( B \), we can enumerate \( A \cup B \) in the order \( a_1, b_1, a_2, b_2, \ldots, a_n, b_n, \ldots \). Write a more general version of this statement for the union of arbitrarily many denumerable sets.

More generally, one shows:

Theorem.
If \(\{A_m\}_{m\in\mathbb N}\) is a countable family of countable (denumerable) sets, then
\[ \bigcup_{m=1}^\infty A_m \] is itself countable.

Proof sketch (by explicit enumeration).

1. For each \(m\in\mathbb N\), choose an enumeration

\[ A_m = \{\,a_{m,1},\,a_{m,2},\,a_{m,3},\dots\}. \]

2. Recall that \(\mathbb N\times\mathbb N\) is countable. Fix any bijection

\[ \pi\colon \mathbb N \;\longrightarrow\;\mathbb N\times\mathbb N, \quad \pi(k) = (m(k),\,n(k)). \]

3. Define a new sequence \((c_k)_{k=1}^\infty\) by

\[ c_k \;=\; a_{\,m(k),\,n(k)}. \]

4. Then \(\{c_1,c_2,c_3,\dots\}\) lists every element of \(\bigcup_{m}A_m\)

(possibly with repetitions), showing that \(\bigcup_m A_m\) is countable.

---

Equivalently, if you prefer a “diagonal” style ordering without naming a particular pairing function, you can say:

1. List all pairs \((m,n)\in\mathbb N\times\mathbb N\) in a single sequence, for example by moving along the diagonals

\[ (1,1),\;(1,2),(2,1),\;(1,3),(2,2),(3,1),\;\dots \]

2. Whenever \((m,n)\) appears in that list, write down the \(n\)-th element of \(A_m\), namely \(a_{m,n}\).

Because every pair \((m,n)\) will eventually appear, every element of every \(A_m\) will be listed. Hence a countable union of countable sets is countable.

The set of all infinite subsets of \( \mathbb{N} \) cannot be denumerable; show this by showing that the set of all finite subsets of \( \mathbb{N} \) is denumerable, and then applying the above theorem.

First, partition the collection of all finite subsets of \(\mathbb{N}\) by their cardinality. For each \(k\in\mathbb{N}\), let \[ \mathcal F_k = \bigl\{\,F\subseteq\mathbb{N}:\lvert F\rvert = k\bigr\} \] be the family of all \(k\)-element subsets of \(\mathbb{N}\). Then:

1. Each \(\mathcal F_k\) is denumerable.
   An easy way to see this is to observe that any \(k\)-element subset can be written uniquely as an increasing \(k\)-tuple \[ (n_1,n_2,\dots,n_k) \quad\text{with}\quad n_1<n_2<\cdots<n_k,\quad n_i\in\mathbb{N}. \] The set of all such increasing \(k\)-tuples is a subset of \(\mathbb{N}^k\), and \(\mathbb{N}^k\) is denumerable (e.g.\ by the diagonal‐pairing argument). Hence each \(\mathcal F_k\) is denumerable.

2. The set of all finite subsets is a countable union of the \(\mathcal F_k\).
   \[ \mathcal F \;=\; \bigl\{\,F\subseteq\mathbb{N}:\lvert F\rvert<\infty\bigr\} = \bigcup_{k=0}^\infty \mathcal F_k. \] By the theorem you just proved, a countable union of denumerable sets is denumerable. Therefore \(\mathcal F\) is denumerable.

---

Now let \[ \mathcal I = \bigl\{\,X\subseteq\mathbb{N}:\lvert X\rvert=\infty\bigr\} \] be the collection of infinite subsets of \(\mathbb{N}\). Notice that every subset of \(\mathbb{N}\) is either finite or infinite, so \[ \mathcal P(\mathbb{N}) \;=\; \mathcal F \;\cup\;\mathcal I. \] Suppose, for the sake of contradiction, that \(\mathcal I\) were denumerable. Then \(\mathcal F\) is denumerable (as shown above), so by the union theorem again, \[ \mathcal P(\mathbb{N}) = \mathcal F \cup \mathcal I \] would be a union of two denumerable sets, hence itself denumerable. But this contradicts Cantor’s theorem that \(\mathcal P(\mathbb{N})\) is uncountable. Therefore our assumption was false, and \(\mathcal I\) cannot be denumerable. In other words, the family of all infinite subsets of \(\mathbb{N}\) is uncountable.

Naturals Powerset Uncountable

show that the powerset of the natural numbers is not denumerable

To show that the powerset of the natural numbers \( \mathcal{P}(\mathbb{N}) \) is not denumerable, we aim to prove that it is uncountable—that is, it cannot be placed into a one-to-one correspondence with \( \mathbb{N} \) (the set of natural numbers).

---

Step-by-step Proof (Using Cantor’s Diagonal Argument)

1. Assume for contradiction:

Suppose \( \mathcal{P}(\mathbb{N}) \) is countable. Then there exists a bijection \[ f: \mathbb{N} \to \mathcal{P}(\mathbb{N}) \] So we can list all subsets of \( \mathbb{N} \) as: \[ f(0), f(1), f(2), \dots \] where each \( f(n) \subseteq \mathbb{N} \).

---

2. Construct a special subset:

Define a subset \( D \subseteq \mathbb{N} \) by: \[ D = \{ n \in \mathbb{N} \mid n \notin f(n) \} \] This is called the diagonal subset, because its construction resembles Cantor’s diagonalization.

---

3. Check whether \( D \) appears in the list:

Since we assumed all subsets are listed, \( D \) must be \( f(k) \) for some \( k \in \mathbb{N} \). So consider whether \( k \in D \):

• If \( k \in D \), then by definition of \( D \), \( k \notin f(k) = D \) ⇒ contradiction.
• If \( k \notin D \), then \( k \in f(k) = D \) ⇒ contradiction.

In either case, we get a contradiction.

---

Conclusion:

This contradiction shows our assumption was false. Therefore:

\[ \boxed{\mathcal{P}(\mathbb{N}) \text{ is not countable, i.e., not denumerable.}} \]

It is, in fact, uncountably infinite.