The difference between a sequence and a set

Question Detail: 

I am new to discrete mathematics and the theory of computation I am trying to learn and understand the terminology.

I am having a difficult time understanding the difference between a set and a sequence. I understand that unlike a set, in a sequence order and repetition does matter and sequences contain objects rather than elements or members. However, I don't see how sequences can be logically applied to the real world.

Can someone please give a clear and simple example of when a sequence would be used as opposed to a set and explain how is a sequence is different that a set?

I appreciate any clarification.

Asked By : MHZ

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7912

Answered By : Dmitri Chubarov

Your question uses a number of words, such as "logic" that might require clarification. In order to answer I should start with some preliminary definitions.

Consider a universe of objects. The objects have different properties. We do not know yet if each object can be identified. We say that all objects that share a certain property form a set (this statement is related to the notion of specification in Set Theory).

For instance in order to have a set of all sand particles you do not need to be able to identify each particle of sand. You just need to be able to distinguish them from objects that are not sand particles.

So a set is either an empty set or a set of all objects in our universe that share some common property. Two sets $A$ and $B$ are considered equal if an element $x$ belongs to $A$ if and only if $x$ belongs to $B$. (this statement is known as extensionality). It follows that removal of duplicates does not change a set.

In order to define a sequence we need to introduce natural numbers into our universe. Now a sequence is a mapping from the set of natural numbers into a set of objects. That is each number is associated with a unique object. (You need to be able to identify individual objects in order to define a sequence).

A sequence can also be considered as a set where each element has a special form. For example a sequence A, B, C, B, ... can be represented as a set

   { {1,{A}}, {2,{B}}, {3,{C}}, {4,{B}}, ... } 

Example

Now here is an example where a sequence can be used as opposed to a set. Suppose our universe consists of colored grains of sand. Assume each grain is either green or red. Then we could have only four different sets in our universe:

  {}, {G}, {R}, {G, R} 

and many higher order sets, such as

  {{G}}, {G,{R}}, ... etc. 

However we could form many infinite sequences without using higher-order sets:

  R, G, G, R, G, R, R, G, .... 

Programming

In programming languages some basic data structures, such as arrays or lists are sequences, that is you can refer to an element by its sequence number. Using such structures to model sets requires additional processing: identifying duplicates and keeping them in a sorted state.

A natural data structure to model sets is a hash table. This model handles duplicates efficiently, however computing a hash table that represents a union of two hash tables may have complexity proportional to the size of the hash tables.

Hope this clarifies the difference between sequences and sets.