Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What I know

  1. I know from Peano's axioms that the empty set is equivalent to the natural number $0$ and that the singleton of the empty set is equivalent to the natural number $1$. ( http://www.proofwiki.org/wiki/Peano%27s_Axioms_Uniquely_Define_Natural_Numbers , http://www.proofwiki.org/wiki/Axiom:Peano%27s_Axioms)

  2. I know from Kuratowski that the set $\{\{A\}\}$ is equivalent to the ordered pair $\langle A,A\rangle$.

What I want to know

  1. Are there any alternative interpretations of $\{\{A\}\}$ other than Kuratowski's?

  2. How can we express an ordered homogeneous triple (e.g. Would $\langle A,A,A\rangle$ be equivalent to $\{\{\{A\}\}\}$?)

  3. It seems like the set $\{\{\varnothing\}\}$ can be interpreted as either $\{1\}$ or $\langle\varnothing,\varnothing\rangle$. Should $\{\{\{\varnothing\}\}\}$ be interpreted as $\langle\varnothing,\varnothing,\varnothing\rangle$ or as $\langle 1,1\rangle$. Is it possible that these tuples are in some way equivalent?

Note, re: Peano's Axioms My understanding of Peano's axioms is consistent with the formulation at WolframAlpha, which is expressed as the 5 postulates:

  1. $0$ is a number.
  2. If $a$ is a number, the successor of $a$ is a number.
  3. $0$ is not the successor of a number
  4. Two numbers of which the successors are equal are themselves equal.
  5. If a set $S$ of numbers contains zero and also the successor of every number in $S$, then every number is in $S$.

These axioms are expressed in set notation at http://www.proofwiki.org/wiki/Axiom:Peano%27s_Axioms / http://www.proofwiki.org/wiki/Peano%27s_Axioms_Uniquely_Define_Natural_Numbers .

share|improve this question

2 Answers 2

up vote 11 down vote accepted

First let me correct one mistake you have in the first line. Peano's Axioms are about numbers. They don't know what are sets. Indeed most people consider PA to be a "good" axiomatization for the natural numbers, but many people don't care whether or not those numbers are sets or not.

It is the common set theoretic interpretation of Peano's axioms from which we understand the empty set as $0$.

Before proceeding I should also add that Zermelo's interpretation of PA was that $n+1=\{n\}$ (You can read more about that here: The history of set-theoretic definitions of $\mathbb N$). In this interpretation: $$0=\varnothing; 1=\{0\}=\{\varnothing\}; 2=\{1\}=\{\{\varnothing\}\}; \dots$$

This in addition to interpreting $\{\{\varnothing\}\}$ as $\langle 0,0\rangle$ and $\{1\}$.

Let me address your questions one at a time:

  1. Yes. You can interpret $\{A\}$ as anything you would like to interpret it, as long as it is coherent with how you interpret other things too. There is nothing particular in how Kuratowski interpreted ordered pairs, or how von Neumann interpreted ordinals (and natural numbers). Those were just very convenient interpretations, so they stuck and became convention.

  2. Kuratowski's idea to express ordered pairs actually came as a general idea, we identify a linearly ordered set with its initial segments. If we think of an ordered pair as "first element, $a$; second element, $b$" then the initial segments are exactly $\{\{a\},\{a,b\}\}$.

    To represent an ordered triplet we therefore would like to write $\langle a,b,c\rangle$ as $\{\{a\},\{a,b\},\{a,b,c\}\}$. However now we have a true problem of interpretation, if $a=b=c$ then both $\langle a,a,a\rangle$ and $\langle a,a\rangle$ would be expressed as $\{\{a\}\}$. Because of that the "atomic" object is an ordered pair, from which we generate functions and treat triplets as indexed by a naturally ordered set like $\{0,1,2\}$.

    We also can agree that $\langle a,b,c\rangle$ is a short for $\langle\langle a,b,\rangle, c\rangle$ (or any other composition of ordered pairs) and then $\langle a,a,a\rangle$ is really $\langle\langle a,a\rangle,a\rangle=\{\{\{a\}\},\{\{\{a\}\},a\}\}$.

    Your suggestion to interpret $\langle a,a,a\rangle$ as $\{\{\{a\}\}\}$ might be useful in this case, but how would that translate to $\langle a,b,c\rangle$ when $a,b,c$ are not necessarily equal? We want definitions to be coherent and as general as possible.

  3. We discussed a bit what $\{\{\varnothing\}\}$ can be interpreted as, and as before $\{\{\{\varnothing\}\}\}$ can be interpreted in many different ways, it just has to be compatible with how we interpret other things too.

    If we agreed that $\{\{\varnothing\}\}=\{1\}$ then $\{\{\{\varnothing\}\}\}=\{\{1\}\}=\langle1,1\rangle$, for example.

All in all, this is just a good example for "type errors" when thinking in terms of sets. Much like when writing code in assembly both numbers and string are the same.

share|improve this answer
5  
Even worse, if $\langle a,b,c\rangle = \{\{a\},\{a,b\},\{a,b,c\}\}$, then $\langle 0,0,1\rangle=\langle 0,1,1\rangle$, and we don't want that! –  Henning Makholm Aug 6 '12 at 15:02
    
