I’m given to understand that the order of the elements of a set doesn’t matter. So can I change the order of the set of natural numbers or any set of numbers ( $\mathbb{W,Z,Q,R}$ for that matter) as follows? $$ \mathbb{N} = \{ 1,2,5,4,3,\cdots \} $$ $$ \mathbb{N}= \{3,5,\cdots,78,1,9\} $$

If yes, is this is really problematic? If not, then why not?

PS: I know this is a silly question, but this has been in the back of my mind for a really long time.

  • 1
    Where do you see a problem? – lulu Aug 15 at 12:16
  • @lulu For instance, if I don't mention they are set of Natural Numbers and if I tell you to name the set, I'm pretty sure you would fail. – William Aug 15 at 12:17
  • 4
    Well, if you don't describe the set clearly then of course nobody will identify it. That's not surprising, nor is it problematic. – lulu Aug 15 at 12:18
  • 2
    There is, of course, a notion of an ordered set. That is, a set along with a binary relation that satisfies certain (fairly natural) properties. The natural numbers are normally thought of as ordered set. Of course, you are free to ignore that ordering and just think of the underlying set. – lulu Aug 15 at 12:19
  • What @lulu alludes to above is, I think, the proper way to think about this. The problem doesn't even come up when you consider that an ordered set is an ordered pair with certain properties. – Git Gud Aug 15 at 13:25
up vote 16 down vote accepted

It's true that sets are not ordered. As to whether you can 'change' the order, you cannot change something that is not there.

However you can define any ordering on them you want. For instance, we can order the naturals the usual way $$0,1,2,3,\ldots$$ or we can define an ordering where all the even numbers come first in their usual order, then the odd numbers $$ 0,2,4,6,\ldots, 1,3,5,7,\ldots.$$ There are many, many possibilities.

Also, the ordering needs to be defined unambiguously so we know exactly the order relationship between any two elements. For instance, I don't know what you mean when you write $$ \{3,5,...,78,1,9\}.$$ It's clear that you mean $9$ comes last (it is not a problem for an ordering to have a greatest element, even though in the two orderings I gave above, there was no greatest element), but I have no idea where $2$ goes in this ordering. If you just wrote this out of the blue, I wouldn't even be able to tell it was an ordering of the whole set of natural numbers and not just a subset.

Edit

Henning mentions an example in the comments that I think deserves mention in the answer, to reinforce the fact that there are many possibilities. Any enumeration of a countably infinite ordered set induces an order on the natural numbers. So, from the usual ordering of the rationals and an enumeration of the rationals, we get an ordering on the natural numbers that is dense, i.e. between any two numbers lies infinitely many others. We can’t even try to communicate this ordering as a list with some ellipses.

  • 1
    @HenningMakholm Perhaps it's more the ordering that's troubling me - is it meaningful to talk of an ordering of a countable set in which one element appears only after infinitely many others? – user3490 Aug 15 at 13:24
  • 1
    @user3490: Of course it is meaningful -- that's what spaceisdarkgreen is doing here, and there's nothing wrong with that. It is a perfectly well-defined ordering relation that satisfies all of the axioms ordering relations have to satisfy. It is even a well-order (of order type $\omega\cdot 2$). – Henning Makholm Aug 15 at 13:26
  • 2
    @user3490: More familiar, perhaps, is the fact that this happens with the usual order on $\mathbb Z$ or $\mathbb Q$. They are countable ordered sets where every element has infinitely many predecessors. (But they are not well-orders). – Henning Makholm Aug 15 at 13:28
  • 2
    @Adam Orderings are usually defined as binary relations - think about the implication of your statement for the real numbers, for example – dbx Aug 15 at 16:44
  • 1
    Wow, I'm just glad, I'm not the only one with this doubt. – William Aug 15 at 19:50

If you have the set $\{0, 1, 5, 3\}$, you can write it as $\{0, 3, 1, 5\}$. These are the same set, they contain the same elements.

And this is not changing the order of elements in the same set, as there is no order of elements in the same set. You're talking about the same set, just using different words. If I say

  • "My family contains me, my wife, and our daughter",

and then I say

  • "My family contains our daughter, my wife, and me",

I didn't change the order of members in my family, that doesn't even mean anything in this context! I just used different words to say the same thing.


But the crux of your question isn't about whether you can reorder the elements in a set, it really about what "..." means.

The "..." is a funny thing in mathematical texts. It's not really a mathematics concept at all, it's short of "dear reader, you know what I would write here if there was enough (possibly infinite) space and time, so let's just pretend I wrote it here".

