Axiom of choice and natural numbers.

[MathematicalPhysicist]

i have a few question, that i hope they will answered.
1) let w={0,1...,n,..}={0}UN, and let f:wxw->w such that the next requirements apply:
a) f(0,n)=n+1
b) f(m+1,0)=f(m,1)
c) f(m+1,n+1)=f(m,f(m+1,n).

i need to prove that for every n,m in w, the next statement applies:
f(m,n)<f(m,n+1).
(i tried with induction, but this was too much complicated for me to do).

2)let there be 2 sets, X and Y, prove with the help of AC that there exist a function from X onto Y iff |X|>=|Y|.

well for the second question, here what i did:
suppose, there exists f:X->Y which is onto Y, if we utilize AC then let's define P(Y)\{empty set} as a subset of X, then by AC f|P(Y)\{empty set} P{Y}\{EMPTY SET}->Y such that f|P(X)\{ES}(A) is in A for every A in P(Y)\{ES} which means Y is onto P(Y)\{ES} and therefore there is bijection between Y and a subset of X, therefore |X|>=|Y|, the second conditional here I am not sure hoe to prove, i will appreciate your help.

 

[matt grime]

in 2) what is P(Y)? Not the power set, surely.

The only if part (that you have tried to prove) is simply: pick a preimage of every point in Y to create a bijection with a subset of X.

the if part is easy then, assuming that your definition of => for cardinals is Y is in bijection with a subset of X: use that bijection to define a map for all x in X

 

[MathematicalPhysicist]

it is the power set of Y, why 'not the power set, surely'.

what's wrong with my approach?

 

[MathematicalPhysicist]

in 2) what is P(Y)? Not the power set, surely.

The only if part (that you have tried to prove) is simply: pick a preimage of every point in Y to create a bijection with a subset of X.

the if part is easy then, assuming that your definition of => for cardinals is Y is in bijection with a subset of X: use that bijection to define a map for all x in X

so about the first if, i should pick f^-1(y)={x in A|f(x)=y} such that for every f^-1(y) is in A where A is in X so there's a bijection between Y and a subset of X, is this correct?

what about the second if?

 

[matt grime]

No, that won't work: y may have many preimages: you need to pick one for each y, that is what the axiom of choice allows you to do.

I told you how to do the 'if' part (which I think you call 'the second if'; it is not a first and second if, it as an if and on only if): you know there is a bijection between Y and a subset of X, ie there is a surjective map from a subset of X to Y, so just extend that to a map on all of X (that is trivially surjective.

 

[MathematicalPhysicist]

the definition of AC that i know from my book is: let X be a family of non empty sets, then there exists a function f:P(X)\{empty set}->X such that f(A) is in A for every A in P(X)\{empty set}.

now if there exists a function from X onto Y f:X->Y then for every y in Y there exists x in X such that f(x)=y, now in order to show that there's a bijection between a subset of X and Y i need to show there's a one to one mapping between them, if ill define A as a subset of X then by AC g:P(A)\{empty set}->A if we let P(A)\{empty set}=Y then there's a one to one cause if x!=x' when x' and x are in P{A}\{empty set} then also f(x)!=f(x') cause f(x) and f(x') are in A which is a subset of P(A)\{empty set}, right?

i think the second part of the proof i can manage.

 

[matt grime]

Again, I repeat my request for you to define P(X), I presume it is power set. There is no way in general to define P(Y) as a subset of X if P(Y) genuinely does mean the power set, which is what you wanted to do in your first post, hence my confusion here. (There is a trivial surjection from X to X but no way to make P(X) a subset of X). Since you are talking about the axiom of choice (and families of sets) then I think it might mean product, but that would be a very non-standard use of the letter P). Try to avoid using X to mean different things in the same post, by the way.

 

[MathematicalPhysicist]

matt, where in my post did i say the P(X) is a subset of X?
all that i said in my post is that A is a subset of X and A is subset of P(A)\{empty set}, not vice versa.

