CS 135 Chapter 3.6 Notes

3.6 Cartesian Products
- An ordered pair of items is written (x, y)
- The Cartesian product of A and B, denoted A x B, is the set of all ordered pairs in which the first
entry is in A and the second entry is in B
- A x B = { (a, b) : a ∈ A and b ∈ B }
- A x B != B x A, unless A = B, or either A or B is empty
- If A and B are finite sets, then |A x B| = |A|⋅|B|




- An ordered triple is denoted (x, y, z)
- {0, 1}3 = { (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
- For n ≥ 4, an order list of n items is called an ordered n-tuple
- R^n, which is the set of all ordered n-tuples of real numbers
- R^2 is the set of all pairs (x, y) such that x and y are real numbers
- If A = {x, y}, the set A^2 would be {xx, xy, yx, yy}
- A sequence of characters is called a string
- The set of characters used in a set of strings is called the alphabet for the set of strings
- The length of a string is the number of characters in the string
- Empty string length is 0, denoted by the symbol λ
- {0, 1}0 = {λ}
- The concatenation of s and t is the adding of the two strings together (denoted as st)