Suppose to start with that the sets are disjoint. Then prove that if the sets are both finite, and if you remove an element from one set and put it in the other, they are both still finite and their union is unchanged. By induction, you will eventually exhaust one of the finite sets, giving the union of a finite set and the empty set, which is therefore a finite set. Because the union was unchanged in each step, this is equal to the union of the original two sets.
The proof has to be done by constructing bijections between the sets and natural numbers, transferring the element mapped to the last natural number in one set, and mapping it to the successor of the last natural number mapped to by the other.
For the case where the sets are not disjoint you can fix it in several ways, such as deleting them from one set without adding to the other, or proving that removing elements from a finite set always gives a finite result, or using your $B-A$ trick.
Let us review the first solution, it's a bit simpler.
We begin with a set $P_0=\{3\}$. That is the base of the induction. Now suppose that $P_n$ was defined, we take $P_{n+1}$ to be $P_n$ with the addition of all elements of the form $x+y$ where $x,y\in P_n$.
Finally, $P$ is the union of the $P_n$'s, namely $\bigcup_{n=0}^\infty P_n$.
We can do the first few steps explicitly, to get the feel:
- $P_0=\{3\}$, that's the definition of the first step.
- $P_1=\{3,3+3\}$, we took $P_0$ and added $3+3$, which is the only possible combination of $x+y$ where $x,y\in P_0$.
- $P_2=\{3,6,9,12\}$, we took $P_1$ and now we add $3+6$ and $6+6$. We don't need to add $3+3$ because it's already in there.
- $P_3=\{3,6,9,12,15,18,24\}$, we added $3+12,6+12,9+12,12+12$. Note that this also included other pairs such as $6+9,9+9$, etc.
To prove that indeed $P$ is all the multiples of $3$ we need to argue that if $n=3m$ then there is some $k$ such that $n\in P_k$. We prove this by induction, of course, on $m$.
- If $m=1$ then $n=3$ and therefore $n\in P_0$.
- Suppose that for $3m$ we proved that $3m\in P_k$ for some $k$, and let $n=3(m+1)$. Since $3\in P_k$ we have that $3m+3\in P_{k+1}$, and therefore $n=3(m+1)=3m+3\in P_{k+1}$.
Now we need to prove that if a number is in $P$ then it is a multiple of $3$. Again we do this by induction, for example we can do this by induction on the index of $P_k$, namely:
- We know that $P_0=\{3\}$ and therefore all its elements are multiples of $3$.
Suppose that for $P_k$ it is true that all its elements are multiples of $3$, we will show this is true for $P_{k+1}$.
Suppose that $n\in P_{k+1}$, then by the definition of $P_{k+1}$ there are $x,y\in P_k$ such that $n=x+y$. From the induction hypothesis for $P_k$ we have that $x,y$ are both multiples of $3$ and therefore their sum, $n$, is also a multiple of $3$.
Finally:
We have seen what exactly is the definition of $P$, and we have seen how to prove that it indeed has the wanted property. We prove these things carefully by induction, using the inductive definition of the stages constructing $P$.
Best Answer
For induction you have to define some explicit base case, what is the smallest finite set? The empty set. Define its power set explicitly.
Now suppose that you defined the power set of a set with $n$ elements, and $A=\{a_0,\ldots,a_n,a_{n+1}\}$, find a way to write $A$ as the union of $A'$ and a singleton, with $A'$ having $n$ elements; now ask yourself, what sort of subsets of $A$ are there, and how do they relate to subsets of $A'$ and that additional singleton?
Since you're a computer science student (according to the user's profile), here is another way to think about it.
Recall that there is a canonical identification between subsets of $\{0,\ldots,n-1\}$ and binary strings of length $n$. Namely, $A\subseteq\{0,\ldots,n-1\}$ is mapped to the string $\langle a_0,\ldots,a_{n-1}\rangle$ such that $a_i=0$ if and only if $i\notin A$.
Now you can think about this as defining a string of length $n+1$ as a concatenation of a string of length $n$ with either $0$ or $1$.