14
$\begingroup$

Sets are defined in such a way that $\{a,a\}$ is the same as $\{a\}$, and $\{a,b\}$ is the same as $\{b,a\}$. By contrast, the ordered pair $(a,a)$ is distinct from $(a)$, and $(a,b)$ is distinct from $(b,a)$.

Intuitively, it would seem useful to draw a distinction between two collections if they are ordered differently, or if one collection has a different number of copies of an element to the other. For instance, this would mean that the collection of prime factors of $6$ would be different to that of $12$. However, it is the set, rather than the tuple, that is chosen as the primitive object. Why is it useful for the foundations of mathematics that sets have very little "structure", and would their be any difficulties in choosing tuples to be the primitive object instead?

$\endgroup$
6
  • 5
    $\begingroup$ Maybe one idea is that you can use sets to construct tuples, i.e. $(a,b)$ can be realized as $\{a, \{a,b\}\}$ or something like that. So we pick the more general object, i.e. sets. $\endgroup$ Jul 31 at 20:48
  • 1
    $\begingroup$ For your prime factors of $12$ being $2$ twice and $3$, you may want to use multisets rather than tuples since $(2,2,3)$, $(2,3,2)$ and $(3,2,2)$ are different tuples. Multisets are harder to handle than sets as it is harder to check that two multisets are the same. $\endgroup$
    – Henry
    Jul 31 at 21:09
  • 5
    $\begingroup$ How do you define an infinite tuple? $\endgroup$ Jul 31 at 21:13
  • 3
    $\begingroup$ Sets are nice for first-order logic because every statement about sets is encoded using a single binary relation $\in$. What's the analogy for tuples? "Initial sub-tuple" maybe? "head/tail"? $\endgroup$ Jul 31 at 21:16
  • 5
    $\begingroup$ @Joe: Part of the point is that you don't need to do anything special to have infinite sets; there's just no limit on how many $a$ there can be such that $a \in b$. But it's far from clear how to define a theory that allows for infinite tuples. Should they be, in effect, indexed by ordinals, or by ordered sets, or what? And how do you define such things having only tuples to work with in the first place? $\endgroup$ Jul 31 at 21:36
14
$\begingroup$

The simpler a kind of object is, the more impressive its expressive power becomes. Sets are more compelling than tuples as an answer to the question, "How structurally simple can we make the foundations of mathematics?" Now that may not be a question one cares about - in particular, structural simplicity is often at odds with actual usability, and moreover one might reasonably reject simplicity as an inherent virtue in this context at all - but it is a meaningful question. And the early history of modern logic (especially around logicism) highlights this question.

So is there a problem with taking tuples - or even more complicated objects - as our "ground objects" for founding mathematics? Well, it depends on exactly what our desiderata of that foundational project are. Certainly there's no fatal obstacle, in the sense that from a technical perspective a tuple-based approach will be as safe and expressive as a set-based approach, but we might still have additional reasons to prefer the sets-based approach.

For what it's worth, I believe that simplicity-of-base-objects as a foundational criterion has lost a lot of steam over the last few decades, especially outside of the mathematical logic community: the notion of structural foundations of mathematics has grown in popularity.

