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

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

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$:

$$(2+2^2+2^3+\cdots +2^k)+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{array}{r}{\displaystyle \frac{1}{2}}+{\displaystyle \frac{2}{2^2}}+{\displaystyle \frac{3}{2^3}}+\cdots +{\displaystyle \frac{n}{2^n}}=2-{\displaystyle \frac{n+2}{2^n}}\end{array}}$$

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:

$$(2-\frac{k+2}{2^k})+\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{array}{r}1\cdot 2+2\cdot 3+3\cdot 4+\cdots +n\cdot (n+1)={\displaystyle \frac{n(n+1)(n+2)}{3}}\end{array}}$$

Let's prove the statement by mathematical induction.

---

Statement:

For every natural number $n\ge 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$:

$$(1\cdot 2+2\cdot 3+\cdots +k\cdot (k+1))+(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)(\frac{k}{3}+1)$$

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\ge 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{array}{r}{\displaystyle \frac{1}{1\cdot 2}}+{\displaystyle \frac{1}{2\cdot 3}}+\cdots +{\displaystyle \frac{1}{n\cdot (n+1)}}={\displaystyle \frac{n}{n+1}}\end{array}}$$

Let's prove this formula using mathematical induction.

---

Statement:

For every natural number $n\ge 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$:

$$(\frac{1}{1\cdot 2}+\cdots +\frac{1}{k\cdot (k+1)})+\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\ge 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\text{where}k=2,3,4,\dots ,n+1$$

Note that $(n+1)!$ is divisible by $k$ because $k\le 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)!\ge (n+1)\cdot n\cdot \cdots \cdot 2\cdot 1$, which is obviously larger than $k$ for all $n\ge 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. $◼$

Bertrand postulate proof sketch

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

Below is a classical proof of

$$\mathrm{\forall }n\in \mathbb{N},n>1⟹\mathrm{\exists }p\in \mathbb{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 _{\begin{array}{c}p\le x\\ p\text{prime}\end{array}}\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\ge 2$,

$$Ax\le \theta (x)\le Bx.$$

One may take for instance

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

for every $x\ge 2$. (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.11n=(1.84-1.11)n=0.73n>0(\mathrm{\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 $Ax\le \theta (x)\le Bx$.
• In 1932, Erdős found a shorter “combinatorial” proof using properties of the central binomial coefficient $(\genfrac{}{}{0ex}{}{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\le k\le n$, $k$ divides $n!$ (by the definition of factorial).
• But $k$ does not divide $n!-1$ because:

$$n!\equiv 0(\mathrm{mod}k)⟹n!-1\equiv -1\not\equiv 0(\mathrm{mod}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 $\le 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(\mathrm{mod}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(\mathrm{mod}3)$, then

• $p+2\equiv 3\equiv 0(\mathrm{mod}3)$

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

The only prime divisible by 3 is 3 itself, but $p+2>p\ge 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(\mathrm{mod}3)$ with $p>3$.

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

---

• If $p\equiv 2(\mathrm{mod}3)$, then

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

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

Again, unless $p+4=3$ (impossible because $p+4>p\ge 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(\mathrm{mod}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{{\displaystyle 13}}$$

Denumerability of Subsets

Given an enumeration $a_1,a_2,\dots ,a_n,\dots$ of a denumerable set $A$, and an enumeration $b_1,b_2,\dots ,b_n,\dots$ of a denumerable set $B$, we can enumerate $A\cup B$ in the order $a_1,b_1,a_2,b_2,\dots ,a_n,b_n,\dots$. 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}^{\mathrm{\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 :\mathbb{N}⟶\mathbb{N}\times \mathbb{N},\pi (k)=(m(k),n(k)).$$

3. Define a new sequence $(c_k{)}_{k=1}^{\mathrm{\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=\{F\subseteq \mathbb{N}:|F|=k\}$$ 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)\text{with}{n}_1<n_2<\cdots <n_k,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}=\{F\subseteq \mathbb{N}:|F|<\mathrm{\infty }\}=\bigcup _{k=0}^{\mathrm{\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}=\{X\subseteq \mathbb{N}:|X|=\mathrm{\infty }\}$$ 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{{\displaystyle \mathcal{P}(\mathbb{N})\text{ is not countable, i.e., not denumerable.}}}$$

It is, in fact, uncountably infinite.