For infinite sets $\displaystyle A$ and $\displaystyle B$ to be numerically equivalent. Is bijective function

$\displaystyle f:A \rightarrow B$

the only requirement that needs satisfying?

Printable View

- May 11th 2010, 07:18 PMnoviceNumerically Equivalent Sets
For infinite sets $\displaystyle A$ and $\displaystyle B$ to be numerically equivalent. Is bijective function

$\displaystyle f:A \rightarrow B$

the only requirement that needs satisfying? - May 11th 2010, 08:30 PMgmatt
I'm not sure what you mean by numerically equivalent. One way of defining two sets to have the same cardinality if and only if there exists a bijection between the two.

There is apparently another way of comparing set cardinalities, with cardinal numbers but I never learned anything on the topic and someone more knowledgeable on the matter will have to discuss it.

(Note that when I say if and only if its merely a logical statement used in every definition, sometimes implicitly.) - May 11th 2010, 08:40 PMDrexel28
- May 12th 2010, 04:11 AMnovice
Are you thinking of $\displaystyle A$ and $\displaystyle B$ being countable?

In my question, $\displaystyle A$ and $\displaystyle B$ are infinite.

I know this theorem: An infinite subset of a denumerable set is denumerable.

But I am tweaking it for a different scenario, where I know that neither $\displaystyle A$ nor $\displaystyle B$ is denumerable, except there is a bijective function from A to B.

To make it simple. Suppose that $\displaystyle A = \mathbb{R}$ and $\displaystyle B=\mathbb{R}$

$\displaystyle f:A \rightarrow B$ or equivalently $\displaystyle f:\mathbb{R} \rightarrow \mathbb{R}$

is defined by $\displaystyle f(x)=x$

Since we know that $\displaystyle f$ is bijective, despite the fact that $\displaystyle A$ and $\displaystyle B$ being uncountable, is it sufficient to conclude that $\displaystyle |A|=|B|$? - May 12th 2010, 04:14 AMnovice
- May 12th 2010, 05:12 AMDefunkt
If I recall correctly, the definition is that $\displaystyle |A| = |B| \text{ if } \exists f:A \overset{\text{bijection}} {\longrightarrow} B$, and $\displaystyle |A| \leq |B| \text{ if } \exists f:A \overset{\text{injection}} {\longrightarrow} B$, as drexel has pointed out.

(This is the definition for any A,B - not just countable sets.) - May 12th 2010, 06:25 AMnovice
Well, you have made it very clear for me to understand.

Drexel runs at hypersonic speed when I am still crawling. I only knew that if $\displaystyle f $ is injective, the $\displaystyle |A| \leq |B|$, but I couldn't see how that automatically translate to $\displaystyle f$ being bijective.

Now, I think you mean if $\displaystyle f$ is bijective, then $\displaystyle f:A\rightarrow B \Rightarrow |A|\leq |B| $, and if $\displaystyle f $ is surjective, then $\displaystyle |A|\geq |B|$. Then only after putting those two together,

$\displaystyle |A|\leq |B|$ and $\displaystyle |A|\geq |B| \Rightarrow |A|=|B| $ .

Yah? - May 12th 2010, 06:32 AMSwlabr
Yes, if $\displaystyle f: A \rightarrow B$ surjective then this implies $\displaystyle A \geq B$. However, the general technique is that if $\displaystyle f_1:A \rightarrow B$ is an injection and $\displaystyle f_2:B \rightarrow A$ is also an injection, then $\displaystyle |A| \leq |B|$ and $\displaystyle |B| \leq |A|$ so $\displaystyle |A| = |B|$.

For example, there clearly exists an injection $\displaystyle f: \mathbb{N} \rightarrow \mathbb{Q}$, this is just $\displaystyle a \mapsto a$. So to prove that $\displaystyle |\mathbb{N}| = |\mathbb{Q}|$ you would just need to find an injection from $\displaystyle \mathbb{Q}$ to $\displaystyle \mathbb{N}$, you don't need to go the whole hog and find a bijection! - May 12th 2010, 06:36 AMnovice
- May 12th 2010, 07:55 AMnovice
Friends, I thought I was done, but something is troubling me when I made $\displaystyle A=\varnothing$ and $\displaystyle B=\varnothing$.

Cleary $\displaystyle \varnothing$ is finite, and we all know that $\displaystyle |\varnothing|=|\varnothing|. $ Since there isn't any element to count nor is there a function from $\displaystyle \varnothing $ to $\displaystyle \varnothing$, how do you prove that |A|=|B|? - May 12th 2010, 07:59 AMMoeBlee
There is a bijection from the empty set onto the empty set. The empty set itself is a bijection from the empty set onto the empty set.