When you write "$\{1, 2, 3, 4, ...\}$", the reader knows that if you had enough space, you'd write all positive integers there, so he knows you mean the set of positive integers. When you write "$\{1, 2, 5, 4, 3, ...\}$", the reader has no clue what you would write there. The problem isn't that you wrote the set in different order, the problem is that you weren't clear enough when you told the reader what you mean.


Again back to a (slightly clumsy) natural language example:

  • "I remember the names of the 3rd US president, the 4th US president, the 5th US president, and so on and so on."

The reader probably realizes you mean you know the names of all US presidents, except perhaps for the first two.

  • "I remember the names of the 30th US president, the 6th US president, the 17th US president, and so on and so on."

The reader has no clue what you mean.

In ZFC the two sets are the same set. I don't see why it is problematic.

  • For instance, if I don't mention they are set of Natural Numbers and if I tell you to name the set, I'm pretty sure you would fail. Secondly, what is ZFC? – William Aug 15 at 12:16
  • 4
    That's because $\{3,5,\cdots,78,1,9\}$ isn't a rigorous notation. You need to tell us what $\cdots$ means. – Kenny Lau Aug 15 at 12:17
  • ZFC is the axiomatic set theory "Zermelo-Fraenkel with axiom of choice". – Babelfish Aug 15 at 12:17

If set extension definition would required set to be ordered, it would imply that you wouldn’t be able to define in extension a set without an order.

Fortunately, you can define sets that are not ordered! Moreover, you may define several orders on a set. Which one would you use for its definition ?

The important point here is that in set theory, the things that most of think of as the "ordering" of the set $\mathbb N$ is encoded separately from the set itself. The set $\{1, 2, 3, ...\}$, on its own, is just a collection of abstract, meaningless objects denoted by the symbols $1$, $2$, $3$ and so on. Of course, in your head, you know that "$3$ is greater than $1$", but that information isn't contained in the expression $\{1, 2, 3, ...\}$. The set is just the objects, it doesn't tell you anything about any other relations between those objects.

In set theory, the information describing which numbers are considered "greater" than which others is encoded in a totally separate object called a relation. A relation is just a property of pairs of elements in a set: it's true for some pairs in the set, and false for other pairs. Here the relation is "$x$ is greater than $y$". It's true for the pair $(3, 2)$, false for the pair $(4, 7)$. This relation is a totally separate object from the set $\mathbb N$. It's as if $\mathbb N$ is just a big pile of symbols in the corner of the room, and the order relation is a book, separate from that pile, which tells you which numbers are "greater than" which others, like a kind of instruction manual.

So changing the notation of a set doesn't change the order, because we're not touching the order relation itself.

There are already great answers; this is just to add a visual dimension that might help.

In some cases (and only some cases), it may be helpful to think of a set as a bag. If this bag is not empty, then it should be pretty obvious now that how its contents are spatially related to each other does not matter in thinking of it just as a bag (in mathematics, we do not assume things not stated -- definitions are if and only if although they're mostly written with if alone, but the former is implied and the latter is just a convention). Therefore, we are thinking of a bag simply as a bag, no other conditions on it, so that it is clear that we do not care about, talk less of impose any arrangement on, its contents.

Whenever we wish to impose a certain kind of arrangement on its contents, we then have to qualify the word bag in referring to it; for example, if we can arrange its content in what is called a (linear) order (and this has been done), we then say that the bag is ordered, or that it is an ordered bag. However, we can impose even more structure on a set (these are not usually called orders -- this name is reserved only for linear orders), but we no longer regard it merely as a set, but a set with something else, say, a binary operation on it satisfying a set of conditions. Such kinds of structured sets are studied in abstract algebra, with such names as rings, lattices, etc.

In summary, we do not conceive of a set (not qualified) as already having some structure on it. As a set, we simply regard it as not more than a bag (in the cases when we can think of it so).

A set does not have order, but an enumeration of a set may have, and even non-enumerable sets like the real numbers may still be orderable.

You can reorder any listing of a finite set in any sense of the word. However, the definition of an infinite set is that it can be placed into bijection with a proper subset of itself. An enumeration is a bijection with natural numbers.

So if your enumeration "starts" with a bijection to a proper subset, you'll be running into logical problems. For example, ordering a listing of the naturals by starting with all odd numbers first is not going to work:

$$\{1, 3, 5, \dots, 2, 4, 6, \dots\}$$ does not work because you'll never actually get to 2: your "enumeration" will run out of steam doing just the odd numbers.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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