The notion that the union of two finite sets is again finite is something I took as intuitively true for quite a while. A proof using arithmetic is relatively straight forward.
Suppose $A$ and $B$ are finite sets, so let $m=|A|$ and $n=|B|$. Now $A\cup B=A\cup(B-A)$, and since $B-A$ is a subset of a finite set, it is also finite (I have already seen this statement proven), so let $k=|B-A|$. Then $|A\cup B|=m+k=m+_\omega k\in\omega$, so $A\cup B\approx m+_\omega k$, and thus finite.
I've read that it is possible to prove this without any use of arithmetic, but I don't quite see how, as arithmetic seems too essential in showing a set is equinumerous to a natural number. Does anyone have a reference to or a reproduction of such a proof?, I'm curious to see. Thank you.
Edit: I was unaware of other definitions of what it means to be finite. I consider a set $A$ finite if there is a bijection $f\colon A\to n$ for some natural number $n$. For arithmetic, I'm trying to refrain from using cardinal arithmetic or the arithmetic of natural numbers, so no $+_\omega$, as was used in the other proof I gave. Also, my definition of natural number is the recursive definition that $0=\emptyset$, and $n^+=n\cup\{n\}$.
Best Answer
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.