The set in question is $S=\Bbb{N}×A$, where $A$ is a set with infinitely many elements and $\Bbb{N}$ is the set of natural numbers.

I think cardinality of $S$ is the same as $A$ no matter whether $A$ is countable or not. I have tried to give a bijection between them but no success.

Any help would be appreciated.

  • 1
    $\begingroup$ AFAIK this result depends on AC. Assuming you have AC... if A is infinite then you can provide a mapping from $\mathbb{N}$ into $A$ (why?); then use this mapping to show that $|\mathbb{N}\times A|\leq |A\times A|$. $\endgroup$ – Steven Stadnicki Sep 19 '17 at 15:41
  • $\begingroup$ @StevenStadnicki is there a quick reason that $|A \times A| = |A|$? $\endgroup$ – Omnomnomnom Sep 19 '17 at 15:43
  • 2
    $\begingroup$ @Omnomnomnom Transfinite induction. Specifically, by AC it's enough to show that $\vert\alpha\times\alpha\vert=\vert\alpha\vert$ for every infinite ordinal $\alpha$, and this is proved (in ZF) by transfinite induction on $\alpha$. If we don't have choice, the first part can fail; in fact, "All infinite sets are in bijection with their own square" is equivalent to full choice!" $\endgroup$ – Noah Schweber Sep 19 '17 at 15:46
  • 1
    $\begingroup$ @Omnomnomnom There's a very canonical AC argument that works by well-ordering $A$ and then using the result for ordinals (which is true by induction). (To be fair, the same argument would work relatively directly here: just order $A$ copies of $\mathbb{N}$ and then argue about the order type of the result.) $\endgroup$ – Steven Stadnicki Sep 19 '17 at 15:48

This depends, as Steven Stadnicki said, on whether we assume the axiom of choice.

First, a quick observation: it's not hard to prove by transfinite induction that if $\alpha$ is an infinite ordinal, then $\vert\mathbb{N}\times\alpha\vert=\vert\alpha\vert$. Interestingly, more is true: for all infinite ordinals $\alpha$ we have $\vert\alpha\times\alpha\vert=\vert\alpha\vert$. This is harder to prove, but not much harder.

If we have the axiom of choice, then we're done: given $A$, the axiom of choice lets us prove that there is some ordinal in bijection with $A$; now just apply the previous paragraph.

If choice fails, however, things can get weird: it's consistent with ZF (= the usual axioms of set theory, but without choice) that there are very weird infinite sets! For example, there might be amorphous sets - these are infinite sets which can't be partitioned into two infinite disjoint subsets! It's easy to show that $\mathbb{N}\times A$ can't be amorphous, regardless of what $A$ is (HINT: think about evens vs. odds ...).

A side comment: if choice fails, then "$\vert A\times A\vert=\vert A\vert$" must fail for some infinite set $A$: the statement "for all infinite sets $A$, $\vert A\times A\vert=\vert A\vert$" is equivalent to the axiom of choice (this was proved by Zermelo). Meanwhile, the statement "$\vert A\times\mathbb{N}\vert=\vert A\vert$" is strictly weaker than the axiom of choice, although it isn't provable in ZF alone.

  • $\begingroup$ This has me wondering now whether even in the absence of AC we can say that either $\left|A\times\mathbb{N}\right|=\left|A\right|$ or $\left|A\times\mathbb{N}\right|=\left|\mathbb{N}\right|$. My gut instinct says no, but I don't know choiceless models well enough to be very confident in that. $\endgroup$ – Steven Stadnicki Sep 19 '17 at 17:57
  • $\begingroup$ @StevenStadnicki No. If $\vert A\times\mathbb{N}\vert=\vert\mathbb{N}\vert$, then $A$ is countable (that is, has an injection into $\mathbb{N}$); this means that if $A$ is (say) amorphous, $\vert A\times\mathbb{N}\vert$ is neither $\vert A\vert$ or $\vert\mathbb{N}\vert$. $\endgroup$ – Noah Schweber Sep 19 '17 at 19:18
  • $\begingroup$ Ahhh, of course - we can just look at the image of e.g. $A\times \{0\}$ for an injection. And $|A\times\mathbb{N}|$ can't be $A$ (which I had been thinking was possible) becasue $\mathbb{N}$ injects into it, right? $\endgroup$ – Steven Stadnicki Sep 19 '17 at 19:26
  • $\begingroup$ @StevenStadnicki Exactly. Actually, that's overkill: just think about $A\times\{0\}$ vs. $A\times(\mathbb{N}\setminus\{0\})$. $\endgroup$ – Noah Schweber Sep 19 '17 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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