Suppose $A \subseteq B$ and that $|A| = |B|$ are both finite. Can we conclude that $A = B$? $A$ must contain only elements that are also in $B$, so if we keep choosing elements from $B$ to be in $A$ we will run out because they have the same cardinality. Is there a more formal way to show this?

What if they are both infinite? I think this is probably false, because of this counter example: $\mathbb{N}_2 \subseteq \mathbb{N}$ and $|\mathbb{N}_2| = |\mathbb{N}|$ but $\mathbb{N}_2 \neq \mathbb{N}$. Where $\mathbb{N}_2$ is the even natural numbers.

  • $\begingroup$ The first statement is true. For the second statement how would you define $|\mathbb{N}|$ ? $\endgroup$ – Jennifer Mar 27 '16 at 19:16
  • $\begingroup$ @Jennifer You don't have to define $|{\mathbb{N}}|$ directly. It's enough to show that $|{\mathbb{N}}|=|{\mathbb{N}_2}|$ by defining a bijection. $\endgroup$ – Edward Jiang Mar 27 '16 at 19:19

Both assertions are correct but "keep choosing ... run out" is pretty informal. Better to rely on the definition: a set has infinite cardinality precisely when it's not equicardinal with a proper subset.

I think you want "cardinality" rather than "carnality" but please don't edit that nice typo away.

  • $\begingroup$ Too late for the typo :) $\endgroup$ – McAngus Mar 27 '16 at 19:23
  • 2
    $\begingroup$ This is not the definition of an infinite set. It's an equivalent definition of an infinite set assuming the axiom of [countable] choice, but not necessarily equivalent without it. More specifically, it is consistent that there is a set which is not equipotent to $\{0,\ldots,n-1\}$ for any $n\in\Bbb N$, but it is not equipotent to any of its proper subsets. $\endgroup$ – Asaf Karagila Mar 27 '16 at 19:38
  • $\begingroup$ @AsafKaragila I'm glad to learn that. But even if I'd known it I'd probably have finessed the issue, thinking it too technical for a question at the OP's level. $\endgroup$ – Ethan Bolker Mar 28 '16 at 0:02
  • 1
    $\begingroup$ (1) I agree that this can be glossed over, and in some very basic courses they even give this as a definition for infinite sets, which is fine. (2) Not every basic course does that, and it's up to the OP to tell us whether or not they define infinite this way; in the courses I had taught in basic set theory over the years this was never the definition, and sometimes we would talk about the axiom of choice and prove essentially this equivalence, and other times we wouldn't talk about the axiom of choice at all and don't really mention this definition. $\endgroup$ – Asaf Karagila Mar 28 '16 at 7:18

Your first statement is correct. If they are both infinite consider the following scenario. Let $\mathbb{E} = \{n \in \mathbb{N} | n = 2k, k \in \mathbb{N}\}$. This is the set of all even natural numbers. There is a bijection $f : \mathbb{N} \to \mathbb{E}$ where $f$ is defined by $f(x) = 2x$. Now we have that $\mathbb{E} \subseteq \mathbb{N}$ and $|\mathbb{E}| = |\mathbb{N}|$ but $\mathbb{E} \not = \mathbb{N}$.


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.