For infinite sets and to be numerically equivalent. Is bijective function

the only requirement that needs satisfying?

Printable View

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

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 and being countable?

In my question, and 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 nor is denumerable, except there is a bijective function from A to B.

To make it simple. Suppose that and

or equivalently

is defined by

Since we know that is bijective, despite the fact that and being uncountable, is it sufficient to conclude that ? - May 12th 2010, 04:14 AMnovice
- May 12th 2010, 05:12 AMDefunkt
If I recall correctly, the definition is that , and , 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 is injective, the , but I couldn't see how that automatically translate to being bijective.

Now, I think you mean if is bijective, then , and if is surjective, then . Then only after putting those two together,

and .

Yah? - May 12th 2010, 06:32 AMSwlabr
Yes, if surjective then this implies . However, the general technique is that if is an injection and is also an injection, then and so .

For example, there clearly exists an injection , this is just . So to prove that you would just need to find an injection from to , 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 and .

Cleary is finite, and we all know that Since there isn't any element to count nor is there a function from to , 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: defines a linear ordering on the set of all cardinal numbers.

Proof: The only thing that is unclear is the linearity of . So, we must prove that given sets it is true that . If either or is empty the result is clear, so assume not. Fix and and define in the only possible way, clearly this is an injection. Let . Define the ordering on by . This clearly is a partial ordering. We now must prove that every chain has an upper bound. But, it is clear (I hope) that where 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 it will be clear that is an upper bound for from where it follows from Zorn's Lemma that must have a maximal element . Now, suppose that . Then, choosing we may define by and and then of course would contradict the maximality of .

Thus, there exists a bijection from one of or into a subset of the other, and the conclusion follows.

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.