Hi,
Prove that the cardinalities of an infinite set A, and a total order R on A, are equal.
Obviously the cardinality of R is not greater than the cardinality of A.
I need a clue for the other inequality.
Thank's in advance.
Hi,
Prove that the cardinalities of an infinite set A, and a total order R on A, are equal.
Obviously the cardinality of R is not greater than the cardinality of A.
I need a clue for the other inequality.
Thank's in advance.
It's been a long time since I've done set theory, but I'll give you my college try. This is a suggestion only. This could be the wrong way to go about it.
You convinced yourself it's not the case that |R| > |A|
The direction you wish to prove is: It is not the case that |R| < |A|
I would proceed using contradiction to prove this, using the property that "If | X | < | Y |, then there exists Z such that | X | = | Z | and Z ⊆ Y."
Suppose not.
If |R| < |A|, then there exists Z such that |R| = |Z| and Z ⊆ A.
Further clue below. I think what's in the spoiler is all you need to make a conclusion, but I can't seem to close it out. Give the above a try first.
Spoiler:
It's either this way or you use Cantor-Bernstein-Schroeder theorem in a similar way.
C-B-S Theorem: "If |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|." This might be easier than proving strict inequalities.
I'm not sure what you mean by disjoint union of R and R^-1 as the disjoint union of involving sets like {A_i} involves the Cartesian product of A X I. I also don't recall if such a union for infinite sets is necessarily the same carnality. (All I recall is that NxN = N)
Hence I can't confirm/deny what you said.
However, your insight had me re-read the C-B-S Theorem, as thinking about R^-1 sounds correct.
Reference for C-B-S: https://en.wikipedia.org/wiki/Schr%C...nstein_theorem
If there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B (and you're done, since this means that "|A| ≤ |B| and |B| ≤ |A|, then |A| = |B|")
Letting f be R and g be R^-1 might be sufficient as a proof. Is this what you mean?
Sorry, I don't know what you mean. If you mean that the cross product A x A = R, then no, I don't think that's necessarily true. Unfortunately, I don't think I can offer more help at this point. I still think my last comment is the most direct way to solve the problem for any set A.