17
$\begingroup$

As you probably know, you can define $2$-tuples $(x_1,x_2)$ as $\{\{x_1\},\{x_1,x_2\}\}$; then you can define $n$-tuples $(x_1,x_2\ldots,x_{n})$ as $((x_1,x_2\ldots,x_{n-1}),x_n)$.

In alternative, you can define ordered pairs $\langle x_1,x_2\rangle$ as $\{\{x_1\},\{x_1,x_2\}\}$ (please notice the use of "ordered pairs" instead of "$2$-tuples" and the use of angular brackets instead of round ones); then you can see $n$-tuples as finite sequences, that is functions whose domain is the set of natural numbers from $1$ to $n$ and whose codomain is the set $\{x_1,\ldots,x_n\}$. So $n$-tuples are sets such as $\{\langle 1,x_1\rangle,\ldots\langle n,x_n\rangle\}$; $0$-tuples are defined to be the empty set.

The first definition is not so rigorous (see the use of dots) and works only for $n\geq 2$. The second definition is rigorous and works for every $n$, but then you end up having ordered pairs and $2$-tuples being different objects; this also implies that you have two kind of cartesian products, two kind of binary relations, two kind of functions and so on.

Is there a way to avoid such problems? Is there another better definition for $n$-tuples?

Thanks.

