Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Halmos proves shortly before the cited paragraph that finite subsets are not equivalent to themselves. He then says the following:

The number of elements in a finite set E is, by definition, the unique natural number equivalent to E; we shall denote it by #(E). It is clear that if the correspondence between E and #(E) is restricted to the finite subsets of some set X, the result is a function from a subset of the power set $\mathcal{P}(x)$ to $\omega$.

This is all clear (a specification on dom[$E \rightarrow \#(E)$] of $s : s \subset X$). He then continues:

This function is pleasantly related to the familiar set-theoretic relations and operations. Thus, for example, if $E$ and $F$ are finite sets such that $E \subset F$, then $\#(E) \leq \#(F)$. (The reason is that since $E \cong \#(E)$ and $F \cong \#(F)$, it follows that $\#(E)$ is equivalent to a subset of $\#(F)$.)

I do not follow his reasoning. The fact itself is clear, but I do not see the implication which he is suggesting. Is he indicating that $E$, as a subset of $F$, will be mapped by this function to some natural number which is a subset of $\#(F)$?

Edit: The passage continues:

Another example is the assertion that if $E$ and $F$ are finite sets, then $E \bigcup F$ is finite, and, moreover, if $E$ and $F$ are disjoint, then $\#(E \bigcup F) = \#(E) + \#(F).$ The crucial step in the proof is the fact that if $m$ and $n$ are natural numbers, then the complement of $m$ in the sum $m+n$ is equivalent to $n$; the proof of this auxiliary fact is achieved by induction on $n$. Similar techniques prove that if $E$ and $F$ are finite sets, then so also are $E \times F$ and $E^F$, and, moreover, $\#(E \times F) = \#(E) * \#(F) $ and $\#(E^F) = \#(E)^{\#(F)}$.

share|cite|improve this question
up vote 2 down vote accepted

By definition $\#(E)\cong E\subseteq F\cong \#(F)$. The equivalence $F\cong\#(F)$ means that there is a bijection $h:F\to\#(F)$; clearly $h[E]\subseteq\#(F)$. The equivalence $E\cong\#(E)$ means that there is a bijection $g:\#(E)\to E$. The composition $h\circ g:\#(E)\to\#(F)$ maps $\#(E)$ bijectively to $$h\big[g[\#(E)]\big]=h[E]\subseteq\#(F)\;,$$ thereby establishing that $\#(E)\cong h[E]$, which is a subset of $\#(F)$.

He’s not saying that $\#(E)$ is a subset of $\#(F)$, just that it’s equivalent to one.

share|cite|improve this answer
I follow your reasoning (thank you for the help). I don't see much connection between his discussion about the power-set function, and his assertion, at least as proven here. How are they related? – Chris Jun 4 '12 at 4:01
@user1296727: In this case he appears to be saying that the subset relation between $E$ and $F$ is (almost) mirrored by the $\#$ function: you don’t quite get $\#(E)\subseteq\#(F)$, but you do get $\#(E)$ equivalent to a subset of $\#(F)$. Similarly, you’ll have $\#(A)$ and $\#(B)$ equivalent to subsets of $\#(A\cup B)$. I’d have to read the whole passage to see whether he actually does much with this, or whether it’s more of an aside, and I don’t have the book. – Brian M. Scott Jun 4 '12 at 4:05
Give me a minute, and I'll edit in the rest. – Chris Jun 4 '12 at 4:06
@user1296727: It appears that he’s simply pointing out that this formal definition of the cardinality of a finite set can be shown to behave the way we want it to behave with respect to the various operations on sets. This is important, because the definition would be pretty useless if it didn’t behave right, but the importance may be obscured by the fact that we so obviously designed the definition to behave right. – Brian M. Scott Jun 4 '12 at 4:18
Where is he "getting this" from? The earlier statement about the power-set restriction? – Chris Jun 4 '12 at 4:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.