Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Some questions on axiom of choice and zorn's lemma.

  1. Feb 13, 2007 #1


    User Avatar
    Gold Member

    1)axiom of choice: prove that for every set X and for every f:X->X there exists g:X->X such that fogof=f.
    2)zorn's lemma: let R be a partial order on X (X a set), prove that there exists a linear order S on X such that R is a subset of S.

    well for the second question i used zorn's lemma to find a maximal partial order S. now we assume that (x,y) and (y,x) aren't in S, so i need to prove that T=SU{(a,b)|(a,x),(y,b) in S} is a partial order and thus get a contradiction.
    now my problem is to prove that it's a partial order obviously (a,a) is in T cause it's in S, but if let's say for antisymmety, if (a,b) and (b,a) in T, then if both of them in S then obvoiously b=a, but what about the other cases? if (a,b) in S and (b,a) not in S, then (b,x) and (y,a) in S, so (y,b) in S and so is (a,x), but then if (b,x) and (y,b) then (x,y) is in S, which is a contradiction this is why the only possible outcome if for (a,b) and (b,a) to be in S.
    is this correct?
    and after that obviously i get a contradiction for the maximality of S.
    (only need to prove transtivity.

    now for the first question, im given a hint to use an equivalent statement for the axiom of choice that if A is a class of non empty sets A={C_i|i in I}, then there exists a function f:A->U(i in I)C_i such that f(C_i) is in C_i for every i in I, but i dont see how to apply it in here, obviously i need to show that g(f(X))=X, but how?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?