Results 1 to 11 of 11
Like Tree1Thanks
  • 1 Post By MacstersUndead

Thread: Cardinality of a total order on an infinite set

  1. #1
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    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.
    Thank's in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    343
    Thanks
    48

    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.
    Last edited by MacstersUndead; Jan 18th 2017 at 09:12 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    343
    Thanks
    48

    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.

    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    Re: Cardinality of a total order on an infinite set

    I ment AXA=R.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    343
    Thanks
    48

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    Re: Cardinality of a total order on an infinite set

    AXA is the disjoint union of R and R^-1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,013
    Thanks
    2552
    Awards
    1

    Re: Cardinality of a total order on an infinite set

    Quote Originally Posted by hedi View Post
    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}|~$
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    Re: Cardinality of a total order on an infinite set

    Total order here is transitive and anti-reflexive.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,013
    Thanks
    2552
    Awards
    1

    Re: Cardinality of a total order on an infinite set

    Quote Originally Posted by hedi View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2012
    From
    israel
    Posts
    167
    Thanks
    14

    Re: Cardinality of a total order on an infinite set

    Yes, but this is the definition I have to work with...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. First and Second order Derivatives and Total Revenue
    Posted in the Business Math Forum
    Replies: 1
    Last Post: Oct 5th 2010, 09:25 AM
  2. Second-order total differential
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Jul 19th 2010, 03:53 AM
  3. Cardinality if infinite sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 24th 2010, 11:43 AM
  4. Finite and Infinite order
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 6th 2010, 07:51 AM
  5. Replies: 6
    Last Post: Mar 13th 2010, 10:10 AM

/mathhelpforum @mathhelpforum