2.4: Sets are not arrays

If you’ve done some computer programming, you might see a resemblance between sets and the collections of items often used in a program: arrays, perhaps, or linked lists. To be sure, there are some similarities. But there are also some very important differences, which must not be overlooked:

• No order. As previously mentioned, there is no order to the members of a set. “{Dad, Mom}" is the same set as “{Mom, Dad}". In a computer program, of course, most arrays or lists have first, second, and last elements, and an index number assigned to each.

• No duplicates. Suppose \(M\) is the set of all males. What would it possibly mean to say \(M\) = {T.J., T.J., Johnny}? Would that mean that “T.J. is twice the man that Johnny is"? This is obviously nonsensical. The set \(M\) is based on a property: maleness. Each element of \(\Omega\) is either male, or it isn’t. It can’t be “male three times." Again, in an array or linked list, you could certainly have more than one copy of the same item in different positions.

• Infinite sets. ’Nuff said. I’ve never seen an array with infinitely many elements, and neither will you.

• Untyped. Most of the time, an array or other collection in a computer program contains elements of only a single type: it’s an array of integers, or a linked list of Customer objects, for example. This is important because the program often needs to treat all elements in the collection the same way. Perhaps it needs to loop over the array to add up all the numbers, or iterate through a customer list and search for customers who have not placed an order in the last six months. The program would run into problems if it tried to add a string of text to its cumulative total, or encountered a Product object in the middle of its list of Customers. Sets, though, can be heterogeneous, meaning they can contain different kinds of things. The Davies family example had all human beings, but nothing stops me from creating a set \(X\) = { Jack Nicholson, Kim Kardashian, Universal Studios, 5786, \(\bigstar\) }.

  I don’t press this point too hard for a couple of reasons. First, most programming languages do allow heterogeneous collections of some sort, even if they’re not the most natural thing to express. In Java, you can define an ArrayList as a non-generic so that it simply holds items of class “Object." In C, you can have an array of void *’s — pointers to some unspecified type — which allows your array to point to different kinds of things. Unless it’s a loosely-typed language, though (like Perl or JavaScript), it sort of feels like you’re bending over backwards to do this. The other reason I make this distinction lightly is that when we’re dealing with sets, we often do find it useful to deal with things of only one type, and so our \(\Omega\) ends up being homogeneous anyway.

Perhaps the biggest thing to remember here is that a set is a purely abstract concept, whereas an array is a concrete, tangible, explicit list. When we talk about sets, we’re reasoning in general about large conceptual things, whereas when we deal with arrays, we’re normally iterating through them for some specific purpose. You can’t iterate through a set very easily because (1) there’s no order to the members, and (2) there might well be infinitely many of them anyway.