Mathematics desk
< May 11	<< Apr \| May \| Jun >>	May 13 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 12[edit]

Countable axiom of choice--is it consistent with Axiom of Determinacy[edit]

I'm personally interested, but if it is or isn't, we should say so in the Axiom of countable choice article.Thanks, Rich (talk) 01:31, 12 May 2009 (UTC)[reply]

It is. If ZF+AD is consistent, then so is ZF+AD+DC, where DC is the axiom of dependent choice, a bit stronger than countable choice. (It's the useful form of countable choice. Countable choice doesn't help you much in any interesting transfinite induction, whereas DC does.)

Actually AD even implies countable choice for sets of reals (that is, if AD is true, then given any countable collection of nonempty sets of reals, you can assign to each such set a real contained in that set). --Trovatore (talk) 02:19, 12 May 2009 (UTC)[reply]

Binary relations and equivalent conditions = Argh[edit]

Argh, my brain is melting with the time I've spent trying and failing to do this question, someone please help!

If R and S are two equivalence relations on the same set A, we deﬁne R ◦ S = {(x, z ) ∈ A × A : there exists y ∈ A such that (x, y) ∈ R and (y, z ) ∈ S }.

Show that the following conditions are equivalent:

(i) R ◦ S is a symmetric relation on A ;

(ii) R ◦ S is a transitive relation on A ;

(iii) S ◦ R ⊆ R ◦ S ;

(iv) R ◦ S is the unique smallest equivalence relation on A containing both R and S .

I've spent literally hours trying to solve this and my brain is leaking out my ears now :( I've managed to prove (i -think-) that (i)=>(ii), and that (i)<=>(iii), but I can't see any way whatsoever to show (ii)=>(i), and I've managed to show that R ◦ S contains both R and S for (iv) but I don't know how to show that if it's the smallest such relation (iv)<=>(i) or (ii) or (iii).

Please help! I'm quite a way out of my depth - (ii)=>(i) is the most frustrating bit, because I'm sure it's probably really obvious but I just can't seem to get it out! :(

If you don't have the time to help me outright then even just pointing me in the direction of a relevant web-page would be useful - thanks very much everyone!! Mathmos6 (talk) 11:07, 12 May 2009 (UTC)[reply]

You are thinking much to complicated. In fact, all of the statements follow directly from the definition. (iv) directly implies (i) and (ii), as equivalence relations are reflexive and transitive by definition. Thus, you don't need to show ii->i at all. --Stephan Schulz (talk) 11:29, 12 May 2009 (UTC)[reply]

(edit conflict) (ii)->(i): if R ◦ S is transitive, then (R ◦ S)⁻¹ = S ◦ R ⊆ (R ◦ S) ◦ (R ◦ S) ⊆ R ◦ S since R and S are symmetric and contained in R ◦ S.

(i)&(ii)<->(iv) is trivial if you unwind the definitions. Could you clarify which of the implications are you having problem with, and how far did you get? — Emil J. 11:33, 12 May 2009 (UTC)[reply]

To show that a set of assertions are logically equivalent is not as hard as verifying the equivalence of any pair of assertions in this set (but is essentially equivalent to doing this!). In essence, it is sufficient to verify that:

(i) => (ii)

(ii) => (iii)

(iii) => (iv)

(iv) => (i)

It is much easier in reality to verify the above, which essentially demonstrates the equivalence between the four statements (you can imagine the logical implications to form a circle - any statement implies another one (based on the above) by travelling clockwise). With regards to your question, all follows from the definitions. --PS T 12:22, 12 May 2009 (UTC)[reply]

Amazing, you guys are fantastic :) I don't see why R.S has to be the -smallest- such relation however? Mathmos6 (talk) 15:44, 12 May 2009 (UTC)[reply]

Well, I suspect there is a clever trick with (iii). But the pedestrian way is via a contradiction. Assume there is a smaller such equivalence relation Q. Then there is a tuple (a,b) in R ◦ S, but not in Q. By definition of R ◦ S, there are (a,c) in R and (c,b) in S. But since Q contains R and S, these are both in Q. And since Q is an equivalence relation, hence transitive, (a, b) in Q. So the assumption must be false. --Stephan Schulz (talk) 16:33, 12 May 2009 (UTC)[reply]

No need to use contradiction. It suffices to say that every transitive relation (and therefore every equivalence) which includes both R and S also includes R ◦ S. — Emil J. 16:54, 12 May 2009 (UTC)[reply]