What is the relationship between sets, sequences, and functions?

Question

There's a practice problem I've been working on that's been bothering me. I've been searching for answers here and elsewhere online but I can't the answer I'm looking for. The question is as follows:

"Consider the abstract data types Sequence and Set, paying attention to how objects are treated mathematically. What is the relationship between sets, sequences, and functions?"

So far I know that sequences and sets can both consist of collections of elements, and functions are the operations that can be done on them, but that isn't enough to answer the question. What else am I missing?

Answer 1

Recall that

1. A set is a collection of distinct objets having a common property or properties.
2. the cartesian product of two sets is another set consisting of all possible ordered pairs having first component $x\in A$ and second component in $y\in B$. That is: $$A\times B=\{(x,y)\ \vert\ x\in A \ \text{and}\ y\in B\}.$$
3. Given two sets $A$ and $B$. A binary relation from $A$ to $B$ is any subset of $A\times B$ (the cartesian product of $A$ and $B$).

4. A map $F$ from $A$ to $B$ is a binary relation having no two distinct pairs with the same first coordinate. Usually you write $F:A\longrightarrow B$ to specify that $F$ is from $A$ to $B$. The common notation is $y=F(x)$ which means that: $$(x,y)\in F \ \Longleftrightarrow y=F(x)$$ The condition to be a map is the following: $$(x,y_1)\in F \ \text{and}\ (x,y_2)\in F \ \Longrightarrow y_1=y_2,\quad \forall x\in A,\ \forall y_1,y_2\in B.$$

   Let $F:A\longrightarrow B$ be a map, then each element $x\in A$ has one and only one image $y\in B$. In other words, that each input $x$ is related to exactly one output $y$.

5. Let $X$ be a non-empty set. A sequence of elements of $X$ is map $s$ from $\mathbb{N}$ to $X$. That is, the domain of $s$ is the whole set $N$ $$ s:\mathbb{N}\longrightarrow X $$ where $s_{n}:=s(n)\in X$, for all $n\in\mathbb{N}$. Recall that $$\mathbb{N}=\{1,2,3,\ldots\}$$ It's ok also to define $\mathbb{N}=\{0,1,2,3,\ldots\}$ depending how you prefer it.

Answer 2

The simplest is a set. It is a collection of elements. It doesn't matter how many times an element of a set is contained in that set. The order of the elements do not matter either.

A sequence is similar but here the order matters (and how often it is contained in the sequence).

A function is a thing that requires two sets $A$ and $B$. It basically assigns elements from $A$ to elements from $B$. The only restriction is that every element in $A$ can at most have at most one element from $B$ assigned to it.

Answer 3

A set is a collection of distinct elements. That is fine. That is what we learned early on, it is correct and we can use it as our basic concept. The only thing we can say about a set is whether specific elements are or are not members of it. Order is neither significant or meaningful and number of times an element appears in a set is meaningless; either an element is or is not a member of a set. Period. Okay, every thing we were taught is good.

We learned that a sequence was an ordered set in which elements may appear multiple times (or not) but the order or position matters. That is what we were taught. It is pure garbage. It's not our fault but --- it's garbage. Let's put pin in sequence and get back to them.

Functions. We were taught functions were a mapping from one set $X$ called the domain to another set $Y$ called the range (or codomain or image-- depends on your age and whether you went to a high school in California or not-- I kid... {I don't kid...}). That's fine as far as it goes. But the idea of "mapping" is not defined and doesn't bear any weight of scrutiny.

Given two sets $X$ and $Y$ then an ordered pair $(a,b)$ is a listing of an element from set $X$ listed in conjunction with an element of set $Y$. $X\times Y$ is the set of all possible ordered pairs.

A function $f:X\to Y$ is a subset $K$ of $X\times Y$ with the two condition that for ever $x \in X$ there is one and only one $(a,b)\in K$ so that $a = x$.

A sequence $S$ of elements of a set $X$ is a function $f:\mathbb N \to X$. That's it.