Sets algebra and combinatorics

Sets 📚

Multicolumn

Blank

Concepts and Notation

• No order: $\{a,b\}=\{b,a\}$, (compared to a vector $(a,b)$ where order matters)
• Notation:
  • Implicit (Description): $A=\{x\in \mathbb{R}\mid 1\le x\le 4\}$
  • Explicit (Listing): $B=\{7,2,3,4,5\}$
• Subset ($\subset$): $A\subset B$ means $A$ is a subset of $B$.
  • $A\subset A$ (Every set is a subset of itself)
  • $\varnothing \subset A$ (The empty set is a subset of every set)

Standard Sets

$\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}$ …

• $\mathbb{N}$ := Natural Numbers $\{0,1,2,\dots \}$
• $\mathbb{Z}$ := Integers $\{\dots ,-2,-1,0,1,2,\dots \}$
• $\mathbb{Q}$ := Rational Numbers $\{\frac{p}{q}\mid p\in \mathbb{Z},q\in \mathbb{Z},q\ne 0\}$
• ${\mathbb{Q}}^{\prime }$ := Irrational Numbers (e.g., $\pi ,e,\sin (1),2^{\sqrt{5}}$)
• $\mathbb{R}$ := Real Numbers ($\mathbb{Q}\cup {\mathbb{Q}}^{\prime }$)
• $\mathbb{C}$ := Complex Numbers

Operations

• Union: $A\cup B$ (Elements in $A$ OR $B$)
• Intersection: $A\cap B$ (Elements in $A$ AND $B$)
• Difference: $A-B$ (Elements in $A$ but NOT in $B$)
• Disjoint: $A\cap B=\varnothing$ (No common elements)

Blank

Quantifiers

• $\forall x$ : “For all $x$”
• $\exists x$ : “There exists at least one $x$”
  • $\nexists x$ : “There does not exist an $x$” (Note: This is $\neg \exists x$)

Cartesian Product

• Two Sets: $A\times B:=\{(a,b)\mid a\in A,b\in B\}$ “The set of all ordered pairs”
  

• Squaring a Set: $A\times A:=\{(x,y)\mid x,y\in A\}$

• General Power: $A^2=\{(x,y)\mid x,y\in \mathbb{R}\}$ (Assuming $A=\mathbb{R}$)

• Triple Product: $A^3=\{(x,y,z)\mid x,y,z\in \mathbb{R}\}$ (Assuming $A=\mathbb{R}$)

Cardinality (Number of Elements)

• Cardinality of A: $|A|$
• Cardinality of Cartesian Product: $|A\times B|=|A|\cdot |B|$

---

Real Numbers representation 🔢

Multicolumn

Blank

Floating-Point Representation

$X=\pm a\cdot 10^e$
where $a$ is the significand (or mantissa), $e$ is the exponent, and:

• $a\in [1,10[$ (i.e., $1\le a<10$)
• $e\in \mathbb{Z}$ (the exponent is an integer)

Decimal Expansion

• Example: $0.3333\dots$

---

Multicolumn

Blank

Algebraic Concepts

Absolute Value

$|x|=\{\begin{array}{ll}x& \text{if }x\ge 0\\ -x& \text{if }x<0\end{array}$

Properties

• Multiplication/Division:
  $|x\cdot y|=|x|\cdot |y|$
  $\left|\frac{x}{y}\right|=\frac{|x|}{|y|},y\ne 0$
• Triangle Inequality:
  $|x+y|\le |x|+|y|$
• Reverse Triangle Inequality:
  $|x-y|\ge ||x|-|y||$
  (Note: The note shows two equivalent forms: $|x-y|\ge |x|-|y|$ and $|x-y|\ge |y|-|x|$)

Modulo

• $X\mathrm{mod}Y$ = Remainder
• It answers the question: “How many times does $Y$ fit into $X$? $⟹$ Remainder”

Combinatorics 📐

Factorial

• For $n\in \mathbb{N}$ (natural numbers):
  $n!=1\cdot \mathrm{2...}\cdot n$
• Base Case:
  $0!=1$

Blank

Pascal’s Triangle

The rows $n$ and columns $k$ of Pascal’s triangle give the values of the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

• $n\to$ (Row index, starting at 0)

• $k\to$ (Column index, starting at 0)

Binomial Coefficient

• For $k,n\in \mathbb{N}$ and $k\le n$:
  The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is defined as:
  $\left(\genfrac{}{}{0ex}{}{n}{k}\right):=\frac{n!}{k!(n-k)!}\in \mathbb{N}$

Binomial Theorem

The expansion of $(a+b{)}^n$ is given by the Binomial Theorem:
$(a+b{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$

Expanded Form:
$(a+b{)}^n=(\genfrac{}{}{0ex}{}{n}{0})a^n+(\genfrac{}{}{0ex}{}{n}{1})a^{n-1}{b}^1+(\genfrac{}{}{0ex}{}{n}{2})a^{n-2}{b}^2+\cdots +(\genfrac{}{}{0ex}{}{n}{n-1})a^1{b}^{n-1}+(\genfrac{}{}{0ex}{}{n}{n})b^n$