$\endgroup$
12
  • 6
    $\begingroup$ Why is your second definition more rigorous than the first? There are also dots.... Both definitions can be made rigorous using inductive definitions. In ZFC there are dozens of ways of constructing objects with certain properties. This is perhaps ugly, but it's very convenient. $\endgroup$ Jan 26, 2010 at 11:09
  • 5
    $\begingroup$ Another issue with your first method is that the length of a finite tuple is not determined, when the x_i are themselves tuples, because you don't know how much to "unwrap" it. So this formulation is unsuitable, for example, in a context when one wants to consider the set of all finite tuples of a set of tuples. $\endgroup$ Jan 26, 2010 at 13:09
  • 5
    $\begingroup$ What I mean is that, for example, every 3-tuple is explicitly also a 2-tuple. Every n-tuple is also a k-tuple for every k<n. $\endgroup$ Jan 26, 2010 at 13:12
  • 2
    $\begingroup$ You cannot tell the codomain? And then what does it mean that a function is surjective? Moreover a relation is a subset of the cartesian product of two sets, so it seems to me that you must include the codomain. A relation is a triple (A, B, I)... $\endgroup$ Jan 26, 2010 at 15:02
  • 7
    $\begingroup$ @Andrea: In set theory, surjectivity is not a property of a function by itself, but a property of a function f and a set B: we say that a function f is onto B iff etc. (It doesn't make sense to say that a function, by itself, is surjective, unless B is understood or already specified; and usually it is.) And no, a relation is just a set of ordered pairs, so you can't get the codomain that way. Although I am of course aware that this terminology is different in other areas, but it is nevertheless completely standard in set theory (for about a hundred years). $\endgroup$ Jan 26, 2010 at 15:51

4 Answers 4

34
$\begingroup$

I think the truth is that nobody cares. I mean, you care about such matters a little bit while learning how set theory can be used as a foundation for mathematics, but it soon ceases to be of any importance. In practice, the one important thing about n-tuples is the relation between the n-tuple and its components, i.e., the fact that two n-tuples are the same if and only if they have the same components in the same order.

If you don't learn to stop worrying about such minutiae, you will have plenty more troubles as you learn about number systems. What is the number 3, really? It could be the ordinal {0,1,2} (i.e., {∅,{∅},{∅,{∅}}}), or it could be the integer 3 represented as an equivalence class {(m,n):m=n+3} of ordered pairs of ordinals, or it could be the rational number 3 represented as an equivalence class {(p,q):p=3q, q≠0} of ordered pairs of integers, or it could be the real number 3 represented by whatever your method of defining the real numbers happen to be, or it could even be the complex number represented as a pair of real numbers (3,0) … I hope you get my drift. Every time you expand the number system, and often when you generalize some notion or other, the new contains an isomorphic copy of the old and nobody cares to distinguish between copies.

This practice of identification has its dangers, of course, so it's good that you worry about such things a bit while learning, but expect such matters to recede into the background in order to make room for more important things.

(For what it's worth, I think the method in your second paragraph is good, but having two kinds of ordered pairs should soon stop bothering you.)

$\endgroup$
5
  • $\begingroup$ I would use ordered pairs and sets of ordered pairs in a "temporary" manner, only to define the various number systems up to the complex numbers, and then I would "forget" them in favour of n-tuples (where n is a complex number) and sets of n-tuples. Also, as you correctly pointed out, there are at least five versions of the number 3, but four of them are "temporary", and only the latest one is the "real", useful one. But I think in set theory the procedure to define something is at least as important as the thing you define, so you cannot really skip that step. $\endgroup$ Jan 26, 2010 at 16:41
  • 3
    $\begingroup$ Wait, that's pointless, Francesco. Why would you want to index by complex numbers? They're not ordered and don't admit any nice type of order structure. You're better off indexing by an arbitrary set of cardinality the continuum. Hell, the only reason we index by naturals is because they're well-ordered and it's easy to see where everything starts. Also with the natural numbers, induction by successor holds up to $\aleph_0$. Sometimes you'd like to index by posets like when taking projective and inductive limits, but you would never want to index by complex numbers. No way. $\endgroup$ Jan 26, 2010 at 20:26
  • 5
    $\begingroup$ This answer resonates closely with how I think. The concept of ordered tuple is essentially primitive. The fact that the structure can be implemented in pure set theory is mildly interesting, but it's no fundamental insight into the nature of tuples. $\endgroup$ Jan 27, 2010 at 3:37
  • $\begingroup$ @HarryGindi: I don't want to index by arbitrary complex numbers, but by natural numbers (seen as particular complex numbers). Just wanted to say I prefer not to index by "pure" natural numbers as defined through inductive sets. For example, I prefer to use the digit 0 for the complex number (0R,0R) and not for the empty set (0R stands for the zero defined as a dedekind cut or a cauchy sequence). This is because complex numbers and their operations are much more used in practice than "pure" natural numbers with addition and multiplication alone. $\endgroup$ Jan 27, 2010 at 8:03
  • 2
    $\begingroup$ Rest assured that there are people who cares. Anyone designing systems for formal verification need to decide how to define tuples and if you decide to use set theory as your basic axioms then you need to decide how to define them as sets. $\endgroup$
    – poizan42
    Jun 7, 2016 at 13:56
5
$\begingroup$

Some people do have to care about such details, at least in unusual contexts, and I do think it’s generally worth being aware of your foundations. The details of the definition of ordered pairs is crucial in Quine’s New Foundations (e.g., https://en.wikipedia.org/wiki/New_Foundations#Ordered_pairs), and taking it as primitive can have actual set-theoretic consequences in NF. In Church’s unpublished supplement to his “Set Theory with a Universal Set,” he uses a deliberately ugly [my interpretation] definition of m-tuple to avoid collisions. In my follow-on work, I use the usual Kuratowski definition of ordered pairs, since their internal structure allowed me to model the singleton function as a set, since it’s a 2-equivalence class, for a generalization of Church’s definition of j-equivalence relations.

$\endgroup$
2
$\begingroup$

My point of view is that there is no inherent problem in using either construction. If you adopt a modicum of categorical language, then you can define the set of ordered pairs in either way, then define 'function as subset with extra properties', define composition. Until that point you have no way of comparing sets, so cannot say within the language that the two Cartesian products are different (Can one say different before one can say 'the same'?) The categorical point is then that 'product' is defined by a universal property and so is determined up to isomorphism (bijection) only, hence having two different models with the same property is no big deal.

You may not want to introduce categorical language, but realising there is no problem and that set theoretic ideas cannot tell the difference between two 'different' but bijective sets seems to be a step towards a solution to your conundrum.

$\endgroup$
1
  • 4
    $\begingroup$ = is usually by default a symbol of first order theories, and in any case it is needed as a symbol in ZFC to formulate the axiom of extensionality (two sets are the same iff they have the same members). So there is a way to compare sets and tell if they are the same, and one such comparison is actually used in the axioms. $\endgroup$ Jan 26, 2010 at 14:34
1
$\begingroup$

If you really want to get into you can also check Nicolas Bourbaki "Théorie des ensembles". Category theory can also give an answer on this question, but i think it's too much for such question. But if you use set-theory as an instrument, you can just lay on the indistinguishability of isomorphic entities up to a choosen algebraic system (as others said).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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