Matters of notation with regard to Sipser
Notation of sets
Depending on when and with whom you took CS 1640 Discrete Structures (formerly CS 064), or MATH 2055 Fundamentals of Mathematics (formerly MATH 052), you may notice some minor differences in notation when reading Sipser.
For example, Sipser uses \mathcal{N}, \mathcal{Z}, \mathcal{Q}, and \mathcal{R} for natural numbers, integers, rationals, and reals, respectively. In other courses, you may have seen \mathbb{N}, \mathbb{Z}, \mathbb{Q}, and \mathbb{R} for the same sets. I will use the latter (it’s easier to write the latter on blackboard or whiteboard and maintain legibility, which is how these symbols arose in the first place). You should understand that these two notations are interchangeable (but shouldn’t ever be mixed).
Inclusion
Sipser writes A \subseteq B to indicate inclusion of A in B. That is, A \subseteq B if and only if every element of A is also an element of B. This leaves open the possibility of A = B. Sipser also writes A \subsetneq B to signify that A is strict subset of B, that is, A is a subset of B and A \neq B. Other authors use A \subset B to signify a strict subset. I will try to use Sipser’s \subsetneq but may occasionally lapse into \subset. Where this occurs \subset should be read as \subsetneq. That is, A \subset B means that A is a strict subset of B (they are not equal).
Why Sipser includes certain notation or fundamentals
You might be wondering why we concern ourselves with certain notation or fundamentals. What follows includes some motivation (but there are many other examples).
Why do we care about sets?
In this course, we’re going to learn about languages—regular languages, context-free languages, recursively enumerable languages. We’ll see that a language is a set of strings (often but not always bitstrings).
We’re going to be asking questions like “Is such-and-such string, s in some language, \mathcal{L}?” That’s a matter of membership in a set.
We’re also going to ask if a string, s, is in two different languages, \mathcal{L}_1 and \mathcal{L}_2. That is, is the string in the language \mathcal{L}_1 and in the language \mathcal{L}_2. That’s asking if s is in the intersection \mathcal{L}_1 \bigcap \mathcal{L}_2.
We’re also going to ask if a string, s, is in either of two different languages. That’s asking if s is in the union \mathcal{L}_1 \bigcup \mathcal{L}_2.
Questions like this will be frequent.
Why do we care about Cartesian products?
Sipser gives the notation of a set, A crossed with itself k times, e.g.
\overbrace{A \times A \times A \times \ldots \times A}^k = A^k.
We’ll see this quite a bit when considering strings. “Strings?” you ask, “What does this have to do with strings?” Well, say we have some set of symbols called an alphabet. In this course, we’ll use \Sigma to denote an alphabet. Then \Sigma^5 would be the Cartesian product \Sigma \times \Sigma \times \Sigma \times \Sigma \times \Sigma. That’s the set of all possible strings of length five. We’ll see this notation, \Sigma^*, to denote all possible strings that can be constructed from the alphabet \Sigma, including the empty string.
This is one reason why we care about notation for Cartesian products.
Why do we care about tuples?
Sipser speaks of sequences, which are ordered collections of objects. Several definitions of automata involve tuples. You don’t need to worry about the details yet, but the definition of a deterministic finite automata is a 5-tuple, a pushdown automaton is a 6-tuple, and a Turing machine is a 7-tuple.
It’s also the case that strings, deep down, are tuples. ('c', 'a', 't'), ('d', 'o', 'g'), ('b', 'a', 'n', 'a', 'n', 'a').
We’ll also see functions which accept multiple arguments (a tuple of arguments), and which return multiple values (a tuple of values).
Copyright © 2024–2025 Clayton Cafiero