Skip to content

Chapter 2 Basic Structure: Sets, Functions, Sequences, Sums, and Matrices

2.1 Sets & 2.2 Set Operations

  • Set
    • unversal set \(U\)
    • empty set \(\emptyset\)
  • subset: \(A \subseteq B\)
  • equality of sets: \(A = B \leftrightarrow A \subseteq B \land B \subseteq A\)

  • proper subset: \(A \subset B \leftrightarrow A \subseteq B \land A \neq B\)

  • cardinality: \(|S|\)

  • Cartesian product: \(A \times B\)
  • finite/infinite

power set \(P(S)\)

  • \(P(S) = \{X | X \subseteq S\}\)
  • \(X \in P(S) => X \subseteq S\)
  • \(|P(S)| = 2^n\)

set operation

  • union: \(A \cup B\)
  • intersection: \(A \cap B\)
  • difference: \(A - B\)
  • symmetric difference: \(A \oplus B = (A \cup B) - (A \cap B) = (A - B) \cup (B - A)\)

  • complement: \(\overline{A} = \{x \in U | x \notin A\}\)

  • disjoint: \(A \cap B = \emptyset\)

set identities

the table

Question

\(S = \{\emptyset\}\), and what is \(P(S), P(P(S))\)?

answer
  • \(P(S) = \{\emptyset, \{\emptyset\}\}\)
  • \(P(P(S)) = \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}\)
  • Proving Set Identities
    1. Subset method
    2. Membership Tables
    3. Apply existing identities

2.3 Functions

  • function

  • domain/codomain/range

  • range \(\subseteq\) codomain

  • image/preimage

  • one-to-one(injective)

  • onto(surjective)

  • one-to-one correspondence(bijection): The two sets must have the same cardinality

  • composition: \((f \circ g)(a) = f(g(a))\)

  • take effect from right to left \(\leftarrow\)

Important Functions

  • floor function \(\lfloor x \rfloor\): \(\lfloor x \rfloor = n\) if and only if \(n \le x \lt n + 1\)
  • ceiling function \(\lceil x \rceil\): \(\lceil x \rceil = n\) if and only if \(n - 1 \lt x \le n\)

2.5 Cardinality of Sets

expansion: cardinality of finite sets -> cardinality of infinite sets

sets have the same cardinality
  • countable \(\aleph_0\): a set is either finite or has the same cardinality as the set of positive integers
  • uncountable: not countable
  • Theorem: If \(A\) and \(B\) are countable sets, then \(A \cup B\) is also countable
  • SCHRODER-BERNSTEIN THEOREM: If \(A\) and \(B\) are sets with \(|A| \le |B|\) and \(|B| \le |A|\), then \(|A| = |B|\)
countable sets

for \((x, y) \in N \times N\), let \(f(x, y) = \frac{(x+y)(x+y+1)}{2} + y + 1\)

  • \(|Q^+| \le |S|\)
  • \(|S| = |N|\)
  • \(N \subseteq Q^+ => |N| \le |Q^+|\)

so \(|Q| = |N|\), Q is countable

uncountable sets

=== \(R\)