What about $(a,b,c)=\{\{\{a\},\{a,b\}\},\{\{a,b,c\}\}\}$ This has the advantage over the "double pair" $((a,b),c)$ that all elements are on the same "depth". Then $(a,a,a)=\{\{\{a\}\}\}$, $(a,a,b)=\{\{\{a\}\},\{\{a,b\}\}\}$, $(a,b,b)=\{\{\{a\},\{a,b\}\},\{\{a,b\}\}\}$. It has also an obvious generalization to $n$-tuples. Also I think it is worthwhile to be able to distinguish between $((a,b),c)$ and $(a,b,c)$. –  celtschk Aug 7 '12 at 5:33
    
@celtschk: It seems reasonable. I've been trying to find Kuratowski's original definition, but I couldn't locate it so far. Note that your definition is really a double tuple too, $\langle a,b,c\rangle=\langle\langle a,b\rangle,\{a,b,c\}\rangle$. –  Asaf Karagila Aug 7 '12 at 13:49
    
@AsafKaragila: $((a,b),\{a,b,c\})=\{\{(a,b)\},\{(a,b),\{a,b,c\}\}\} = \{\{\{\{a\},\{a,b\}\}\},\{\{\{a\},\{a,b\}\},\{a,b,c\}\}\}$. Which is not equivalent to my formula (and doesn't have all variables occurring at the same "depth", although the latter could be changed by using $((a,b),\{\{a,b,c\}\})$ instead (which wouldn't give my set either, though). Indeed, it is easy to see that my set in general isn't a classic pair, because none of the two subsets is a subset of the other. –  celtschk Aug 7 '12 at 15:05
1  
Thank you for the excellent answer. Where can I find the formulation of "Zermelo's interpretation of PA was that n+1={n}"? –  smartcaveman Aug 10 '12 at 20:25

You're taking the Kuratowski ordered pair definition too seriously. It doesn't have any intrinsic intuitive meaning, and in particular does not tell us anything deep about the sets it chooses to represent ordered pair. Its only role is as a technical detail in the proof of

ORDERED-PAIR METATHEOREM. There exists a formula $\phi(x,y,p)$ with three free variables such that

  • For all $x$ and $y$ there is exactly one $p$ such that $\phi(x,y,p)$.
  • If $\phi(x,y,p)$ and $\phi(x',y',p)$, then $x=x'$ and $y=y'$.

are theorems of set theory.

In the entire rest of the development of set theory (including the very formulation of several of the axioms), and of the development of the rest of mathematics as an application of set theory, we forget completely which formula this $\phi(x,y,p)$ actually is and just write it as $\langle x,y\rangle=p$ instead.

This involves taking care that we never depend on any properties of ordered pairs other than what the metatheorem guarantees -- in particular we never put ordered pairs and other things into the same set and expect to be able to tell them apart later, because a priori anything might be a pair. We could have proved the ordered-pair metatheorem for a different $\phi$ -- for example one that represents the particular pair $\langle \omega_3,\{42,19\}\rangle$ as $\varnothing$ and everything else as Kuratowski pairs in reverse order -- and that should not make any difference at all for the rest of the development.

So yes, it is true in a technical sense that $\langle 0,0\rangle $ and $\{1\}$ are the same set. But that is just a coincidence -- an implementation detail -- and we deliberately don't depend on such details when we do mathematics.

It makes very good sense, as Asaf suggests, to view this as a type system. In that view, asking whether $A=B$ when we know $A$ as an ordered pair, and $B$ as a set with particular members, is a type error which produces an implementation-dependent (even if definite) truth value.

share|improve this answer
    
I see that my idea about proof schema with "insert ordered pair here" stuck with you... :-) –  Asaf Karagila Aug 6 '12 at 15:36
    
@Asaf: Yes, indeed. –  Henning Makholm Aug 6 '12 at 15:48
    
Maybe one could formalize the "forgetting" by saying that any formula involving pairs implicitly contains the condition "for any formula $\phi$ fulfilling those conditions" (or maybe that's how it's already done?). So if $p(\phi)$ is the formula formalizing those conditions, the statement $x\in S\times T$ would actually mean $\forall \phi: p(\phi)\rightarrow (\exists U: (x\in U\leftrightarrow \exists s:\exists t: s\in S\land t\in T\land \phi(s,t,x)))$. –  celtschk Aug 7 '12 at 14:55
    
@celtschk: But this is not just this formula. We use "proof schemas" all the time, because we may represent things in a myriad of formulas which may not produce the same object when translated to sets. However the point of the proof is that we use the properties provable from these formulas, and they are merely placeholders. The notion you suggest is somewhat formalized in category theory in the sense that the actual underlying set doesn't matter as long as there is an isomorphism (and sometimes a canonical one, or a unique one) between the different interpretations. –  Asaf Karagila Aug 7 '12 at 15:10
    
@celtschk: I understand that there is a formalization of this in many computer proof systems such as HOL. I've never used it myself, but what I understand is that you can prove a "definitional theorem" "there exist a functional relation with such-and-such properties", and henceforth you're allowed to use that relation and its properties as if they were primitives. Being higher-order helps this work smoothly, of course. –  Henning Makholm Aug 7 '12 at 15:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.