Sets and relations
Paul Schrimpf
02 October, 2019
Definition & Notation
- Well-specified collection of elements
- set \(A\), element \(a \in A\)
- Example: \[
A = \{4, 5, 6 \} = \{ n \in \mathbb{N} : 3 < n < 7 \}
\]
Operations & relations
- Union: \(A \cup B = \{x: x\in A \text{ or } x \in B\}\).
- Intersect: \(A \cap B = \{x: x \in A \text{ and } x \in B\}\).
- Minus: \(A \setminus B = \{ x: x\in A \text{ and } \not\in B \}\)
- Product: \(A \times B = \{(x,y): x \in A, y \in B \}\)
- Power set: \(\mathcal{P}(A) =\) set of all subsets of \(A\)
- Subset \(A \subseteq B\) means that if \(a\in A\) then \(a \in B\)
- \(A \subset B\) means \(A \subseteq B\) and \(\exists b \in B\) such that \(b \not\in A\)
Relations
- relation on two sets \(A\) and \(B\) is any subset of \(A \times B\), \(R \subseteq A \times B\). We usually denote relations by \(a \sim_R b\) if \((a,b) \in R\)
- Example: \(A=B=\mathbb{R}\), \(<\) is associated with \(R_{<} = \{(a,b) \in \mathbb{R}^2 : a<b \}\)
Equivalence Relation
- equivalence relation is
- relexive: \(a \sim_R a\) \(\forall a \in A\)
- transitive: \(a \sim_R b\) and \(b \sim_R c\) implies \(a \sim_R c\)
- symmetric: \(a \sim_R b\) implies \(b \sim_R a\),
- partitions \(A\) into equivalence classes, \(\sim(x) = \{a \in A: a \sim x \}\)
Weak order
- \(\preceq\) is a weak order if
- relexive: \(a \preceq a\) \(\forall a \in A\)
- transitive: \(a \preceq b\) and \(b \preceq c\) implies $a $c
- complete: for any \(a, b \in A\), either \(a \preceq b\) or \(b \preceq a\) (or both)
- Example: preference relation
Pareto order
- \(n\) individuals, preferences \(\succeq_i\)
- Pareto order: \[
x \succeq^P y \text{ if } x \succeq_i y \text{ for all } i=1,...,n
\]
- transitive? reflexive? complete?
Social choice rule
- Combines preferences into single weak order \(F(\succeq_1, ..., \succeq_n) = \succeq\)
- Completes Pareto order if \(x \succeq^P y\) implies \(x \succeq y\)
Examples
- Binary voting
- social choice rule is determined by majority vote on each pair \[ x \succeq y \iff x \succeq_i y \text{ for at least $(n+1)/2$
individuals } \]
Examples
- Majority voting
- Each person votes for most preferred outcome
- Social choice rule ranks by number of votes
- Ties broken by number of votes for second most preferred, then third, etc
Social choice rule