4
$\begingroup$

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation))


In axiomatic (ZFC) set theory, we define the ordered pair $(a,b)$ to equal $\{\{a\},\{a,b\}\}$. Then, we define the ordered triple in terms of the ordered pair: $(a,b,c):=((a,b),c)$. Similarly, we define the ordered quadruple as $(a,b,c,d)=((a,b,c),d)=(((a,b),c),d)$. In general, one can define the $n$-tuple using this nesting argument.

To define $(x)$, Herbert Enderton's 1977 Elements of Set Theory suggests the convention $(x)=x$. This seems reasonable: note that if $S=\{a,b,c,d\}$, then $(a,b,c) \in S^3$, $(a,b) \in S^2$, you would also expect $(a) \in S$, which would be true if you defined $(a)=a \in S$.

Finally, the "Empty Tuple" or "$0$-Tuple", $()$, is defined as

\begin{equation} ()=\{\}=\emptyset \end{equation}

This is confirmed by The Wikipedia Tuple page as the correct choice of definition for $()$. Moreover, this agrees with the conclusion we discovered in the previous discussion, in which we decided that $S^0=\{()\}=\{\emptyset\}=1$. For consistency, then, it is pleasing to know that $()=\emptyset$.


My question, however, pertains to the properties of $()$. I have listed some which I believe true:

  1. $(())=(\emptyset)=\emptyset$. Thus $(())=()$.

  2. The "dissolution property": $((),s_1,\ldots,s_n)=(\emptyset,s_1,\ldots,s_n)=(s_1,\ldots,s_n)$

Any others?

  1. Although this doesn't have to do specifically with the empty tuple, as a follow-up to the dissolution property, it would be ideal if it were true that $((a,b),c)=(a,(b,c))$ (both suitable definitions for $(a,b,c)$), and possibly also $((a,b,c),d)=(a,(b,c,d))=((a,b),(c,d))$ (which are all suitable definitions for $(a,b,c,d)$), etc.

The reason I want (2) to be true is because certain definitions like the nullary operation require that \begin{equation} S^0 \times S^n = \{()\} \times S^n = \{\emptyset\} \times S^n = S^n. \end{equation} For this to be true, however, would require that $((),s_1,\ldots,s_n)=(\emptyset,s_1,\ldots,s_n)=(s_1,\ldots,s_n)$, i.e. property (2). However, I can't just "want" or "believe" these properties to be true; I need to prove them within ZFC set theory, using the set-theoretic definition of $n$-tuples. Any help with this?

Thanks for reading my trail of thoughts, and please let me know if you see anything anywhere which is incorrect. Thanks!


Edit 1: Looking at the "Tuples as Nested Ordered Pairs" section of the Wikipedia Tuple Page, I see they define $(a,b,c)$ not as $((a,b),c)$, but instead as $(a,(b,(c,\emptyset)))$. There are two thing strange about this to me: first why the nesting occurs on the right, and second why they choose to pair $c$ with $\emptyset$ instead of just writing it as $(a,(b,c))$. Any insight on this? I wish I could sort this all out. Thanks again!

Edit 2: Chris Culter's answer points out a contradiction which may stem from the definition of $(a)=a$. Perhaps if we define $(x)=(\emptyset,x)=\{\{\emptyset\},\{\emptyset,x\}\}$ then all the desired properties, including the dissolution property, fall into place. So far we haven't been successful in letting $(\emptyset, a) = (a)$, however. But this is the property we need, i.e. we need $((),s_1,\ldots,s_n)=(s_1,\ldots,s_n)$ if we want $S^0 \times S^n = S^n$!

$\endgroup$
  • 5
    $\begingroup$ There is no need to "define" (): you can use that symbol to denote the only element of $X^0$ and be happy with that. $\endgroup$ – Mariano Suárez-Álvarez Oct 8 '14 at 18:37
  • $\begingroup$ Okay, so you mean one should define $S^0$ first in set theory; then define the member of $S^0$ to be the "empty tuple" and write it as $()$. Correct? I usually see the opposite in set theory: first defining ordered tuples (like $(x)$, $(x,y)$, $(x,y,z)$, etc.), and then defining cartesian products of sets (like $S^2$, $S^3$, etc.) in terms of tuples. $\endgroup$ – Mathemanic Oct 8 '14 at 20:28
  • 2
    $\begingroup$ I don't see how you can have $(a,b)=\{\{a\},\{a,b\}\}$, $(b)=b$, and $(\emptyset,b)=(b)$. Using the first of these three, $(\emptyset,b)=\{\{\emptyset\},\{\emptyset,b\}\}$, which is not $b$. (Or maybe it is...) $\endgroup$ – Steve Kass Oct 8 '14 at 20:53
  • 2
    $\begingroup$ There is an axiom in ZFC to prevent $b$ to be equal to $\{\{\emptyset\},\{\emptyset,b\}\}$. $\endgroup$ – Mariano Suárez-Álvarez Oct 8 '14 at 21:57
  • 2
    $\begingroup$ @Mathemanic: The Wikipedia definition mirrors the way lists are defined in Lisp (or, more generally, in functional languages). Also, it allows to distinguish e.g. the triple $(a,b,c)$ from both the tuple $((a,b),c)$ and the tuple $(a,(b,c))$. $\endgroup$ – celtschk Oct 8 '14 at 22:47
