MathematicalPhysicist

Gold Member

- 4,139

- 149

## Main Question or Discussion Point

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)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?