How can one prove that the union of two finite sets is again finite, without the use of arithmetic?

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\}$.

-
What definition of finite are you using? Of natural number? Also, what is "arithmetic"? –  Qiaochu Yuan Jan 16 '11 at 2:52
@Qiaochu 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. –  yunone Jan 16 '11 at 3:00
Can you do this by induction on $|B\setminus A|$? Would that be using too much arithmetic? –  Jonas Meyer Jan 16 '11 at 3:13
@Jonas, perhaps forbidding arithmetic of the natural numbers is too restrictive, and I was confused about the definition of "arithmetic" when first reading this assertion. In the book I am reading, it is first mentioned before cardinal arithmetic is introduced, so I assume it meant no arithmetic of natural numbers. As for you suggestion, would it go something like this? Assume $|B\setminus A|=0$. Then $B\subseteq A$, so $A\cup B\subseteq A$ and is thus finite. Assume that if $|B\setminus A|=k$, then $A\cup B$ is finite... –  yunone Jan 16 '11 at 3:22
...Suppose $|B\setminus A|=k^+$. Then consider some $b\in (B\setminus A)$. Then $|(B\setminus A)\setminus\{b\}|=k$, so $A\cup(B\setminus A)\setminus\{b\}$ is finite, and $|A\cup B|=|A\cup(B\setminus A)\setminus\{b\}\cup\{b\}|=k^+$, so $A\cup B$ is finite? Not quite sure if I did it correctly near the end. –  yunone Jan 16 '11 at 3:24

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.

-
Thanks for this idea, SteveB, I think I understand what I was asking to do now better. –  yunone Jan 16 '11 at 6:31

Not entirely free of arithmetic, but giving a proof because I think it would be useful any way.

If both sets are non-empty and finite (if one of them is empty, then the result is trivial), then there are bijections f:{1, ..., m} --> A and g:{1, ..., n} --> B for some choice of m and n. Define a function h:{1, ..., m+n} --> A U B by setting h(i) = f(i) for i = 1 to m and h(i) = g(i - m) for i = m+1 to m+n. It's easy to check h is surjective from which it follows A U B is finite.

-

Another notion of finite is: "The set does not contain a proper subset bijective with itself." This does not use arithmetic, and might be used to show what you want.

-
This notion of finite requires at least some measure of the axiom of choice. Countable choice is enough to ensure this is equivalent to the usual definition of finite. Ultimately, we need to know that every set is comparable (in terms of cardinality) to the natural numbers, or there may be finite sets (in this sense) that are infinite in the usual sense. –  Cameron Buie May 16 '13 at 13:33
@CameronBuie: Luckily the axiom of choice is true. :P –  Grumpy Parsnip May 16 '13 at 14:23

Let $A$ be an arbitrary finite set, and assume by contradiction there exists a $B$ which is finite such that the union is infinite.

We have that $B$ is finite, that is there is a bijection of $B$ to some $\{0,\ldots,n-1\}$. So we can assume that this $n$ is the minimal $n$ to have this property.

Choose an arbitrary $b\in B$ (we can do it because $B$ cannot be empty, otherwise the union $A\cup B=A$ and is still finite) then $B\prime = B\setminus\{b\}$ is a finite set whose cardinality is less than $n$ and therefore $A\prime=A\cup B\prime$ is finite by the minimality of $n$.

We have that $A\prime\cup\{b\}$ is infinite, but (this is a much simpler claim) adding one more element to a finite set is still finite, contradiction.

-
Why does $A\prime=A\cup B\prime$ is finite? –  AnnieOK May 30 at 8:33
"$A'=A\cup B'$ is finite by the minimality of $n$". –  Asaf Karagila May 30 at 8:33
What does it mean exactly? You assume by contradiction that $A\cup B$ is infinite. Then, you subtract one term from $B$ and come to the conclusion that $A\prime=A\cup B\prime$ is finite. –  AnnieOK May 30 at 8:34
Recall that $n$ was the minimal integer such that $|B|=n$ and $A\cup B$ is infinite. Then if we add to $A$ anything less than $n$ elements, the set is finite. –  Asaf Karagila May 30 at 8:35

If your definition of finite is based on a cardinality equal to a natural number, then perhaps in that sense you would never be free of arithmetic in any such proof.

However an alternative definition of finite could be used that would avoid any explicit reference to cardinal numbers and thus to arithmetic. Such a definition is being ordered so that a set is simultaneously well-ordered in both directions, ie. that any nonempty subset has both a smallest and a greatest element (not necessarily different if the subset has only one element).

In ZFC this definition of finite is known to be equivalent to the usual one, ie. that a set has cardinality equal to a natural number.

-
Thanks for your response hardmath. This is actually a comment after a proof using arithmetic in Enderton's Elements of Set Theory. I'm reading through this book currently, and he makes no mention of an alternative definition of finite, so I'm unsure if that's what he intended. But your right, I don't see a way to get around using arithmetic of that natural numbers. –  yunone Jan 16 '11 at 3:08
You don't actually need AC to show that this definition is equivalent to the usual one. –  Ricky Demer Jan 16 '11 at 7:04
@Ricky: Actually, the following is equivalent to AC: "If $X$ is a set such that the inverse of any well-ordering relation on $X$ is again a well-ordering relation on $X$, then $X$ is finite." It's perhaps one of the most surprising AC equivalences. Now, you don't need AC to see that every finite set has this property, but you do need it to see that every set with this property is finite. –  Cameron Buie May 16 '13 at 12:55
@CameronBuie: But isn't this sleight of hand? If $X$ were a set without a well-order, the premise of your AC equivalent is vacuously true, forcing the conclusion that $X$ is finite (and thus has a well-ordering). This "proves by contradiction" that every $X$ has a well-ordering. –  hardmath May 16 '13 at 13:03
True. We can even prove it directly. Suppose $X$ is an infinite set. By the AC equivalent, $X$ has a well-ordering relation whose inverse is not a well-ordering. Then $X$ is well-orderable. It isn't a tricky proof, in any case, but the statement, itself, seems so "obviously true" that it's hard to imagine that it should be equivalent to AC. –  Cameron Buie May 16 '13 at 13:25