P(X) is the power set of X.

 

[MathematicalPhysicist]

another question in set theory:
find a choice function without the help of AC (if you can) for the next sets:
1) P(Z)\{empty sets}
2) P(Q)\{empty set}
for the first option perhaps it should be f(x)=-x for x in P(Z)\{es}, cause it gets every number from P(Z)\{empty set} to itself but so does f(x)=x, as far as i can tell i need to find a function f(A) which is in A such that A is in P(Z)\{empty set}, right? if so than both of these functions will do as choice functions.

 

[matt grime]

Look at post 1: your method is to, and I quote,

"if we utilize AC then let's define P(Y)\{empty set} as a subset of X"

this is, in general, impossible: you cannot define P(Y) as a subset of X given some surjection from X to Y, since if you could then you can define P(X) as a subset of X which is impossible.

 

[MathematicalPhysicist]

but now I've refraind from that, haven't i?

im really confused here as to how to create a bijection between Y and a subset of X, if we have f:X->Y onto Y then by definition for every y in Y there exists x in X such that f(x)=y, now i need to use AC to see that there's a function one to one from Y->A where A is a subset of X, now if we take a choice function g:Y->A (A is non empty) g(B) is in B and B is in Y, now i need to show that if y!=y' then g(y)!=g(y') how do i show it with what I am given?

 

[matt grime]

Take the union of the sets f^{-1}(y) for y in Y. It is therefore a family of sets and by the axiom of choice it is possible to choose a representative of each one. That is all the axiom of choice says. This is where you use the choice function.

 

[MathematicalPhysicist]

so g:Uf^-1(y)->A (A a subset of X) such that g(B) is in B for every B in Uf^-1(y), but now i need to show that if g(x)=g(x') then x=x', how o i do this? (this ofcourse in order to show that they are one to one).

 

[matt grime]

I am still puzzled as to what you're doing, but that is my fault not yours. B is what? an element of something? a subset of something?

The g you ought to be constructing which is from Y to X is trivially an injection (otherwise f would map one element of X to two elements of Y, and that is not allowed as f is a function).

 

[MathematicalPhysicist]

I am still puzzled as to what you're doing, but that is my fault not yours. B is what? an element of something? a subset of something?

im following the defintion from here http://planetmath.org/encyclopedia/AxiomOfChoice.html
in my notation B is the same as x in there.

The g you ought to be constructing which is from Y to X is trivially an injection (otherwise f would map one element of X to two elements of Y, and that is not allowed as f is a function).

shouldnt it be from Y to a subset of X?

 

[matt grime]

A map from Y to a subset of X is a map from Y to X.

I am not going to, nor should I be expected to, follow a link (that I am supposed to guess...?) to planet math in order to figure out what you mean when you write a letter. Tell me, and everyone else.

 

[MathematicalPhysicist]

no one asked you to guess here, you asked what B stands for and i gave a link to planet math which explains it, any other problems from your behalf to read it are your problems, not mine.

btw, does my construction of g ok, or does it lack something you didnt mention already in your posts?

 

[matt grime]

You used B without explaining its meaning before I asked. If you want help, the onus is on you to explain yourself clearly. I will not bother helping anymore, bye.

 

[CrankFan]

I agree with Matt that your use of $$P(X)$$ was confusing. As such I didn't get too far into the proof in the direction you opted and didn't read the back and forth too much but I think Matt gave a hint on how to do it.

Here's an idea for how to prove it in the other direction

$$|X| >= |Y|$$ implies that there is an injection $$g:Y -> X$$

Define $$f:X \rightarrow Y$$ so that

For all $$x \in X$$

$$f(x) =$$ [Fill in the blank] if $$x \in ran(g)$$

$$f(x) =$$ [Something about choice] if $$x \notin ran(g)$$

To show the other direction you can use a similar idea.