1 Notation
This chapter recalls the standard (and non-standard) notations we use in this set of notes.
This chapter is not meant to be read exhaustively, but instead used as a reference for doubts on notation used. Skim it and focus on notations that you are unsure about (that might be slightly different from what you are used to). If you are really not familiar with some of the notations used here, and ask for help.
1.1 Miscellaneous notation
| Notation | Meaning |
|---|---|
| \mathsf{value}_{2}(w) | the natural number represented by the binary string w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^*. In particular, \mathsf{value}_{2}(\textcolor{darkred}{\mathtt{0}}w)=\mathsf{value}_{2}(w), \mathsf{value}_{2}(w\textcolor{darkred}{\mathtt{0}})=2\mathsf{value}_{2}(w), and \mathsf{value}_{2}(w\textcolor{darkred}{\mathtt{1}})=2\mathsf{value}_{2}(w)+1. |
| \lfloor x \rfloor | for x\in \mathbb{R}, \lfloor x \rfloor is the largest integer smaller or equal x. For example, \lfloor \pi\rfloor = 3. |
| \binom{S}{k} | for a set S and k\in \mathbb{N}, \binom{S}{k} is the set of all subsets of S of size k. For example, \binom{\{1,2,3\}}{2}=\{\{1,2\},\{1,3\},\{2,3\}\}. If |S|=n, the set \binom{S}{k} has size \binom{n}{k}=\frac{n!}{k!(n-k)!}. |
1.2 Logic
In this course we use logic formalism to describe properties of sets. You should be already familiar with the notation.
| Notation | Meaning |
|---|---|
| P\lor Q | P or Q: at least one between P and Q is true. |
| P\land Q | P and Q: both P and Q are true. |
| \lnot P | not P: the opposite truth value of P. |
| P\to Q | P implies Q: if P is true, the Q is also true Q. It is logically equivalent to Q\lor \lnot P. |
| P\leftrightarrow Q | P if and only if Q: the same as (P\to Q)\land (Q\to P). |
| \forall x\, P(x) | the property P holds for every x. It is logically equivalent to \lnot (\exists x\,\lnot P(x)). |
| \exists x\, P(x) | the property P holds for some x. It is logically equivalent to \lnot (\forall x\,\lnot P(x)). |
Exercise 1.1 (De Morgan’s law) Argue that \lnot (P\lor Q)\equiv \lnot P \land \lnot Q and \lnot (P\land Q)\equiv \lnot P \lor \lnot Q\ , where \equiv means the two expressions are logically equivalent, i.e. they always take the same truth values.
1.3 Sets
There is a whole branch of mathematics dedicated to study sets axiomatically. For this course the so-called naïve set theory is enough.
| Notation | Meaning |
|---|---|
| x\in S | x is an element of the set S. |
| \{x\in S :P(x)\} | the set of all elements x in S s.t. the property P holds on x. |
| \{E(x) :x\in S\} | the set of all elements of the form E(x) for x\in S. For example \{2n+1 :n\in \mathbb{N}\} is the set of all odd natural numbers. |
| \{xy\in A :P(x,y)\} | for a set A and a predicate P, is shorthand for \{w\in A :\exists x,y\ w=xy \land P(x,y)\}. |
| \emptyset | the empty set. Please do not write the number zero as \emptyset. |
| A\subseteq B | the set A is contained in B. A is a subset of B. For sets, A=B is the same as A\subseteq B and B\subseteq A. |
| A\subsetneq B | the set A is contained in B and A\neq B. |
| A\cup B | the union of A and B. This set contains only elements that are either in A or in B. |
| A\cap B | the intersection of A and B. This set contains only elements that are both in A and in B. |
| A\setminus B | the difference of A and B. This set contains only elements that are in A but not in B. |
| A\Delta B | the symmetric difference of A and B, it is the same as (A\setminus B)\cup (B\setminus A) |
| A\times B | the Cartesian product of A and B. This set contains only ordered pairs of elements (a,b) for all a\in A and b\in B. |
| \mathscr{P}(A) | the set of all possible subsets of A, also called power-set of A. |
| \mathbb{N} | the natural numbers \{0,1,2,\dots\}. |
| k\mathbb{N}+\ell | =\{kn+\ell :n\in \mathbb{N}\}. For example, 2\mathbb{N}+1 is the set of odd natural numbers. |
| \mathbb{Z} | the integers \{\dots, -2,-1,0,1,2,\dots\}. |
| \mathbb{Q} | the rationals \{\frac{p}{q} :p,q\in \mathbb{Z}\}. |
| \mathbb{R} | the reals: sequences of digits infinite on the right and with a single “.” somewhere, e.g. \pi=3.141592653\cdots. |
Exercise 1.2 (De Morgan’s law for sets) Argue that A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C) and A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)\ . Since they are equalities of sets, you need to argue \subseteq and \supseteq.
1.4 Functions and relations
| Notation | Meaning |
|---|---|
| R\subseteq A\times B | R is a relation on A and B. |
| f:A\to B | f is a (total) function from A to B, i.e. it associates each element of A to exactly one element of B. Formally, a relation f\subseteq A\times B is a function from A to B if for all a\in A, exists exactly one b\in B s.t. (a,b)\in f. This b is denoted as f(a). Unless specified otherwise, functions will always be total. |
| f is a partial function from A to B if it associates each element of A to at most one element of B. | |
| \mathrm{dom}(f) | the domain of a partial function f:A\to B is the set of all a\in A that have associated one element in B. |
| f(C) | the image of C is \{f(c) :c\in C\}. |
| \mathrm{img}(f)=f(A) | this is the image (or range) of f:A\to B. |
| f:A\to B is 1-to-1 (or injective) | when f(a)=f(a') implies a=a'. |
| f:A\to B is onto (or surjective) | when \mathrm{img}(f)=B. |
| f:A\to B is a one-to-one correspondence (or bijective) | if f is 1-to-1 and onto. |
| f^{-1} | the inverse of a function f:A\to B is the relation f^{-1}\subseteq B\times A given by f^{-1}=\{(b,a) :(a,b)\in f\}. |
| f^{-1}(S) | =\{a:f(a)\in S\}. |
Exercise 1.3 Show that if a (partial) function f:A\to B is injective, then f^{-1} is a (partial) function and also injective.
Exercise 1.4 Show that for every function f:A\to B and every C\subseteq B, f(f^{-1}(C))\subseteq C\subseteq f^{-1}(f(C))\ .