My Math Forum Axiom of Choice

 Applied Math Applied Math Forum

 January 9th, 2014, 02:43 AM #1 Newbie   Joined: Jan 2014 Posts: 23 Thanks: 0 Axiom of Choice I do some exercises in set theory. Among them, there is one that says: Prove, using the Axiom of Choice, the following: a) $\forall x \exists y : \phi(x, y) \equiv \exists f \forall x : \phi(x, f(x))$ b) $\cup_y \cap_x F_{x,y} \subset \cap_x \cup_y F_{x,y}$ It is clear to me that point a) requires AC (to "define" the function f(x)). However, I am not sure why is it required for b)? I solve b) as: $x \in \cup_y \cap_x F_{x,y} \equiv \exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y} \equiv x \in \cap_x \cup_y F_{x,y}$ My questions are: 1) Is my solution correct? 2) Does my solution require the AC? In some implicit way maybe? Maybe it is required for proving the implication $\exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y}$? 3) If not, why use AC? Maybe there is a more elegant way to solve b) using AC (or point a) for that matter, which requires AC)? Note 1: this is not a homework so don't tell me to go and ask the lecturer. I don't have one, that's why I am asking the question here. Note 2: my question concerns only point b). Point a) is clear enough.
January 9th, 2014, 01:12 PM   #2
Math Team

Joined: Sep 2007

Posts: 2,409
Thanks: 6

Re: Axiom of Choice

Quote:
 Originally Posted by smieci I do some exercises in set theory. Among them, there is one that says: Prove, using the Axiom of Choice, the following: a) $\forall x \exists y : \phi(x, y) \equiv \exists f \forall x : \phi(x, f(x))$ b) $\cup_y \cap_x F_{x,y} \subset \cap_x \cup_y F_{x,y}$
Perhaps others are smarter but I have no idea what "$F_{x,y}$" is supposed to represent!

Quote:
 It is clear to me that point a) requires AC (to "define" the function f(x)). However, I am not sure why is it required for b)? I solve b) as: $x \in \cup_y \cap_x F_{x,y} \equiv \exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y} \equiv x \in \cap_x \cup_y F_{x,y}$ My questions are: 1) Is my solution correct? 2) Does my solution require the AC? In some implicit way maybe? Maybe it is required for proving the implication $\exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y}$? 3) If not, why use AC? Maybe there is a more elegant way to solve b) using AC (or point a) for that matter, which requires AC)? Note 1: this is not a homework so don't tell me to go and ask the lecturer. I don't have one, that's why I am asking the question here. Note 2: my question concerns only point b). Point a) is clear enough.

January 10th, 2014, 08:40 AM   #3
Senior Member

Joined: Dec 2013
From: Russia

Posts: 327
Thanks: 108

Re: Axiom of Choice

Quote:
 Originally Posted by HallsofIvy Perhaps others are smarter but I have no idea what "$F_{x,y}$" is supposed to represent!
I assume that $F_{x,y}$ is just a family of sets labeled by two indices.

Quote:
 Originally Posted by smieci I solve b) as: $x \in \cup_y \cap_x F_{x,y} \equiv \exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y} \equiv x \in \cap_x \cup_y F_{x,y}$ My questions are: 1) Is my solution correct?
Yes.

Quote:
 Originally Posted by smieci 2) Does my solution require the AC? In some implicit way maybe?
I don't think so.

Quote:
 Originally Posted by smieci Maybe it is required for proving the implication $\exists y \forall x : x \in F_{x,y} \Rightarrow \forall x \exists y : x \in F_{x,y}$?
No, this definitely does not require AC. It is provable in first-order logic (even constructive one).

Quote:
 Originally Posted by smieci 3) If not, why use AC? Maybe there is a more elegant way to solve b) using AC (or point a) for that matter, which requires AC)?
The only thing that comes to mind is that to prove $\forall x \exists y : x \in F_{x,y}$ you can define a constant function using the $y$ whose existence is guaranteed by $\exists y \forall x : x \in F_{x,y}$, and then use the right-to-left direction of a). However, this direction does not use AC.

 January 11th, 2014, 01:27 AM #4 Newbie   Joined: Jan 2014 Posts: 23 Thanks: 0 Re: Axiom of Choice Evgeny, thank you for the answers. Yes, $F_{x,y}$ is any family of sets labeled by two indices. Good idea to use right-to-left a) to prove b). Maybe this is what was meant by the author of the book? I agree with you, however, that AC is not required in this case also. Thanks for your help, and best regards

 Tags axiom, choice

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post shaharhada Algebra 1 December 13th, 2013 02:21 AM johnr New Users 0 November 9th, 2012 03:35 PM mathabc Applied Math 1 August 11th, 2011 04:22 AM becko Applied Math 2 June 30th, 2010 08:15 PM nandrolone Applied Math 2 June 10th, 2010 09:07 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top