For infinite cardinal $\kappa$, $\kappa$ . $\kappa$ = $\kappa$ . Set Theory Enderton p-162, Lemma 6R

Question

Enderton's proof goes like below;

Let B be any infinite set of cardinality $\kappa$.

Let $H=${$f|f=$$\emptyset$ or $f: A×A-A$ is a bijection for some A $\subseteq B$}

Then he showed that any chain in H has upper bound in H. Hence H has a maximal element, $f_o$. That's fine I have no problem upto this.

But then he tells that the maximal element $f_o$$:A_o×A_o$ $-A_o$ is a bijection, for some $A_o$ $\subseteq B$. The maximal element $f_o$ might not be a bijection from $B×B$ onto $B$, instead for big enough subset $A_o$ $\subseteq B$, $f_o$$:A_o×A_o$ $-A_o$ is a bijection. I am unable to comprehend, why should the transfinite process stop at some $A_o$ $\subseteq B$ instead taking whole B. Can someone explain this point with an expository explanation? (Edit: Here I mainly wanted to get an intuition that how the transfinite recursion process will work in general rather than a formal proof)

My guess: For $B=\omega +2$, we might be stop at $A_o=\omega$. But I don't have any insight into the process. Why might we stop at $A_o$.

====================================

There is similar question already here.

show that for an infinite cardinal $k$, $k + k = k$

I understand the Enderton's proof, as well as Asaf's proof. But I am unable to understand the point in Asaf's proof(link of the Asaf's proof given above)/the same point in Enderton's proof that "Why $(K,f)$ might not be a maximal element of the partial order mentioned in the Asaf's proof?"

It would be best, if I asked this in comment below Asaf's answer but I don't have enough reputation to comment. So if someone explain this to me, I will be thankful.

Answer 1

Note: This answer focuses on the sum of cardinals case, the product case is slightly different but the same example works, and is left as an exercise.

Letting $K=\mathbb{N}$. Applying Zorn’s lemma we get the existence of a maximal element under that order, all Zorn’s lemma says is that a maximal element exists and nothing more, the maximal element could for example be $(\mathbb{N},f)$ but it could also be $(\mathbb{N}-\{0\},g)$(Checking this is a maximal element is not hard), so Zorn’s lemma gives no guarantee that the maximal element is $(K,f)$. Luckily, by the way the order is constructed it is not hard to prove that the maximal element must be of the form $(K-F, h)$ where $F$ is some finite set.

Edit: You don't seem to be convinced that $(\mathbb{N}-\{0\}, g)$ where, $g: \mathbb{N}-\{0\} \to 2\times (\mathbb{N}-\{0\})$ is a bijection, is a maximal element. To prove that it is maximal element note that there can not exist a bijection $f:\mathbb{N}\to2\times \mathbb{N}$ extending $g$, because $2\times\mathbb{N}$ has two more elements than $2\times(\mathbb{N}-\{0\}$), while $\mathbb{N}$ has only one more element than $\mathbb{N}-\{0\}$.

Answer 2

Given sets $S$ and $T,$ I will denote the class of all functions from $S$ to $T$ by ${}^{S}T.$ I will similarly denote the class of all functions from some subset of $S$ to some subset of $T$ by ${}^{[S]}[T].$ The latter is non-standard notation, as far as I'm aware. It is not difficult to prove that if $S$ and $T$ are sets, then so is ${}^ST,$ and from there, one can prove that ${}^{[S]}[T]$ is likewise a set. Finally, for any set $A,$ I will denote the "successor set" of $A$ by $s(A):=A\cup\{A\}.$

Consider $B=s(\omega):=\omega\cup\{\omega\}.$ Then $$H:=\left\{f\in{}^{[B\times B]}[B]\mid f:A\times A\to A\textrm{ is a bijection for some }A\subseteq B\right\}.$$ Indeed, observing that $\emptyset$ is a function that is readily a bijection $\emptyset\times\emptyset\to\emptyset,$ we have that $\emptyset\in H,$ even though I didn't make it explicit that $\emptyset\in H$ from the definition, the way that Enderton did.

The next thing worth noting is something that you already observed, which is that if $A$ is a finite, non-empty subset of $B,$ then there is no $f\in H$ such that $f:A\times A\to A.$ However, that doesn't mean that $H=\{\emptyset\}.$

Indeed, we can use the following classical construction of a bijection $\omega\times\omega\to\omega.$

• Partition $\omega\times\omega$ into sets of ordered pairs as follows. Given $n\in\omega,$ and let $$A_n:=\bigl\{\langle k,m\rangle\in\omega\times\omega\mid k\cup m=n\bigr\}.$$ So, for any element of $A_n,$ we know that neither of its coordinates is greater than $n,$ and at least one of its coordinates is equal to $n.$ It can be shown that the sets $A_n$ are pairwise disjoint, and that their union is all of $\omega\times\omega.$
• It can be shown that for each $n\in\omega,$ $|A_n|=2n+1.$
• Define the relation $\sqsubset$ on $\omega\times\omega$ by $\langle k_1,m_1\rangle\sqsubset\langle k_2,m_2\rangle$ iff either (1) $m_1=m_2$ and $k_1\in k_2$ or (2) $k_1=k_2$ and $m_2\in m_1.$ It can readily be verified that the restriction of $\sqsubset$ to any of the sets $A_n$ is an order relation on $A_n,$ and so a well-order relation (that we might think of as the "clockwise" order).
• Now, we construct a bijection $\omega\times\omega\to\omega$ by recursion, first letting $g(\emptyset,\emptyset)=\emptyset.$ If we have just defined $g(k,\emptyset)$ for some $k\in\omega,$ then we define $g\bigl(\emptyset,s(k)\bigr):=s\bigl(g(k,\emptyset)\bigr).$ If we have just defined $g(k,m)$ for some $\langle k,m\rangle\in\omega\times\omega$ such that $m\neq\emptyset,$ then letting $n=k\cup m,$ we have that $\langle k,m\rangle\in A_n,$ but is not the $\sqsubset$-greatest element of $A_n,$ so letting $\langle k',m'\rangle$ be the immediate $\sqsubset$-successor of $\langle k,m\rangle$ in $A_n,$ we define $g(k',m'):=s\bigl(g(k,m)\bigr).$

The gist is that we work our way through all of $\omega\times\omega$ by working through the sets $A_n$ in numerical order, and working through the individual elements of each set $A_n$ in "clockwise order." I leave it to you to verify that the function $g$ thus defined is, in fact, a bijection $\omega\times\omega\to\omega.$ (You can even work out a formula, if you want.)

However, there are several observations about $g$ that are much more relevant!

1. $g\in H.$
2. $g$ is a maximal element of $H$ with respect to set inclusion.
3. If $f\in H$ such that $f\subseteq g,$ then either $f=g$ or $f$ is the restriction of $g$ to $\emptyset\times\emptyset$ or to $\{\emptyset\}\times\{\emptyset\}.$
4. The largest chain in $H$ including $g$ is of cardinality $3.$

Consequently, there need be no infinite process occurring in $H$ to produce a maximal element at all!