# Thread: Cardinality of a total order on an infinite set

1. ## Cardinality of a total order on an infinite set

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.

2. ## Re: Cardinality of a total order on an infinite set

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:

I would then use that if Z ⊆ A that a total order on A would totally order Z, and there exists an element a in A not in Z. (if Z is a proper subset not equal to A)

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.

3. ## Re: Cardinality of a total order on an infinite set

I think that since A is the disjoint union of R and R^-1 (the inverse relation),and the last two relations have the same cardinality,then A and R must have the same cardinality.Am I right?

4. ## Re: Cardinality of a total order on an infinite set

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.

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?

5. ## Re: Cardinality of a total order on an infinite set

I ment AXA=R.

6. ## Re: Cardinality of a total order on an infinite set

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.

7. ## Re: Cardinality of a total order on an infinite set

AXA is the disjoint union of R and R^-1

8. ## Re: Cardinality of a total order on an infinite set

Originally Posted by hedi
AXA is the disjoint union of R and R^-1
That makes no sense. $\mathscr{R}$ is a total ordering on $A$ and as such it is reflexive.
So $\mathscr{R}~\&~\mathscr{R}^{-1}$ cannot be disjoint. Thus what do you really mean?

Are you claiming that $|A|\le |\mathscr{R}|~$

9. ## Re: Cardinality of a total order on an infinite set

Total order here is transitive and anti-reflexive.

10. ## Re: Cardinality of a total order on an infinite set

Originally Posted by hedi
Total order here is transitive and anti-reflexive.
That is not true in western mathematics. SEE HERE

Combine antisymmetric(1) and totally(3) to get the reflexive property.

11. ## Re: Cardinality of a total order on an infinite set

Yes, but this is the definition I have to work with...