Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Sets

• set : an unordered collection of objects
• objects in the set : members, or elements
• \(S = {a, b, c, d} = {a, b, a, b, c, d}\) (can repeat)
• \(S = {a, b, c, d, … , z}\)
• Important Set :
• Set - Builder Notation : \(S = {x | P(x)}\)
• universal set / empty set

Russell’s Paradox: S is a set of all sets are not members of themselves, Is S a member of itself?

Note

sets can be elements of sets.

a empty set isn’t a set containing a empty set

• equality
• subset : \(\forall x \in A, x \in B \to A \subseteq B\)
• the proof of subset
• set cardinality : \(|A|\)

Note

\[|\emptyset| = 0\]

\[|\emptyset| = 1\]

• power sets : the set of all subsets of set \(A\), denoted \(P(A)\)

• tuples: \((a_1, a_2, …, a_n)\) (when \(n = 2\) , it also called ordered pair)

  • Cartesian Product : \(A \times B = \{(a, b) | a \in A \land b \in B\}\)

  Note

  a subset of Cartesian Product is called relation

• Truth Sets of Quantifiers : \(\{x \in D | P(x)\}\)

Set Operations

• Union : \(A \cup B\)
• Intersection : \(A \cap B\)
• Complement : \(\bar A\)
• Difference : \(A - B\)
• Inclusion-Exclusion : \(|A \cup B| = |A| + |B| - |A \cap B|\)
• Set Identities : use set to replace proportion in proportion laws.
• the proof of identity
• \(A\subseteq B \land B \subseteq A\)
• use set identities
• list all elements inbound each set
• Generalized unions and intersections
• using bit strings to represent sets.

Functions

• functions : \(f : A\to B, f(a) = b\)

Note

also can defined by a subset of A x B

• \(A\) : domain of \(f\)
• \(B\) : codomain of \(f\)
• \(b\) : image of \(a\) under \(f\)
• \(a\) : preimage of \(b\) (can be a set)
• range : all images of points in \(A\) under \(f\) , denoted \(f(A)\)
• representing:
• explicit statement of the assignment
• a formula
• a computer program
• injection / one-to-one : for all preimage is only one element
• surjection / onto : \(f(A) = B\)
• bijection / one-to-one corresponding : injection and surjection
• proof of injection / surjection / bijection
• inverse function : exist when \(f\) is a bijection
• composition : \(f(g(x))\)
• graphs of functions : 可视化形式 (与图论的图不同)
• floor / ceiling function
• factorial function :

Note

\[n! \sim \sqrt{2 \pi n} * (\frac{n}{e}) ^ n\]

• partial functions
• \(a\) in \(A\) but not in domain of definition of \(f\), called undefined
• domain of definition = \(A\), called total function

Sequences and Summations

• term : the image of \(N\)
• arithmetic
• string :

Note

empty string : \(\lambda\)

• recurrence relation
• fibonacci sequence
• closed formula : a formula for the nth term of the sequence generated by a recurrence relation.
• summations : \(\sum_{i \in S} a_i\)

Cardinality of Sets

• |\(A| = |B| \leftrightarrow \text{exist bijection between A and B}\)
• countable : a set is either finite or has the same cardinality as the set of positive integer \(Z^+\). \(|Z^+| = \aleph_0\)

• properties :

  • any two set satisify \((|A| = |B|) \lor (|A| > |B|) \lor (|A| < |B|)\)
  • \((|A| \leq |B| \land |A| \geq |B|) \to |A| = |B|\)

  Note

  pairs of integers is countable (螺旋型展开)

  • no infinite set has a smaller cardinality than a countable set
  • the union of two countable sets is countable
  • the union of finite numbers of countable sets is countable
  • the union of countable number of countable sets is countable
  • uncountable : \(|R| = \aleph_1\)

Matrices

• matrix : a rectangular array of numbers. A matrix with \(m\) rows and \(n\) columns is called an \(m \times n\) matrix.

• arithmetic : has mentioned in LA course.

• zero-one matrices : a matrix all of whose entries are either \(0\) or \(1\)

• join : the join of \(A\) and \(B\) is \(A \lor B = \{c_{ij} = a_{ij} \lor b_{ij}\}\)

• meet : the meet of \(A\) and \(B\) is \(A \land B = \{c_{ij} = a_{ij} \land b_{ij}\}\)

• boolean product : the boolean product of \(A\) and \(B\) is \(A \odot B = \{ c_{ij} = \bigvee_{k=1}^K a_{ik} \land b_{kj}\}\)

评论