Moreover, if A = the empty set, and B = the empty set, then you don't need set theory to prove |A| = |B|, since it follows by identity theory alone (A = the empty set = B, so A = B, so |A| = |B|). - May 12th 2010, 08:05 AMnovice
- May 12th 2010, 08:10 AMMoeBlee
By the way, I think in some of the discussion above it was taken as implicit that if there is a surjection from A onto B then there is an injection from B into A. However, just to note, that requires the axiom of choice.

The salient principles here that do not require the axiom of choice:

By definition, A and B are equinumerous if and only if there is a bijection from A onto B.

And, if there is a bijection from A onto B, then there is a bijection from B onto A (just take the inverse of the bijection from A onto B).

And, if there is an injection from A into B and there is an injection from B into A, then there is a bijection from A onto B. And, such a bijection can be recovered from the two given injections (by following any of the constructive proofs of Schroder-Bernstein). - May 12th 2010, 04:58 PMDrexel28
I would like to remark that just like the above remark there is another thing which needs to be proven using Zorn's Lemma (AKA AOC).

Theorem: $\displaystyle \text{has a smaller cardinal number}\overset{\Delta}{=}\text{ }\leqslant$ defines a linear ordering on the set of all cardinal numbers.

Proof: The only thing that is unclear is the linearity of $\displaystyle \leqslant$. So, we must prove that given sets $\displaystyle A,B$ it is true that $\displaystyle \exists f:A\overset{\text{injection}}{\longrightarrow}B\te xt{ or }\exists g:B\overset{\text{injection}}{\longrightarrow}A$. If either $\displaystyle A$ or $\displaystyle B$ is empty the result is clear, so assume not. Fix $\displaystyle a_0\in A$ and $\displaystyle b_0\in B$ and define $\displaystyle f_0:\{a_0\}\to\{b_0\}$ in the only possible way, clearly this is an injection. Let $\displaystyle \Omega=\left\{(E,G,f):\{a_0\}\subseteq E,\text{ }\{b_0\}\subseteq G,\text{ }f:E\overset{\text{bijection}}{\longrightarrow}G,\ text{ } x\overset{f}{\mapsto}y\right\}$. Define the ordering $\displaystyle \overset{\Omega}{\leqslant}$ on $\displaystyle \Omega$ by $\displaystyle (E,G,f)\overset{\Omega}{\leqslant}\left(E',G',f'\r ight)\Leftrightarrow E\subseteq E',\text{ }G\subseteq G',\text{ }f'\mid_{E}=f$. This clearly is a partial ordering. We now must prove that every chain $\displaystyle \left\{\left(E_\alpha,G_\alpha,f_\alpha\right)\rig ht\}_{\alpha\in\mathcal{A}}$ has an upper bound. But, it is clear (I hope) that $\displaystyle \left(\bigcup_{\alpha\in\mathcal{A}}E_\alpha,\bigc up_{\alpha\in\mathcal{A}}G_\alpha,F\right)\in\Omeg a$ where $\displaystyle F:\bigcup_{\alpha\in\mathcal{A}}E_\alpha\to\bigcup _{\alpha\in\mathcal{A}}G_\alpha$ is defined in the obvious way (@**novice**there's an exercise, figure it out how to say that in a rigorous manner). Also, once you have defined $\displaystyle F$ it will be clear that $\displaystyle \left(\bigcup_{\alpha\in\mathcal{A}}E_\alpha,\bigc up_{\alpha\in\mathcal{A}}G_\alpha,F\right)$ is an upper bound for $\displaystyle \left\{\left(E_\alpha,G_\alpha,f_\alpha\right)\rig ht\}_{\alpha\in\mathcal{A}}$ from where it follows from Zorn's Lemma that $\displaystyle \left(\Omega,\overset{\Omega}{\leqslant}\right)$ must have a maximal element $\displaystyle \left(E_\mathfrak{M},G_\mathfrak{M},f_\mathfrak{M} \right)$. Now, suppose that $\displaystyle E_\mathfrak{M}\ne A\text{ and }G_\mathfrak{M}\ne B$. Then, choosing $\displaystyle x\in A-E_{\mathfrak{M}}\text{ and }y\in B-G_{\mathfrak{M}}$ we may define $\displaystyle \alpha:E_{\mathfrak{M}}\cup\{x\}\to G_{\mathfrak{M}}\cup\{y\}$ by $\displaystyle \alpha\mid_{E_\mathfrak{M}}=f_{\mathfrak{M}}$ and $\displaystyle x\overset{\alpha}{\mapsto}y$ and then of course $\displaystyle \left(E_{\mathfrak{M}}\cup\{x\},G_{\mathfrak{M}}\c up\{y\},\alpha\right)$ would contradict the maximality of $\displaystyle \left(E_{\mathfrak{M}},G_{\mathfrak{M}},f_{\mathfr ak{M}}\right)$.

Thus, there exists a bijection from one of $\displaystyle A$ or $\displaystyle B$ into a subset of the other, and the conclusion follows. $\displaystyle \blacksquare$

I don't think I said that very eloquently, but oh well.

In essence all your doing is pairing off elements until you run out.