Sets and relations

Paul Schrimpf

02 October, 2019

Sets

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

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