The Central Idea
A set answers the question
Which elements are present?
An ordered structure can answer additional questions:
- In what order do the elements appear?
- Which element occupies a particular position?
- May an element appear more than once?
- How long is the structure?
- Can the structure continue indefinitely?
Tuples, strings, lists, and sequences are closely related ways to organize objects while preserving position.
Order Changes the Object
For sets,
\[ \{1,2,3\}=\{3,2,1\}. \]But for ordered structures,
\[ (1,2,3)\ne(3,2,1). \]The first entries differ, the second entries differ, and the third entries differ.
In an ordered structure, position is part of the mathematical information.
Repetition Can Matter
Sets ignore repeated listings:
\[ \{1,1,2\}=\{1,2\}. \]Lists and sequences do not.
\[ [1,1,2]\ne[1,2]. \]The first list has three positions, while the second has two.
This distinction is essential in counting arrangements, processing data, analyzing strings, and describing repeated states.
What Is a Tuple?
A tuple is a finite ordered collection of entries.
For example,
\[ (4,7,9) \]is a three-entry tuple.
A tuple with \(n\) entries is called an \(n\)-tuple.
Thus,
\[ (a_1,a_2,\ldots,a_n) \]is an \(n\)-tuple.
Ordered Pairs
A tuple with two entries is an ordered pair.
\[ (x,y) \]The first entry and second entry play distinct positional roles.
In general,
\[ (x,y)\ne(y,x) \]unless \(x=y\).
Ordered pairs appear in coordinate geometry, relations, graph edges, probability models, and Cartesian products.
Triples and Higher Tuples
A three-entry tuple is often called an ordered triple:
\[ (x,y,z). \]Higher tuples continue the same pattern:
\[ (a_1,a_2,a_3,a_4) \]is a \(4\)-tuple, while
\[ (a_1,\ldots,a_n) \]is an \(n\)-tuple.
Tuples are useful whenever a mathematical object is described by several coordinated attributes.
Equality of Tuples
Two tuples are equal only when they have the same length and corresponding entries are equal.
For example,
\[ (a,b,c)=(x,y,z) \]exactly when
\[ a=x,\qquad b=y,\qquad c=z. \]Equality is therefore positional.
Tuple Length
The length of a tuple is the number of positions it contains.
For
\[ T=(5,8,8,1), \]the length is
\[ \boxed{4}. \]Repeated values still occupy separate positions.
The Empty Tuple
An ordered structure may contain no entries.
The empty tuple has length \(0\) and is commonly written
\[ (). \]In computing and combinatorics, empty ordered structures are often important base cases for recursive definitions.
What Is a List?
A list is a finite ordered collection in which repetition is generally allowed.
One common notation is
\[ [a_1,a_2,\ldots,a_n]. \]For example,
\[ [3,5,3,8] \]is a list of length \(4\).
The term list is especially common in algorithms and computer science.
Tuple versus List
Tuples and lists are mathematically similar because both preserve order and repetition.
The distinction is often contextual rather than absolute.
A tuple commonly emphasizes a fixed collection of positional fields:
\[ (\text{name},\text{age},\text{score}). \]A list often emphasizes an ordered collection that may be processed, extended, shortened, or traversed:
\[ [12,7,9,4,15]. \]Different fields of mathematics and computing may use these terms somewhat differently.
Indexing
Indexing assigns positions to entries in an ordered structure.
For a list
\[ L=[10,20,30,40], \]one indexing convention may label positions as
\[ L_0=10,\quad L_1=20,\quad L_2=30,\quad L_3=40. \]Another convention may begin at \(1\):
\[ L_1=10,\quad L_2=20,\quad L_3=30,\quad L_4=40. \]The convention must be stated or understood from context.
Zero-Based and One-Based Indexing
In much of mathematics, indexing commonly begins with \(1\):
\[ a_1,a_2,a_3,\ldots \]In many programming languages and discrete models, indexing commonly begins with \(0\):
\[ a_0,a_1,a_2,\ldots \]Neither convention is inherently more correct.
What matters is consistency.
What Is a String?
A string is a finite sequence of symbols drawn from some specified alphabet.
If
\[ \Sigma=\{0,1\}, \]then examples of strings over \(\Sigma\) include
\[ 0,\qquad 1,\qquad 01,\qquad 1011,\qquad 000101. \]Strings are central in computer science, coding, automata, formal languages, cryptography, and digital representation.
Alphabet
In string theory and formal-language contexts, an alphabet is a finite set of allowed symbols.
For binary strings,
\[ \Sigma=\{0,1\}. \]For decimal digit strings,
\[ \Sigma=\{0,1,2,3,4,5,6,7,8,9\}. \]A string is formed by arranging symbols from the alphabet in order.
String Length
The length of a string \(w\) is often written
\[ |w|. \]If
\[ w=101101, \]then
\[ \boxed{|w|=6}. \]Here the vertical bars represent string length rather than set cardinality. Context determines the meaning.
The Empty String
The empty string contains no symbols.
It is commonly denoted by
\[ \varepsilon \]and has length
\[ \boxed{|\varepsilon|=0}. \]The empty string plays an important role in recursion, automata, formal languages, and concatenation.
Concatenation
Concatenation joins one string directly after another.
If
\[ u=101 \]and
\[ v=00, \]then
\[ \boxed{uv=10100}. \]The order matters:
\[ uv=10100 \]while
\[ vu=00101. \]Length under Concatenation
If strings \(u\) and \(v\) have lengths \(|u|\) and \(|v|\), then their concatenation has length
\[ \boxed{|uv|=|u|+|v|}. \]For example, if
\[ |u|=4 \]and
\[ |v|=7, \]then
\[ |uv|=11. \]Strings of Fixed Length
If an alphabet contains \(k\) symbols, then the number of strings of length \(n\) is
\[ \boxed{k^n}. \]For binary strings, \(k=2\).
Therefore the number of binary strings of length \(n\) is
\[ \boxed{2^n}. \]This is an early connection between ordered structures and combinatorial counting.
Example: Binary Strings of Length Three
Each of three positions may contain either \(0\) or \(1\).
Therefore,
\[ 2^3=8 \]strings are possible:
\[ 000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 110,\ 111. \]Position and repetition both matter.
What Is a Sequence?
A sequence is an ordered collection of terms indexed by consecutive integers, usually natural numbers or positive integers.
A sequence may be finite:
\[ 2,4,6,8 \]or infinite:
\[ 2,4,6,8,\ldots \]Sequence notation emphasizes how a term depends on its index.
A Sequence as a Function
Formally, a sequence can be viewed as a function whose domain is an ordered index set.
For an infinite sequence indexed by \(\mathbb{N}\),
\[ a:\mathbb{N}\to S. \]The value at index \(n\) is written
\[ a_n. \]Thus a sequence is not merely a row of values. It is a rule associating positions with terms.
Explicit Sequence Rules
An explicit rule gives a sequence term directly from its index.
For example,
\[ a_n=3n+1 \]with \(n=0,1,2,\ldots\) produces
\[ 1,4,7,10,13,\ldots \]Each term can be calculated without first computing earlier terms.
Recursive Sequence Rules
A recursive rule defines later terms using earlier terms.
For example,
\[ a_0=2, \] \[ a_{n+1}=a_n+3. \]This produces
\[ 2,5,8,11,14,\ldots \]Recursive structures will become central when we study recurrence relations, algorithms, trees, and state transitions.
Finite Sequences
A finite sequence contains a fixed number of indexed terms.
For example,
\[ (a_1,a_2,a_3,a_4,a_5) \]has length \(5\).
A finite sequence may be treated as a tuple when its length is fixed and its entries are considered simultaneously.
Infinite Sequences
An infinite sequence continues without a final term:
\[ a_0,a_1,a_2,a_3,\ldots \]Every individual term has a finite index, but the sequence has no last position.
This is the same countable organization developed in the previous lesson: the natural numbers provide the index set.
Constant Sequences
A sequence may repeat the same value forever.
For example,
\[ a_n=5 \]gives
\[ 5,5,5,5,\ldots \]The sequence is infinite even though it uses only one distinct value.
This is another reason to distinguish a sequence from the set of values appearing in that sequence.
Sequence versus Set of Terms
Consider the sequence
\[ 1,0,1,0,1,0,\ldots \]The sequence is infinite.
But the set of values that appear is only
\[ \{0,1\}, \]which is finite.
A sequence records positions and repetitions. A set records only distinct membership.
Substrings
A substring is a consecutive block of symbols inside a string.
If
\[ w=101101, \]then
\[ 110 \]is a substring because those symbols appear consecutively.
By contrast, choosing nonconsecutive positions produces a different concept, often called a subsequence.
Subsequences
A subsequence is formed by selecting terms from a sequence while preserving their original relative order.
From
\[ 2,4,6,8,10, \]one subsequence is
\[ 2,6,10. \]The selected terms need not be adjacent.
However, they may not be rearranged.
Prefix and Suffix
A prefix begins at the start of a string or list.
A suffix ends at the final position.
For
\[ w=110101, \]examples of prefixes include
\[ \varepsilon,\ 1,\ 11,\ 110, \]while examples of suffixes include
\[ \varepsilon,\ 1,\ 01,\ 101. \]Prefixes and suffixes are especially important in string algorithms and formal languages.
Lexicographic Order
Ordered structures can themselves be arranged according to a comparison rule.
Lexicographic order compares entries from left to right, much like dictionary order.
For binary strings of equal length,
\[ 001<010<011<100. \]Lexicographic order is useful for systematic enumeration and algorithmic searching.
Cartesian Products Produce Tuples
If \(A\) and \(B\) are sets, their Cartesian product is
\[ A\times B = \{(a,b):a\in A,\ b\in B\}. \]The elements of \(A\times B\) are ordered pairs.
If
\[ A=\{1,2\} \]and
\[ B=\{x,y,z\}, \]then
\[ |A\times B|=2\cdot3=6. \]Higher Cartesian Products
Repeated Cartesian products create higher tuples.
For a set \(A\),
\[ A^3=A\times A\times A \]contains ordered triples
\[ (a_1,a_2,a_3) \]with each \(a_i\in A\).
If \(|A|=k\), then
\[ \boxed{|A^n|=k^n}. \]This is the same counting pattern used for strings of length \(n\).
Strings as Tuples of Symbols
A string of length \(n\) over an alphabet \(\Sigma\) can be viewed as an \(n\)-tuple
\[ (s_1,s_2,\ldots,s_n) \]where every
\[ s_i\in\Sigma. \]Thus strings of length \(n\) correspond naturally to the Cartesian power
\[ \Sigma^n. \]This unifies string notation with tuple and product-set notation.
Variable-Length Strings
Let \(\Sigma^n\) denote the set of strings of length \(n\) over \(\Sigma\).
Then the set of all finite strings over \(\Sigma\) is written
\[ \Sigma^* = \bigcup_{n=0}^{\infty}\Sigma^n. \]The \(n=0\) case contributes the empty string \(\varepsilon\).
If \(\Sigma\) is finite and nonempty, then \(\Sigma^*\) is countably infinite.
Why All Finite Strings over a Finite Alphabet Are Countable
Suppose \(\Sigma\) is finite.
For each fixed length \(n\), the set
\[ \Sigma^n \]is finite.
We can list all strings by length:
\[ \Sigma^0,\ \Sigma^1,\ \Sigma^2,\ \Sigma^3,\ldots \]and list the finitely many strings inside each block.
Therefore all finite strings can be systematically enumerated.
Lists as Data Records
Ordered collections often represent data.
For example,
\[ [72,85,91,88] \]might represent four measurements recorded in chronological order.
Reordering the entries would change the historical record even though the same four values remain present.
This is why lists are appropriate when position carries meaning.
Tuples as Structured Records
A tuple may represent several attributes of one object.
For example,
\[ (\text{ID},\text{category},\text{quantity},\text{time}) \]may describe a transaction or event.
The positions have different meanings, so swapping entries would generally produce invalid data.
Sequences as Histories
A sequence can describe how a system changes over time.
Suppose a process visits states
\[ s_0,s_1,s_2,s_3,\ldots \]The sequence records the history of the system.
This perspective will later connect sequences to state transitions, random walks, Markov chains, algorithms, and dynamical processes.
Finite Words and Formal Languages
In formal-language theory, strings are often called words.
A language is a set of strings.
For example, over
\[ \Sigma=\{0,1\}, \]the collection of all binary strings ending in \(1\) is a language.
This distinction is important:
- a string is one ordered object;
- a language is a set of such strings.
Reversal
The reversal of a finite string or list places its entries in the opposite order.
If
\[ w=10110, \]then its reversal is
\[ \boxed{w^R=01101}. \]Reversal demonstrates again that position, not merely membership, defines an ordered structure.
Palindromes
A palindrome is a string that equals its reversal.
For example,
\[ 10101 \]satisfies
\[ w=w^R. \]Palindromes are simple examples of structural constraints on ordered objects.
Common Error: Treating a Tuple Like a Set
The tuples
\[ (1,2) \]and
\[ (2,1) \]are different.
The sets
\[ \{1,2\} \]and
\[ \{2,1\} \]are the same.
Brackets and context matter because they indicate different structures.
Common Error: Ignoring Repeated Entries
The lists
\[ [1,2,2,3] \]and
\[ [1,2,3] \]are not equal.
Their lengths differ, and the value \(2\) occupies an additional position in the first list.
Common Error: Mixing Indexing Conventions
Suppose a sequence is written
\[ a_n=2n+1. \]If indexing begins at \(n=0\), the first term is
\[ a_0=1. \]If indexing begins at \(n=1\), the first term is
\[ a_1=3. \]The rule alone is not always enough. The index domain must also be known.
Common Error: Confusing a Substring with a Subsequence
In the string
\[ 101101, \]the symbols in a substring must be consecutive.
A subsequence may skip positions as long as the remaining symbols preserve their original order.
Consecutive and order-preserving are not the same requirement.
Common Error: Assuming Concatenation Is Commutative
In general,
\[ uv\ne vu. \]For example,
\[ 10\cdot011=10011 \]as concatenated strings, while
\[ 011\cdot10=01110. \]Concatenation preserves left-to-right order and is generally not commutative.
Common Error: Confusing String Length with Numerical Value
The binary string
\[ 1011 \]has length
\[ |1011|=4. \]If interpreted as a binary numeral, it represents the decimal value \(11\).
Length and numerical value are different properties.
A Reliable Procedure for Reading an Ordered Structure
- Identify the type of object: tuple, list, string, or sequence.
- Determine whether order matters.
- Determine whether repetition is allowed or meaningful.
- Identify the indexing convention, if positions are indexed.
- Determine whether the object is finite or infinite.
- Identify the alphabet or underlying set of allowed entries.
- Distinguish the structure itself from the set of values appearing in it.
- Apply the operation appropriate to the structure.
Example: Comparing Four Structures
Consider
\[ \{1,2,2,3\}, \qquad (1,2,2,3), \qquad [1,2,2,3], \qquad 1223. \]The first expression is a set, so repetition disappears:
\[ \{1,2,2,3\}=\{1,2,3\}. \]The second is a tuple, the third is a list, and the fourth may be interpreted as a string over the alphabet
\[ \{1,2,3\}. \]In the last three structures, order and repeated positions are preserved.
Practice 1: Tuple Equality
Are the tuples
\[ (2,5,7) \]and
\[ (2,7,5) \]equal? Explain.
Practice 2: List Length
Find the length of
\[ [4,4,1,9,4,2]. \]Practice 3: String Length
Find
\[ |10100101|. \]Practice 4: Concatenation
Let
\[ u=101 \]and
\[ v=11. \]Find \(uv\) and \(vu\).
Practice 5: Counting Strings
How many binary strings of length \(5\) exist?
Practice 6: Sequence Rule
Let
\[ a_n=4n+2 \]for \(n=0,1,2,\ldots\).
Write the first five terms.
Practice 7: Recursive Sequence
Let
\[ a_0=3 \]and
\[ a_{n+1}=2a_n. \]Write \(a_0,a_1,a_2,a_3,a_4\).
Practice 8: Subsequence
Is
\[ 2,6,10 \]a subsequence of
\[ 2,4,6,8,10? \]Explain.
Practice 9: Strings over an Alphabet
Let
\[ \Sigma=\{a,b,c\}. \]How many strings of length \(4\) can be formed over \(\Sigma\)?
Practice 10: Distinguishing Structures
Explain why
\[ \{1,1,2\} \]and
\[ [1,1,2] \]contain different kinds of information.
Practice Answers
Practice 1
No. Tuple equality is positional:
\[ \boxed{(2,5,7)\ne(2,7,5)}. \]The second and third entries occur in different positions.
Practice 2
There are six positions:
\[ \boxed{6}. \]Practice 3
The string contains eight symbols:
\[ \boxed{|10100101|=8}. \]Practice 4
\[ \boxed{uv=10111} \]while
\[ \boxed{vu=11101}. \]Concatenation is generally not commutative.
Practice 5
Each of five positions has two choices:
\[ \boxed{2^5=32}. \]Practice 6
Substitute \(n=0,1,2,3,4\):
\[ \boxed{2,6,10,14,18}. \]Practice 7
Double each preceding term:
\[ \boxed{3,6,12,24,48}. \]Practice 8
Yes. The terms \(2\), \(6\), and \(10\) appear in the original sequence in that same relative order, even though intermediate terms are skipped.
Practice 9
There are three choices for each of four positions:
\[ \boxed{3^4=81}. \]Practice 10
The set ignores repetition, so
\[ \{1,1,2\}=\{1,2\}. \]The list preserves all three positions:
\[ [1,1,2]. \]Thus the list records order and repeated entries that the set does not.
What to Remember
- Ordered structures preserve positional information.
- Tuples are finite ordered collections of entries.
- Lists preserve order and generally allow repetition.
- Strings are finite sequences of symbols from an alphabet.
- Sequences are indexed ordered collections and may be finite or infinite.
- Indexing may begin at \(0\) or \(1\), depending on convention.
- Concatenation joins ordered structures and generally is not commutative.
- A subsequence preserves relative order but may skip positions.
- A string of length \(n\) over a \(k\)-symbol alphabet has \(k^n\) possibilities.
- The same values can define different objects when their order or repetition changes.
The most important distinction is: a set records membership, while an ordered structure records membership together with position.
Where We Go Next
Once ordered objects are available, we can ask how they may be arranged, selected, divided, or grouped.
The next lesson, Arrangements, Selections, and Partitions, develops these basic ways of constructing discrete objects from collections of available elements.