7
$\begingroup$

I've wondered whether a list is the same as an ordered set (or multiset) in mathematics ?

Since a list can contain the same element more than once, the above can only be true for an ordered multiset ?

Sometime people speak about a empty list like it is an empty set ?

Why is it legal to use the $\in$ notation for a list, if it is not an ordered set (or multiset) ?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I think you mean

whether a list in computer science is the same as an ordered set (or multiset) in mathematics ?

And the answer is that mathematics doesn't have the notion of a list - that was created to organize and store data in structures in a computer.

Mathematics does have the notion of a Set, and it comes with the property that its elements are distinct. The notion of a Multiset also exists, and relaxes that property.

I'm pretty sure the distinction between List and Set exists in computer science because people wanted a term to describe a sequence of data (a "List") versus an unordered, unsequenced "Set", and because many lists are implemented in a way such that they are logically described as a List. (For example, Linked Lists are pretty a pretty obvious choice wherein each element literally points to the next one in the list).

The notation s $\in$ S is overloaded a lot (even on this site, where the formatting for it is "\in") to mean s "is in" S, despite the more formal s "is an element of the set" S.

You could say that a List is most closely related to a Multiset... until...multiset. Computer science overloads a lot of terms.

Wanted to include something about why computer science has so many shared yet different terms:

In CS a lot of their terms are overloaded because of guarantees we want to make. For example, in a list, there's a natural progression from one element to the next (somehow via pointers or data addresses or what) - in a Set, this may not be the case, but the notion of a Set still has its place in that it's valuable to have the concept of "distinct elements in some collection, even if their arrangement isn't assured". A lot of times you want to be able to tell other parts of code "Give me a data structure with the following guarantees" and by having different types (List, Set, Map, etc), you can enforce some properties of the data structure you're getting.

For example, maybe you don't care that the data is contiguous in memory, but you want to be able to move from one element of the list to the "next" according to an ordering. You want a List of some kind. Do you want to guarantee that each data element will be next to its logical neighbor in memory? Then ask for an Array instead. Do you not even care that you can get from one element to the next? Ask for a Set or Multiset or a HashMap. In addition to guarantees on organization, a lot of these structures make guarantees on the performance of various operations (inserting elements, fetching them, deleting them, etc). Wow big edit.

$\endgroup$
5
  • $\begingroup$ But in Linear Algebra books they use the notation $v_1,v_2, \ldots,v_n$ are linearly independent vectors (this is a list right ?). Or is it another notation for a set ? $\endgroup$
    – Shuzheng
    Apr 2, 2015 at 11:13
  • $\begingroup$ That's a "list" in the same way that the alphabet $a, b, ... , y, z$ is a "list". It's just a convenient notation for "you know, the stuff that happens between these places, you can fill it in yourself I'm just too lazy to write it all down". en.wikipedia.org/wiki/Ellipsis#In_mathematical_notation Literally, "and so forth". $\endgroup$
    – SubSevn
    Apr 2, 2015 at 11:16
  • $\begingroup$ Also I just realized your initial question may have been about the ellipsis and not about the List data type in computer science! Sorry for the wall of text if that is the case!!! $\endgroup$
    – SubSevn
    Apr 2, 2015 at 11:20
  • $\begingroup$ Thank you for your answer. But since Linear Algebra is purely mathematics, shouldn't it avoid using notation and terminology from computer science ? $\endgroup$
    – Shuzheng
    Apr 2, 2015 at 11:21
  • $\begingroup$ I think you have it the other way around actually - CS borrowed almost all their terminology from mathematics. And there is some (very little) argument about the terminology in CS, however it's still the best terminology we've got, and it does have a lot of useful overlap if sometimes introducing some minor (and generally correctable) confusion. $\endgroup$
    – SubSevn
    Apr 2, 2015 at 11:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .