preliminary_math_concepts

Preliminary math concepts

Sets

  • an unordered collection of unique/distinct objects, usually represented by numbers
  • Explicitly or implicitly defined
  • Explicit: describe every element of a set.
    • Binary set = {0, 1}
    • roman alphabet = {a, b, c, …, z}
  • Implicit: Abstract representation of a set, a set where you have to "do work"
    • \(\mathbb{N}\) = {1, 2, 3, …}
    • \(x \in U: P(x)\)
    • \(x \in \mathbb{N}:x\text{ a product of two disticnt primes\)

Special sets

  • \(\emptyset\): set with no elements (null set)
  • \(\mathbb{N}\): set with all natural numbers
  • \(\mathbb{Z}\): Set of all integers
  • \(\mathbb{Q}\): Set of all rational numbers
  • \(\mathbb{U}\): universal set

Set operations

  • \(\cup\): union
    • {1, 2} \(\cup\) {2} = {1, 2}
  • \(\cap\): intersection
  • \(2^A\): power set, every subset of A (including \(\emptyset\))
    • \(2^{|A|}\): number of subsets
  • \(|A|\): cardinality is the number of elements in set
  • \(A^c = \{x \in U, x \notin A\}\)
  • \(A \times B = \{(a, b) : a \in A, B \in B\}\)
  • \(|A \times B| = |A||B|\)
  • \(\{1,2,3\} - \{2\} = \{1, 2, 3\} \char`\\ \{2\} = \{1, 3\} \)

Excercises

  • help
  • Let A be a non-empty finite set. What is \

1

What is \(2^\emptyset\)

  • \(2^\emptyset = \emptyset\)

2

Let A be a non-empty finite set. What is \(A \times \emptyset\)

3

Prove that: A = B if and only if A \ B = B 

\A

  • \(A-B = \{x \in A, x \notin B\}\)
  • \(B-A = \{x \in B, x \notin A\}\)
  • if: \(\{x \in B, x \notin A\} = \{x \in A, x \notin B\}\)
  • then: \(\{x \in B, x \notin A, x \in A, x \notin B\} = \emptyset\)
  • if A = B then A-B = A-A = B-A = \(\emptyset\)
  • If A - B = B - A then A - B = \(\emptyset\) and B-A = \(\emptyset\)
  • therefore A = B if and only if A - B = B - A

Functions

A relationship between sets that transforms one set into an another set.

Total function

Every element in A is mapped to a point in B

  • \(A \rightarrow B\)

Partial function

Not every element in A is mapped to a point in B

  • \(A \rightsquigarrow B\)

Graphs

  • Set V of vertices or nodes
  • set E of unordered/ordered pairs of vertices called edges
  • Paths are an undirected path between nodes

Proofs

Induction

  • basis step: evalutate formula for n=1 and 2
  • Inductive Step: Assuming that forumula is true for \(F_1, ... F_{I-1}\).

Contradiction

  • assume that \(\neg P\) is true

  • prove \(\)

Alphabet

Finite set denoted by \(\sum\)

  • roman Alphabet {a-z}
  • binary alphabet {0,1}
  • \(\lambda\) is the empty string