Results 1 to 12 of 12

Math Help - With or without Choice-axiom?

  1. #1
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411

    With or without Choice-axiom?

    Is it possible to make in injection

    X*X --> P(X)

    (*= carthesian product, P(X) is the powerset of X, that is, the set of all subsets from X)

    without the choice-axiom?

    I tried to construct such an injection but it seems somewhat hard
    there's ofcourse an injection X--> P(X) given by x -> {x}

    But X*X--> P(X) doesn't work with <x,y> -> {x,y}
    U need a way to distuinguish between <x,y> and <y,x> somehow.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1
    Quote Originally Posted by Dinkydoe View Post
    Is it possible to make in injection
    X \timesX --> P(X), P(X) is the powerset of X, that is, the set of all subsets from X) without the choice-axiom?
    This may be of no use to you. But this is the usual theorem.
    Prove that A\times B\subseteq \mathcal{P}\left(\mathcal{P}(A\cup B)\right) .
    This follows from the definition of ordered pair: (a,b) \equiv \left\{ {\{ a\} ,\{ a,b\} } \right\}.

    That theorem gives you a natural injection: \Phi:A\times B\mapsto  \mathcal{P}\left(\mathcal{P}(A\cup B)\right) .

    But as I said this does not answer the question as stated.
    However, it may give you some ideas.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Yes, I know this

    This gives a natural injection: X*X--> P(P(X))
    (As you said, by using Kuratowski's definition of an ordered pair: by sending <x,y> -> {{x},{x,y}})

    I was hoping to even get one step further and construct an injection X*X -> P(X) wich should be possible for any infinite set X.

    But I suspect it's impossible to construct such an injection without the Choice-axiom. Was just a curiosity.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1
    Quote Originally Posted by Dinkydoe View Post
    But I suspect it's impossible to construct such an injection without the Choice-axiom. Was just a curiosity.
    I also suspect that is correct.
    By the way, using some basic code you can be clear in your posts.
    For example [tex]A \times B[/tex] gives the output A \times B.
    That means learning basic LaTeX.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    I am actually familiar with Latex

    I'll use Latex-code next time. Thanks for your reply!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Sometimes you can't make it:for example, the case of X has three element.
    If X has four element, then it is very easy since they have the same cardinal, every injection satisfy our requirement.
    If X has more elements, |X|>4:
    Since every set can be well ordered. w.l.o.g. suppose (X, <) is well ordered set.
    define the mapping F:X*X to P(X) as following:
    F(x,x)={x};
    F(x,y)={x,y} if x,y are distinct, and x<y;
    F(x,y)=the complement of {x,y}, if x,y are distinct ,and x>y.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    Since every set can be well ordered. w.l.o.g. suppose (X, <) is well ordered set.
    Well yes, but then you've actually assumed the choice-axiom.

    The choice axiom is equivalent to the wellordering-theorem of Zermelo. And the set X is not necessarily a ordered set!
    And I like to know whether we can construct such an injection without assuming the choice-axiom

    And I suspect this is impossible, since it seems the only way to determine the difference between <x,y> and <y,x> is having some wellorder on X
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    If |X| is less than or equal to 4, it is very easy.
    Othwise,Classify the element into two groups:
    for the element of the form (x,x) in X*X, associate with {x}.
    for the element pair (x,y) and (y,x) wherex,y are distinct,in X*X, associate with pair \{x,y\} \text{ and }\{x,y\}^c,no matter the detail on how they are associated in the sysmetric pair, since we are focus on "injection mapping".
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Shanks View Post
    If |X| is less than or equal to 4, it is very easy.
    Othwise,Classify the element into two groups:
    for the element of the form (x,x) in X*X, associate with {x}.
    for the element pair (x,y) and (y,x) wherex,y are distinct,in X*X, associate with pair \{x,y\} \text{ and }\{x,y\}^c,no matter the detail on how they are associated in the symmetric pair, since we are focus on "injection mapping".
    That does not avoid the Axiom of Choice, because for each pair (x,y) and (y,x) you have to choose which of them will go to \{x,y\} (with the other one going to \{x,y\}^c).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Quote Originally Posted by Opalg View Post
    That does not avoid the Axiom of Choice, because for each pair (x,y) and (y,x) you have to choose which of them will go to \{x,y\} (with the other one going to \{x,y\}^c).
    I know what you mean. How about first proving the following proposition and then applying to the problem:
    \text{ If }\{A_i:i\in I\}\text{ is pairwise disjoint set collection, so is }\{B_i:i\in I\},

     \text{ and for each }i \in I,\text{ there is injective mapping }f_i:A_i \to B_i,

    \text{ then there is injective maping }f\text{ from the union of }\{A_i:i\in I\} \text{ to the union of }\{B_i:i\in I\}.
    Still can't Avoid the AoC.
    Last edited by Shanks; December 19th 2009 at 09:38 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    If X is finite or countable infinite, then we can construct such injective mapping by induction, Otherwise, we can't make it without using the Axiom of Choice.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1
    Quote Originally Posted by Shanks View Post
    If X is finite or countable infinite, then we can construct such injective mapping by induction, Otherwise, we can't make it without using the Axiom of Choice.
    What else do you think this discussion has been about?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Axiom of choice.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2010, 08:50 AM
  2. axiom of choice
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 13th 2009, 02:01 PM
  3. Axiom of choice
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2009, 02:27 AM
  4. Axiom of Choice
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 18th 2006, 01:52 PM

Search Tags


/mathhelpforum @mathhelpforum