2
$\begingroup$

There is a simple solution to the problem. It comes in two parts. And it says that what you're looking for cannot be done, in general.

The first part, is to see the larger picture, that we may want to extend the notion of tuple to infinite index sets, and iterated ordered pairs is not the way to go. Instead we define what an ordered pair is, and what is a function (using ordered pairs), then an $I$-tuple is a function whose domain is $I$. So an $n$-tuple is a function whose domain is $\{0,\ldots,n-1\}$, and in particular $0$-tuple is a function whose domain is the empty set, so a $0$-tuple is indeed $\varnothing$.

The more important part, as long as you define the product of $A\times B$ as the set of ordered pairs (or set of $2$-tuples) such that one coordinate is in $A$ and the other is in $B$, it will rarely be the case that $A^n\times A^m=A^{n+m}$.

This is because one is a set of ordered pairs, and the other $(n+m)$-tuples. If instead you recognize this issue, and decide to resolve it by relaxing the equality in favor of "canonical isomorphisms", then there is a unique way of concatenating $n$-tuples with $m$-tuples to form $(n+m)$-tuples.

We can acknowledge that this is what's going on, or we can decide to reject set theory outright for using equality rather than equivalences. I don't know how this sort of situation is handled in type-theoretic foundations, but I'm guessing that if you define the product of two collections to give you ordered pairs, then it can't be that different, and you'll just resort to an equivalence instead of equality (even if that equivalence is part of the language and so on).

$\endgroup$
0
$\begingroup$

Okay, let's adopt the definitions:

  • $(x) = x$
  • $(a,b) = \{\{a\},\{a,b\}\}$

Then we can check that $(\varnothing)\neq (\varnothing,\varnothing)$. By definition,

  • $(\varnothing) = \varnothing$
  • $(\varnothing,\varnothing) = \{\{\varnothing\},\{\varnothing,\varnothing\}\}$ (This can be simplified further, but there's no need.)

We have $\{\varnothing\}\in(\varnothing,\varnothing)$, so by the definition of the empty set, $(\varnothing,\varnothing)\neq\varnothing$.

Note that this proof used only the existence and defining properties of the sets $\varnothing$, $\{a\}$, and $\{a,b\}$, which are assumed by the original question. I didn't have to assume any other axioms of set theory—not even Extensionality! So it's hard to imagine a theory with any other outcome.

$\endgroup$
  • $\begingroup$ Aha! Thank you for your answer. So if we want $((),a,b)=(a,b)$, i.e. $(\emptyset,a,b)=(a,b)$, then the problem is likely in choosing to define $(x)=x$. Perhaps if we define $(x)=((),x)=(\emptyset,x)=\{\{\emptyset\},\{\emptyset,x\}\}$ then all the desired properties fall into place. $\endgroup$ – Mathemanic Oct 9 '14 at 4:55
  • $\begingroup$ Well, whatever you do with $(x)$, you can check that you'll still get $(\varnothing,\varnothing)\neq(\varnothing,\varnothing,\varnothing)$. As long as you use the Kuratowski ordered pair to define everything, you'll find that $(a,a,a)$ has a higher rank than $(a,a)$. Now, maybe there are other approaches; see for example mathoverflow.net/a/62801 and math.ucla.edu/~asl/bsl/1403/1403-004.ps $\endgroup$ – Chris Culter Oct 9 '14 at 6:24
  • $\begingroup$ That's not good then... That's the property we need if we want $S^0 \times S^n = S^n$! $\endgroup$ – Mathemanic Oct 9 '14 at 19:43
0
$\begingroup$

If we are to define the Cartesian product of two sets $A$ and $S$ as $\{(a,s):a \in A$ and $s \in S\}$, then in general there is no set $A$ such that $A$ $\times$ $S = S$. If $A$ is empty, then $A$ $\times$ $S$ is empty: see here. If $A$ is non-empty then $A$ $\times$ $S$ cannot be equal to $S$ in general (which requires $A$ $\times$ $S$ $\subseteq$ $S$ and $S \subseteq A \times$ $S$). I leave the proof to you.

This should resolve the issue. But correct me if I'm wrong.

PS: I don't have points to comment, so wrote an answer.

$\endgroup$
  • 1
    $\begingroup$ I feel it's a bit like asking you want 1 + 1 = 1, which is inconsistent with the rest of mathematics. $\endgroup$ – Stranger Dec 18 '14 at 4:05
  • 1
    $\begingroup$ I should however add that you can show a bijection exists between any set $A$ $\times$ $S$ where $A$ has a single element and the set $S$. $\endgroup$ – Stranger Dec 18 '14 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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