4
$\begingroup$

I study at course Foundations of Mathematics the below definitions and lemma:
$\langle x,y\rangle:=\{\{x\},\{x,y\}\}$ (from Kuratowski 1921)
$\langle x,y\rangle:=\{\{\{x\},\varnothing\}\{\{y\}\}\}$ (from Norbert Wiener 1914)

Lemma : If $x\in C$ and $y\in C$ then $\langle x,y\rangle\in P(P(C))$. (Lemma is true with Kuratowski definitions and $P(A)$ means power set of $A$)

  1. Now is there any proof that explain there is no definition compatible with axioms of set theory and $\langle x,y\rangle\in P(C)$ instead of $P(P(C))$?

It seems answer is "No" for me, but I can't present any proof.
If you know any reference which can help for above question please point it.

A new approach:

Can we replace the question with below one:

Prove that there are no formulas $\varphi$ of two free variable, such that for all sets $C$, $\varphi$ describes an injective map from $C\times C$ into $P(C)$.

An other view to problem:

  1. How can I check compatibility of 1. with axioms of set theory?
  2. What informations I will need?
$\endgroup$
10
  • 1
    $\begingroup$ Norbert was a Winner. But his name was Wiener. Also, the definition is not quite correct, you forgot $\varnothing$ in there. $\endgroup$
    – Asaf Karagila
    Feb 9, 2014 at 9:19
  • 1
    $\begingroup$ Also: There is no "fixed enumeration" of the axioms of $\sf ZFC$, so it's not quite clear what are the first six axioms. $\endgroup$
    – Asaf Karagila
    Feb 9, 2014 at 9:22
  • 1
    $\begingroup$ The title of your question says $P(P(C))$, but the body asks about $P(C)$. $\endgroup$ Feb 9, 2014 at 10:57
  • $\begingroup$ Assuming the axiom of choice, there is always injective map $C^2 \to \mathcal{P}(C)$. $\endgroup$
    – user14972
    Feb 9, 2014 at 11:05
  • 3
    $\begingroup$ It's quite easy to prove that for $C=\{0,1,2\}$ we have $|C\times C|>|\mathcal P(C)|$. So we're done with the proof. But what if you want to say "Well, for finite sets... do something, but for infinite sets, do something else." In this case it is consistent with the axioms of $\sf ZFC$ that there is such $\varphi$. $\endgroup$
    – Asaf Karagila
    Feb 16, 2014 at 8:11

1 Answer 1

2
$\begingroup$

The fact that you can't do it for very small sets invariably means that you can't do it at all.

First of all, it is important to note that the way we encode the pairs shouldn't depend on the set we are considering at the moment. So $\langle 0,0\rangle$ should be encoded to the same set regardless to use considering it as an ordered pair in $\omega\times\omega$ or in $V_\omega\times V_\omega$.

This means that given an element $a$, $\langle a,a\rangle$ must be in every $A\times A$ whenever $a\in A$. If we want $A\times A\subseteq\mathcal P(A)$, this means that $\langle a,a\rangle\in\bigcap\{\mathcal P(A)\mid a\in A\}=\{\varnothing,\{a\}\}$. Clearly $\varnothing$ cannot encode all ordered pairs, so $\langle a,a\rangle=\{a\}$.

This means that $\langle a,b\rangle\in\mathcal P(\{a,b\})$ and that if $a\neq b$ then $\langle a,b\rangle\neq\{a\},\{b\}$. Therefore $\langle a,b\rangle=\{a,b\}$. But therefore $\langle a,b\rangle=\langle b,a\rangle$ even if $a\neq b$. And this is a contradiction to the axioms of the ordered pair.

Therefore there is no consistent definition of an ordered pair such that for every set $A$ we have $A\times A\subseteq\mathcal P(A)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .