Sets and relations

Paul Schrimpf

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$

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 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 \}$

$\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

$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?

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 } \]

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