There are a few different ways to define finiteness of sets. The method below is due to Tarski. It requires some preliminary definitions. To improve readability I’ll start being less strict about the bracketing of expressions.
A minimal member of a set \({ A }\) is a set \({ C }\) such that \({ C ∈ A }\) and if \({ B ∈ A }\) and \({ B ⊆ C }\) then \({ B = C }\). In other words, \({ C }\) is a member of \({ A }\) and no proper subset of \({ C }\) is a member of \({ A }\). A maximal member of a set \({ A }\) is a set \({ B }\) such that \({ B ∈ A }\) and if \({ C ∈ A }\) and \({ B ⊆ C }\) then \({ B = C }\). In other words, \({ B }\) is a member of \({ A }\) and is not a proper subset of any member of \({ A }\). Sets can have more than one minimal or maximal member. Suppose \({ x ≠ y }\). Then \({ \{ x \} }\) and \({ \{ y \} }\) are both minimal and maximal members of the set \({ \{ \{ x \} , \{ y \} \} }\).
A set \({ E }\) is said to be finite if every non-empty set of subsets of \({ E }\) has both a minimal and a maximal member. It is said to be infinite if it is not finite.
Your intuitive notion of finiteness probably involves associating a natural number to each finite set, the number of members in the set. This assignment probably has the property that if \({ A }\) is a proper subset of a finite set \({ B }\) then \({ A }\) is also finite and the number of members of \({ A }\) is less than the number of members of \({ B }\). Assuming for a moment that your intuition is correct we can see that every set which is finite according to your intuition is also finite according to the definition above. Let \({ E }\) be finite according to your intuition and let \({ A }\) be a non-empty set of subsets of \({ E }\). The set of numbers of members of members of \({ A }\) is a non-empty set of natural numbers and therefore has a least member. This number is the number of members of some member of \({ A }\). Call that member \({ C }\). If \({ B ∈ A }\) and \({ B ⊆ C }\) then \({ B }\) can’t have fewer members than \({ C }\) because the number of members of \({ C }\) is the least possible number of members for a member of \({ A }\). It is therefore not a proper subset, so \({ B = C }\). In other words \({ B }\) is a minimal member of \({ A }\). The argument to show that \({ A }\) has a maximal member is very similar. We look for a member \({ C }\) of \({ A }\) with the largest possible number of members. Of course subsets of the natural numbers don’t have to have a largest member but in this case we only need to consider subsets of \({ E }\) and they have at most as many members as \({ E }\) has, so there is an upper bound on this set and therefore there is a largest member.
The intuitive notion of finiteness considered above can’t be turned into a definition. It requires a number of facts about sets which we haven’t yet proved. In particular it requires one fact about sets, that proper subsets have a strictly smaller number of members than the whole set, which is only true of finite sets, so even if we had the notions of integers and cardinalities of sets and all their properties we would still be left with a circular definition. That’s why we need a definition like the one above.
The argument above just showed that sets you would intuitively regard as finite are finite according to the definition. It didn’t show that sets you would intuitively regard as infinite are infinite according to the definition. Part of your intuition for infinite sets is probably that they have arbitrarily large finite subsets. In other words, if \({ E }\) is infinite according to your intuition then we can find a subset \({ D _ m }\) with \({ m }\) members for each natural number \({ m }\). Let \({ B _ m }\) be the union of \({ D _ k }\) for each \({ k ≤ m }\) and let \({ A }\) be the set of all \({ B _ m }\)’s. If \({ E }\) were finite according to the definition then some member of \({ A }\) would be maximal. It would have to be \({ B _ m }\) for value of \({ m }\) because those are the only members of \({ A }\). Let \({ n }\) be the number of members of \({ B _ m }\). \({ m ≤ n }\) because \({ B _ m }\) has \({ m }\) members and is a subset of \({ C }\). Let \({ C = B _ { n + 1 } }\). Then \({ C ∈ A }\). Also, \({ B _ m ⊆ C }\) because \({ B _ m }\) is the union of \({ D _ k }\) for \({ k ≤ m }\) and \({ C }\) is the union of \({ D _ k }\) for \({ k ≤ n + 1 }\) and \({ m < n + 1 }\). Since we’ve assumed \({ B _ m }\) is maximal it follows that \({ B _ m = C }\). But \({ B _ m }\) has \({ n }\) members and \({ D _ { n + 1 } }\), which is a subset of \({ C }\), has \({ n + 1 }\) members, so we have a subset with more members than the whole set, which is impossible. So our assumption that \({ E }\) is finite according to the definition is untenable. In other words, every set which is infinite according to your intuition is also infinite according the definition.
As with the previous argument this one can’t really be formalised because the intuitive notion of finiteness is vague and, if pushed too far, circular. That’s why we need a formal definition, which is necessarily somewhat unintuitive. There are two standard choices. One is the definition above, due to Tarski. The other choice, due to Dedekind, is to define infinite sets to be those which have a proper subsets with the same number of members as the whole set, and then to define infinite to mean not finite. Tarski’s definition is better adapted to proving that finite sets have the properties you would expect them to have, e.g. that every subset of a finite set is finite.
Our definition says that \({ E }\) is finite if every member of \({ P P E ∖ ∅ }\) has a maximal member and that every member of \({ P P E ∖ ∅ }\) has a minimal member. In fact either of these conditions implies the other. Suppose, for example, that every \({ A ∈ P P E ∖ ∅ }\) has a maximal member and that \({ B ∈ P P E ∖ ∅ }\). Since every \({ A ∈ P P E ∖ ∅ }\) has a maximal member it follows that \[ A = \{ C ∈ P E : ∃ D ∈ B : C = E ∖ D \} \] has a maximal member. This \({ A }\) is just the set of relative complements of the members of \({ B }\). If \({ C }\) is a maximal member of \({ A }\) then \({ E ∖ C }\) is a minimal member of \({ B }\), so \({ B }\) has a minimal member. The argument above shows that if every member of \({ P P E ∖ ∅ }\) has a maximal member then every member of \({ P P E ∖ ∅ }\) has a minimal member. The same argument, but with the words minimal and maximal switched, shows that if every member of \({ P P E ∖ ∅ }\) has a minimal member then every member of \({ P P E ∖ ∅ }\) has a maximal member. So in order to prove that a set is finite it suffices to prove one condition or the other; we don’t have to prove both.
The empty set is finite. Indeed, \({ P ∅ = \{ ∅ \} }\) and \({ P P ∅ = \{ ∅ , \{ ∅ \} \} }\). The only non-empty member of \({ P P ∅ }\) is \({ \{ ∅ \} }\). It has \({ ∅ }\) as both a minimal and maximal member.
A set with only one member is finite. Let \({ A = \{ a \} }\). Then \({ P A = \{ ∅ , A \} }\) and \({ P P A = \{ ∅ , \{ ∅ \} , \{ A \} , \{ ∅ , A \} \} }\). The non-empty members are \({ \{ ∅ \} }\), \({ \{ A \} }\) and \({ \{ ∅ , A \} \} }\). The first of these has \({ ∅ }\) as a minimal and maximal member. The second has \({ A }\) as a minimal and maximal member. The third has \({ ∅ }\) as a minimal member and \({ A }\) as a maximal member.
We could do a similar case by case analysis to show that sets with two members are finite but it’s better just to prove that the union of two finite sets is finite and use the fact that a set with two members is the union of two sets with one member.
Before considering unions we consider subsets, intersections and relative complements, all of which are easier. We start with subsets. Suppose \({ E }\) is finite and \({ D ⊆ E }\). If \({ A ∈ P P D ∖ ∅ }\) then \({ A ∈ P P E ∖ ∅ }\). \({ E }\) is finite so \({ A }\) has a minimal member. So every non-empty set of subsets of \({ D }\) has a minimal member. We’ve already seen that if every non-empty set of subsets of a set has a minimal member then that set is finite. So \({ D }\) is finite.
As an easy consequence if \({ A }\) or \({ B }\) is finite then \({ A ⋂ B }\) is finite because \({ A ⋂ B ⊆ A }\) and \({ A ⋂ B ⊆ B }\). More generally, if \({ C }\) is a set of sets at least one member of which is finite then \({ ⋂ C }\) is finite, because it’s a subset of that member and subsets of finite sets are finite.
Similarly, if \({ A }\) is finite then \({ A ∖ B }\) is finite for any set \({ B }\) because \({ A ∖ B }\) is a subset of \({ A }\).
Now we turn our attention to unions. Suppose \({ A }\) and \({ B }\) are finite sets and that \({ C }\) is a non-empty set of subsets of \({ A ⋃ B }\). Define \[ D = \{ E ∈ P A : ∃ F ∈ C : A ⋂ F = E \} . \] In other words, \({ D }\) is the set of sets which are intersections of \({ A }\) with members of \({ C }\). This is a set of subsets of \({ A }\). It’s a non-empty set because \({ C }\) is non-empty and taking a member of \({ C }\) and intersecting it with \({ A }\) gives a member of \({ D }\). \({ A }\) is finite so \({ D }\) has a minimal member. Let \({ G }\) be such a member. Now let \[ H = \{ I ∈ P B : G ⋃ I ∈ C \} . \] This is a set of subsets of \({ B }\). Since \({ G ∈ D }\) there must be some \({ F ∈ C }\) such that \({ A ⋂ F = G }\). Let \({ J = F ∖ A }\) for such an \({ F }\). Now \({ J ⊆ F }\) and \({ F ∈ C }\) and \({ C ∈ P P [ A ⋃ B ] }\) so \({ J ⊆ A ⋃ B }\). But no member of \({ J }\) is a member of \({ A }\) so they are all members of \({ B }\). In other words \({ J ⊆ B }\). Also \({ G ⋃ J = [ A ⋂ F ] ⋃ [ F ∖ A ] }\) so \({ G ⋃ J = F }\) and hence \({ G ⋃ J ∈ C }\). Therefore \({ J ∈ H }\) and so \({ H }\) is a non-empty set of subsets of \({ B }\). \({ B }\) is finite so \({ H }\) must have a minimal member. Let \({ K }\) be such a member. Now \({ K ∖ A ∈ H }\) and \({ K }\) was minimal so \({ K ∖ A = K }\) and therefore \({ A ⋂ K = ∅ }\). I claim that \({ G ⋃ K }\) is a minimal member of \({ C }\). First of all, it is a member of \({ C }\) because \({ K ∈ H }\) and the definition of \({ H }\) requires the union of any member of \({ H }\) with \({ G }\) to be in \({ C }\). Suppose \({ L }\) is a member of \({ C }\) such that \({ L ⊆ G ⋃ K }\). Then \({ A ⋂ L ⊆ A ⋂ [ G ⋃ K ] }\). Also, \({ A ⋂ [ G ⋃ K ] = [ A ⋂ G ] ⋃ [ A ⋂ K ] }\). Now \({ G ⊆ A }\) so \({ A ⋂ G = G }\) and \({ A ⋂ K = ∅ }\) so \({ A ⋂ L ⊆ G }\). \({ L ∈ C }\) so \({ A ⋂ L ∈ D }\) and \({ G }\) was a minimal member of \({ D }\) so \({ A ⋂ L = G }\). Then \({ G ⋃ [ L ∖ A ] = L }\). Since \({ L ∈ C }\) it follows that \({ L ∖ A ∈ H }\). Now \({ L ∖ A ⊆ K }\) and \({ K }\) is a minimal member of \({ H }\) so \({ L = A ⊆ K }\). From \({ L = [ A ⋂ L ] ⋃ [ L ∖ A ] }\) we see that \({ L = G ⋃ K }\). In other words we’ve shown that if \({ L ∈ C }\) and \({ L ⊆ G ⋃ K }\) then \({ L = G ⋃ K }\), i.e. that \({ G ⋃ K }\) is a minimal member of \({ C }\). \({ C }\) was an arbitrary non-empty set of subsets of \({ A ⋃ B }\) so every such set of subsets has a minimal member. Therefore \({ A ⋃ B }\) is finite.
From this and the fact that \({ \{ x \} }\) is finite we find that if \({ A }\) is finite then so is \({ A ⋃ \{ x \} }\) for any \({ x }\). One consequence of this that if every proper subset of a set is finite then the set itself is finite. Indeed, suppose \({ B }\) is a set such that every proper subset of \({ B }\) is finite. Either \({ B }\) is empty or there is some \({ x ∈ B }\). If \({ B }\) is empty then we’re done, because we already know the empty set is finite. If \({ x ∈ B }\) then let \({ A = B ∖ \{ x \} }\). Then \({ A ⊆ B }\) and \({ x }\) is a member of \({ B }\) but not of \({ A }\) so \({ A }\) is a proper subset of \({ B }\) and therefore is finite. But we just saw that if \({ A }\) is finite then so is \({ A ⋃ \{ x \} }\), which in this case is \({ B }\), so \({ B }\) is finite.
The following is the counterpart for finite sets to the principle of mathematical induction for integers:
Suppose \({ A }\) is a finite set and \({ B }\) is a set of sets such that \({ ∅ ∈ B }\) and for all \({ C ∈ B }\) and \({ x ∈ A }\) we have \({ C ⋃ \{ x \} ∈ B }\). Then \({ A ∈ B }\).
To prove this, first set \({ D = B ⋂ P A }\). Then \({ D }\) is a set of subsets of \({ A }\). It’s non-empty because \({ ∅ ∈ D }\). It therefore has a maximal member. Let \({ E }\) be such a member. \({ E }\) is a subset of \({ A }\). If it were a proper subset there would be an \({ x }\) which is in \({ A }\) but not in \({ E }\). Let \({ F = E ⋃ \{ x \} }\). Since \({ E ⊆ A }\) and \({ \{ x \} ⊆ A }\) we have \({ F ⊆ A }\). Also, \({ E ∈ D }\) so \({ E ∈ B }\). From the properties which \({ B }\) was assumed to have it follows that \({ E ⋃ \{ x \} B }\), i.e. that \({ F ∈ B }\). Now \({ D = B ⋂ P A }\) and \({ F ∈ B }\) and \({ F ∈ P A }\) so \({ F ∈ D }\). \({ E }\) is a proper subset of \({ F }\) since \({ x }\) is a member of \({ F }\) but not of \({ E }\). But \({ E }\) was a maximal member of \({ D }\). This is impossible, so our assumption that \({ E }\) is a proper subset of \({ A }\) is untenable.
The statement above has a sort of converse:
Suppose \({ A }\) is a member of every set of sets \({ B }\) such that \({ ∅ ∈ B }\) and for all \({ C ∈ B }\) and \({ x ∈ A }\) we have \({ C ⋃ \{ x \} ∈ B }\). Then \({ A }\) is finite.
To prove this we just take \({ B }\) to be the set of finite subsets of \({ A }\). We’ve already proved that it has the required properties. By what we’ve just proved it follows that \({ A ∈ B }\) and therefore that \({ A }\) is finite.
We can use induction on sets to generalise our earlier theorem about the union of two finite sets being finite to finite unions of finite sets. Suppose \({ A }\) is a finite set and each member of \({ A }\) is also a finite set. Let \({ B }\) be the set of subsets of \({ A }\) such that \({ ⋃ B }\) is finite. We have \({ ⋃ ∅ = ∅ }\) and \({ ∅ }\) is finite so \({ ∅ ∈ B }\). If \({ C ∈ B }\) and \({ D ∈ A }\) then \[ ⋃ [ C ⋃ \{ D \} ] = [ ⋃ C ] ⋃ D \] and \({ ⋃ C }\) and \({ D }\) are both finite so \({ ⋃ [ C ⋃ \{ D \} ] }\) is finite. In other words, if \({ C ∈ B }\) and \({ D ∈ A }\) then \({ ⋃ [ C ⋃ \{ D \} ] ∈ B }\). The set \({ B }\) therefore satisfies the conditions from our induction principle for sets and we can therefore conclude that \({ A ∈ B }\), i.e. that \({ ⋃ A }\) is finite.
Another thing we can prove by induction is that the power set of a finite set is finite. For this we first need a preliminary lemma saying that if \({ P A }\) is finite then for any \({ x }\) the set \({ B = P [ A ⋃ \{ x \} ] ∖ P A }\) is also finite. Either \({ x }\) is a member of \({ A }\) or it isn’t. If it is then \({ B = ∅ }\) and we’ve already seen that \({ ∅ }\) is finite. Suppose then that \({ x }\) is not a member of \({ A }\). If \({ C }\) is a non-empty set of subsets of \({ B }\) then we construct a set \({ D }\) of sets of subsets of \({ P A }\) by saying that \({ E ∈ D }\) if and only if \({ E ⋃ \{ x \} ∈ C }\). \({ C }\) was assumed to be non-empty so there is an \({ F }\) in \({ C }\). Then \({ F ∖ \{ x \} ∈ D }\) so \({ D }\) is also non-empty. \({ A }\) is finite so \({ D }\) has a minimal member. Let \({ G }\) be such a member. Then \({ G ⋃ \{ x \} }\) is a minimal member of \({ C }\). So every non-empty set \({ C }\) of subsets of \({ B }\) has a minimal member and therefore \({ B }\) is finite.
We’ve just seen that if \({ P A }\) is finite then so is \({ P [ A ⋃ \{ x \} ] ∖ P A }\) for any \({ x }\). But \[ P [ A ⋃ \{ x \} ] = P A ⋃ [ P [ A ⋃ \{ x \} ] ∖ P A ] \] and the union of two finite sets is finite so \({ P [ A ⋃ \{ x \} ] }\) is finite. Now \({ P ∅ = \{ ∅ \} }\) is finite so by induction on sets we can conclude that if \({ B }\) is finite then so is \({ P B }\).
For reference here are the main finiteness properties we’ve proved so far:
\({ ∅ }\) is finite, as is \({ \{ x \} }\) for any \({ x }\).
If \({ A ⊆ B }\) and \({ B }\) is finite then so is \({ A }\).
If \({ A }\) is finite then so is \({ A ∖ B }\) for any \({ B }\).
If \({ A }\) is a set of sets at least one of which is finite then \({ ⋂ A }\) is finite. In particular \({ B ⋂ C }\) is finite if \({ B }\) or \({ C }\) is finite.
If \({ A }\) is a finite set of sets all of which are finite then \({ ⋃ A }\) is finite. In particular \({ B ⋃ C }\) is finite if \({ B }\) or \({ C }\) is finite.
If \({ A }\) is finite then so is \({ P A }\).