With or without Choice-axiom?

Printable View

December 18th 2009, 07:45 AM
Dinkydoe

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.
December 18th 2009, 01:31 PM
Plato

Quote:

Originally Posted by Dinkydoe

Is it possible to make in injection
X $\times$ X --> 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.
December 18th 2009, 02:38 PM
Dinkydoe

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.
December 18th 2009, 03:09 PM
Plato

Quote:

Originally Posted by Dinkydoe

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.
December 18th 2009, 05:18 PM
Dinkydoe

I am actually familiar with Latex :)

I'll use Latex-code next time. Thanks for your reply!
December 18th 2009, 06:16 PM
Shanks

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.
December 19th 2009, 04:20 AM
Dinkydoe

Quote:

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
December 19th 2009, 06:37 AM
Shanks

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".
December 19th 2009, 07:57 AM
Opalg

Quote:

Originally Posted by Shanks

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$ ).
December 19th 2009, 08:52 AM
Shanks

Quote:

Originally Posted by Opalg

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.
December 19th 2009, 05:57 PM
Shanks

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.
December 19th 2009, 07:08 PM
Plato

Quote:

Originally Posted by Shanks

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?