Prove using PMI that if $A$ is denumerable and $B$ is finite, then $A \cup B$ is denumerable.

Question

This is what I have thus far:

Claim: If $A$ is denumerable and $B$ is finite, then $A \cup B$ is denumerable.

Proof. Suppose $A$ is denumerable and $B$ has $n$ elements and $B = \{b_1, b_2, b_3, \ldots, b_n\}$.

(i) Let $n = 1$. Then $A \cup B = A \cup \{b_1\}$. Which, by Th. 5.3.4, is denumerable. Thus this is true for $n = 1$

ii) Assume that $A \cup B$ is denumerable for $B = \{b_1, b_2, b_3, \ldots, b_n\}$.

I don't really know how to use PMI to do the second part. Our instructor said to use Then $A \cup B = A \cup \{\ldots\} \cup \{\ldots\}$ and use PMI in the first part ($A \cup \{\ldots\}$) and then the theorem that if $A$ is denumerable, the $A \cup \{x\}$ is denumerable.

This is what I used for my finished proof:

Claim: If A is denumerable and B is finite, then A ∪ B is denumerable.

Proof. Suppose A is denumerable and B has n elements and B = {b1, b2, b3, …, bn}.

(i) Let n = 1. Then A ∪ B = A ∪ {b1}. Which, by Theorem 5.3.4, is denumerable. Thus this is true for n = 1

(ii) Assume that A ∪ B is denumerable for B = {b1, b2, b3, …, bn}, and (A∪B) ̿=A ̿+B ̿-(A∩B) ̿. We must show that (A∪b_n ) ̿=(A∪b_(n+1) ) ̿

A ̿+(B_n ) ̿-(A∩B_n ) ̿=A ̿+(B_(n+1) ) ̿-(A∩B_(n+1) ) ̿

(B_n ) ̿-(A∩B_n ) ̿=(B_(n+1) ) ̿-(A∩B_(n+1) ) ̿

n-(m+n) = n+1-(m+(n+1))

-m = -m

m = m

Therefore, by PMI A ∪{bn+1} is denumerable, and by Theorem 5.3.4, A ∪ {bn} is denumerable.

Thus, if A is denumerable and B is finite, then A ∪ B is denumerable.

Answer 1

The basic idea is exactly what your instructor said. You have one big theorem, from the sounds of things:

If $A$ is denumerable (countably infinite), then $A \cup \{x\}$ is denumerable.

In other words, if you have a countably infinite set, it's still countably infinite after "adding one more thing."

So, when you have denumerable $A$ and finite $B = \{b_1, b_2, \ldots, b_n\}$, the basic idea is to create a bunch of intermediate denumerable sets. For example,

$$A \cup \{b_1\}$$

must be denumerable, by that theorem. Then, since $A \cup \{b_1\}$ is denumerable, if we add another element from $B$,

$$A \cup \{b_1, b_2\} = \left( A \cup \{b_1\} \right) \cup \{b_2\}$$

the theorem again applies, so that $A \cup \{b_1, b_2\}$ must be denumerable.

We could continue on and write out $A \cup B = A \cup \{b_1, \ldots, b_n\}$ as a bunch of repeated unions, but that gets clunky fast. However, it's exactly the idea behind using induction; we'll just make the argument a little cleaner.

Specifically, we'll let $A_k$ be the set $A \cup \{b_1, \ldots, b_k\}$, where $1 \leq k \leq n$. We want to show that $A_n = A \cup \{b_1, \ldots, b_n\} = A \cup B$ is denumerable.

Base case

$A_1 = A \cup \{b_1\}$ is denumerable. This follows directly from the theorem you were given.

Inductive Hypothesis:

$A_k = A \cup \{b_1, \ldots, b_k\}$ is denumerable. This is what we get to assume, to show that...

Conclusion:

\begin{align*} A_{k + 1} &= A \cup \{b_1, \ldots, b_k, b_{k+1}\} \\ &= \left(A \cup \{b_1, \ldots b_k\}\right) \cup \{b_{k+1}\} \\ &= A_k \cup \{b_{k+1}\}\end{align*}

is denumerable. I haven't explicitly said why it must be, but hopefully you can use your theorem to justify that $A_{k+1}$ is indeed denumerable, given that $A_k$ is.

If you can show that our inductive hypothesis implies the conclusion we want, then PMI will imply that $A \cup B$ is denumerable, for denumerable $A$ and finite $B$, as desired.

Answer 2

Maybe it worth that in the book Metalogic: An Introduction to the Metatheory of Standard First Order Logic By Geoffrey Hunter you can see:

---

also

---

Mathematical Analysis-Problems and Solution By Sitansu Bandyopadhyay has: