12
$\begingroup$

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

  • 0
    @Jonas, ah yes, I must have gotten caught up while TeXing it. That should be $|A\cup (B\setminus A)\setminus\{b\}\cup\{b\}|=p^+$, where $|A\cup (B\setminus A)\setminus\{b\}|=p$ for some $p\in\omega$. Again, thanks.2011-01-16

5 Answers 5

8

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.

  • 0
    Thanks for this idea, SteveB, I think I understand what I was asking to do now better.2011-01-16
7

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.

  • 1
    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.2013-05-16
7

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.

  • 2
    @MathsLover: Yes, using contradiction and "least counterexample" is essentially using induction.2015-01-27
5

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.

  • 0
    @CameronBuie: Luckily the axiom of choice is true. :P2013-05-16
2

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.