$\endgroup$
7
  • $\begingroup$ Thanks for this answer, Noah. Regarding your last point, do you have any examples of well-known structural foundational systems? Do they have any advantages/disadvantages over $\mathsf{ZFC}$? $\endgroup$
    – Joe
    Jul 31 at 21:20
  • 3
    $\begingroup$ @Joe: One direction is "type theories" -- practically every computer-verified proof system is based on one, and in many cases there's a tight interplay between the design of the proof system and the software there implements it. Their great advantage is that they offer a much better alignment between how mathematics for human readers is actually written and how it looks when translated into the type theory, than a rendering into ZFC proofs would be. (Which is not to say that they map directly to conventional prose proofs; the best way to construct such systems is an active area of research). $\endgroup$ Aug 1 at 11:48
  • 3
    $\begingroup$ A different but related direction is category theory, which offers some neat tools for structuring and generalizing the design space of type theories. It comes at a cost of added abstraction, and the jury is still out on whether that abstraction is too much to be practical or not. (Saying things in set theory can tend to bury you in detail so you can't see the forest for individual twigs and leaves, whereas going to category theory can feel like you still can't speak about the forest you're interested in, but have to work with general properties of vegetation-classified landscape types). $\endgroup$ Aug 1 at 11:57
  • 1
    $\begingroup$ I think you should clarify what you mean by "tuple", because most mathematicians I know (and myself) consider tuples to have finitely many items each, so I do not see how you can encode an infinite set as any kind of tuple. $\endgroup$
    – user21820
    Aug 1 at 13:08
  • 1
    $\begingroup$ But why would sets be inherently “simpler” than tuples? $\endgroup$ Aug 1 at 15:10
4
$\begingroup$

Sets can be infinite, and there are different cardinalities of infinite sets; we know by Cantor's diagonal argument that there are "more" real numbers than natural numbers, so not every set can be indexed by the natural numbers. Therefore, many sets including the set of real numbers simply cannot be represented as an infinitely long tuple.

There's some talk in the comments about how you could define tuples to be indexed by an arbitrary ordinals, but in that case it seems to me that infinite tuples would not be primitive objects at all; they would be defined in terms of other things (ordinals and functions).

$\endgroup$
11
  • 1
    $\begingroup$ If one were to try and base all of mathematics on tuples, one would have to write down an axiomatic theory of tuples. I imagine these including statements that can be interpreted along the lines of "for any tuple there exists a tuple of all its sub-tuples" and "an infinite tuple exists". I imagine that, if such a theory were set up correctly, an analog of Cantor's result would exist, but stated purely in terms of tuples rather than sets. $\endgroup$
    – Nathaniel
    Aug 1 at 14:49
  • $\begingroup$ @Nathaniel The main distinction between a set and a tuple is that the elements of a tuple have indices. The elements of the set of real numbers cannot be indexed by the natural numbers. That is the problem. As for your axiom, you cannot properly define "a tuple of all of its subtuples" without saying which subtuples occur at which indices. If an analogue of Cantor's diagonal argument is possible in your theory founded on tuples, then your theory is inconsistent; an infinite tuple must permit a surjection from the natural numbers to its components, namely the one which maps $i$ to $x_i$. $\endgroup$
    – kaya3
    Aug 1 at 15:45
  • $\begingroup$ Clearly if you define a tuple in terms of an index set then you have to define sets first. If you were going to try and base all of mathematics on tuples rather than sets that wouldn't make sense, so it's pretty clear that you'd have to define tuples a different way. Personally, I think it would be possible do that and still have the definition correspond intuitively to what I think of the word "tuple" as meaning, or rather to a generalisation of it that isn't limited to a finite (or countable) number of items. YMMV, but you could always use another word if "tuple" bothers you. $\endgroup$
    – Nathaniel
    Aug 1 at 16:01
  • $\begingroup$ @Nathaniel If you're willing to give up the ordering/indexability of the tuple in order to allow for uncountably infinite tuples, then the other word you should use for them seems to be "sets". $\endgroup$
    – kaya3
    Aug 1 at 16:06
  • $\begingroup$ I don't see why giving up on countability should entail giving up on ordering. $\endgroup$
    – Nathaniel
    Aug 1 at 16:06
2
$\begingroup$

The mainly reason why set theory chose sets not natural mathematical objects (such as ordered pair, relations, functions, numbers and so on) as a base is: almost all the mathematical objects in modern mathematics can be reduced to sets, or the existence of almost all the mathematical objects can appeal to axioms of set theory for which $\mathsf{ZFC}$ is usually considered. And the reason why we pursuit such a general goal is because of the third mathematical crisis which is led by Russell paradox.

In fact, before the third mathematical crisis, set theory is developed as naive set theory and after that into axiomatic set theory. Naive set theory treat many natural mathematical objects as a base while axiomatic set theory chose sets.

Almost all the mathematicians just want to get a solid foundation to choose sets as a base in their thought which brings almost nothing to their mathematical practice because the sets as a base are too general, and so they still do what they do as usual in their mathematical practice.

$\endgroup$
3
  • 3
    $\begingroup$ ‘almost all the mathematical objects in modern mathematics can be reduced to sets’: this is circular, in effect saying ‘set are taken as primitive objects because everything else can be represented as a sets, which are primitive objects’. What is asked is why the same couldn’t be done with tuples instead of sets. $\endgroup$ Aug 1 at 12:54
  • $\begingroup$ @user3840170: And what Nate asked back is "How do you define an infinite tuple?". $\endgroup$
    – user21820
    Aug 1 at 13:11
  • $\begingroup$ @user3840170 In fact, tuples are finite, and we "call" infinite tuples as infinite sequences, otherwise the concepts of tuples and sequences are the same one. And we usually define infinite sequences to be some kind of functions, for example we define $\langle S_i\mid i\in\mathbb{N}\rangle$ to be the function $f(i)=S_i$. $\endgroup$
    – M. Logic
    Aug 1 at 16:27

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.