Set of all functions and axiom of choice question

B

Barles

New member
Joined
Dec 2, 2013
Messages
8
So the problem is formulated as follows:

"Show that there is no set to which every function belongs"

So the plan is to form the "set" containing every function, and show that this leads to the set of all ordered pairs, and then the set of all sets.

A = {fi | (∀<x,y1> ∈ fi ^ ∀<x,y2> ∈ fi) y1=y2 }
∪A = {<x,y> | (∀<x,y> (∃ fi ∈ A)<x,y> ∈ fi }

I want to show that ∪A is the set of all ordered pairs. It feels like I need the axiom of choice here, but I'm not sure if it can actually do what I think I need it to do here. Here's what I mean. I take an arbitrary ordered pair <a,b>, and try to show that it is in ∪A. <a,b> belongs to some relation (if nothing else, {<a,b>}). At this point, I want to use the axiom of choice to say that from some arbitrary relation containing <a,b>, I can extract a function containing <a,b> as an element, and that function would be a member of the set A. The axiom of choice is formulated as such:

For any relation R, there is a function H ⊆ R with domH = domR.

I guess my first question is, am I on the right track? And my second is, does the axiom of choice actually do what I need it to do here? Because if it does, I can't see it.
 
Barles said:
"Show that there is no set to which every function belongs"
A = {fi | (∀<x,y1> ∈ fi ^ ∀<x,y2> ∈ fi) y1=y2 }
∪A = {<x,y> | (∀<x,y> (∃ fi ∈ A)<x,y> ∈ fi }
I want to show that ∪A is the set of all ordered pairs. It feels like I need the axiom of choice here, but I'm not sure if it can actually do what I think I need it to do here. Here's what I mean. I take an arbitrary ordered pair <a,b>, and try to show that it is in ∪A. <a,b> belongs to some relation (if nothing else, {<a,b>}). At this point, I want to use the axiom of choice to say that from some arbitrary relation containing <a,b>, I can extract a function containing <a,b> as an element, and that function would be a member of the set A. The axiom of choice is formulated as such:
Click to expand...

I wish you would learn to post using LaTeX. I cannot read enough of the above to know what the heck you are on about. That characterization is one of many for the axiom of choice.

Do you have a reference to this problem? Is it also from Enderton?
It looks like a logician's notation for ordered pairs: \(\displaystyle <x,y>=\{\{x\},\{x,y\}\}\)

Can you restate it simply?
 
pka said:
I wish you would learn to post using LaTeX. I cannot read enough of the above to know what the heck you are on about. That characterization is one of many for the axiom of choice.

Do you have a reference to this problem? Is it also from Enderton?
It looks like a logician's notation for ordered pairs: \(\displaystyle <x,y>=\{\{x\},\{x,y\}\}\)

Can you restate it simply?
Click to expand...

If I'm welcome to it I'll be asking a lot of questions here so I probably should learn latex.

But yes, the problem is from Enderton, Chapter 3 problem 16. <x,y> is exactly as you wrote. I'll write in words what I mean by the sets in the initial post.

A = the set of all functions f such that for any ordered pair <x,y1> in f, and any ordered pair <x,y2> in f, y1 = y2.

Basically the set A is a set of functions that has an entry condition that every function should meet.

∪A is the union over the set A. It's usage is described in Enderton Chapter 2 under the section "Arbitrary Unions and Intersections".

∪A = the set of all ordered pairs <x,y> such that for any ordered pair <x,y>, there exists a function f in the set A, such that <x,y> is in f.

Taking the union over A essentially takes all of the functions in A, opens them up and dumps out all of the ordered pairs in those functions, forming a new set I'm calling ∪A.

Also note that I'm using "f" now instead of "fi" as in the initial post. I think the index isn't needed. Hopefully I didn't make some gross error in all of this.
 
Last edited:
Barles said:
But yes, the problem is from Enderton, Chapter 3 problem 16. <x,y> is exactly as you wrote. I'll write in words what I mean by the sets in the initial post.
Click to expand...

Thank you. Have you done #15 just above #16?
 
stapel said:
I suspect that the other poster was asking about the other exercise because he wanted to know what your results were. ;)
Click to expand...


Oh, alright. Here goes:

Let A be a set of functions such that for any f and g in A, either f ⊂ g or g ⊂ f. Show that UA is a function.

Let x ∈ UA, then ∃f ( x ∈ f ∈ A). This makes the the set x an ordered pair, and the set UA a relation.

Fix some y ∈ UA where y ∈ g for some g ∈ A. Also, let x = <a, b1>, and y = <a, b2>.

If f ⊂ g, then x ∈ g and y ∈ g. thus, b1 = b2, because g is a function.

If g ⊂ f, then y ∈ f and x ∈ f. Thus, b1 = b2, because f is a function.

Forgive the lack of proper latex formatting, I cannot download any of the packages as I'm doing this from my work computer. Below I'll rewrite the proof in words as I did in an earlier post.

Let x be an element of the union over the set A. Then there exists a set f such that x is an element of f, and f is an element of A. This makes the set x an ordered pair, and the union over the set A, a relation.

Let y be an element of the union over the set A, where y is an element of the set g, for some g in A. Also, let x = <a, b1>, and let y = <a, b2>.

If f is a subset of g, then x is an element of g, and y is an element of g, forcing b1 = b2, since g is a function.

If g is a subset of f, then x is an element of f, and y is an element of f, forcing b1 = b2, since f is a function.

Thus, the union over the set A is itself a function.
 
Last edited:
You must log in or register to reply here.
Top