1. Sets, Relations, and Preferences

Key words:

• Set Theory
• Binary Relation
• Group
• Field
• social choice

1.1 Elements of Set Theory

• the Universal Set: $\mathcal{U}$
• intersection: $A \cap B$
• union: $A \cup B$
• null set/ empty set: $\Phi$
• negation/complement of A in $\mathcal{U}$: $\mathcal{U} \backslash A = \bar { A } = \{ x : x \text { is in } \mathcal{U} \text { but not in } A \}$
• included in: $A \subset B$

1.1.1 A Set Theory

Let $\Gamma$ be a family of subsets of $\mathcal{U}$.

$$\begin{array}{l}\text { 1. for any } A \in \Gamma, \bar{A} \in \Gamma, \\ \text { 2. for any } A, B \text { in } \Gamma, A \cup B \text { is in } \Gamma \text { , } \\ \text { 3. for any } A, B \text { in } \Gamma, A \cap B \text { is in } \Gamma \text { . }\end{array}$$

Then we say that $\Gamma$ satisfies closure with respect to $( \bar{}, \cup , \cap )$ , and we call $\Gamma$ a set theory.

---

Boolean algebra: a set theory that satisfies the following axioms

---

Propositional Calculus Associated with any set theory is a propositional calculus which satisfies properties analogous with a Boolean algebra, except that we use $\wedge$ and $\vee$ instead of the symbols $\cap$ and $\cup$ for “and” and “or”.

For example, $A = \{ x : x \text { satisfies } P ( A ) \}$

$${ A \cup B = \{ x : " x \text { satisfies } P ( A ) " \vee ^ { \prime \prime } x \text { satisfies } P ( B ) " \} } \\ { A \cap B = \{ x : " x \text { satisfies } P ( A ) " \wedge " x \text { satisfies } P ( B ) " \} }$$

1.1.2 A Propositional Calculus 命题逻辑

Now extend the family of simple propositions to a family $\mathcal{P}$, by including in $\mathcal{P}$ any propositional sentence $S(P_1 ,...,P_i ,...)$ which is made up of simple propositions combined under $( \bar{}, \cup , \cap )$. Then P satisfies closure with respect to $( \bar{}, \cup , \cap )$ and is called a propositional calculus.

• Truth function $T$

• $T : P \rightarrow \{ 0,1 \}$

• If $T(S_1)=T(S_2)$ for all truth values of the constituent simple propositions of the sentences $S_1$ and $S_2$, then $S_1 = S_2$ (i.e., $S_1$ and $S_2$ are identical propositions).

• Example:

$$\begin{array}{cccc}T\left(P_{1}\right) & T\left(P_{2}\right) & T\left(P_{1} \vee P_{2}\right) & T\left(P_{2} \vee P_{1}\right) \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1\end{array}$$

Since $T (P_1 \vee P_2 ) = T (P_2 \vee P_1)$ for all truth values it must be the case that $P_1 \vee P_2 = P_2 \vee P_1$.

If $\Gamma = ( U , \Phi , A _ { 1 } , A _ { 2 } , \ldots )$ is a set theory, then by exactly this procedure $\Gamma$ can be shown to be a Boolean algebra.

Suppose now that $\Gamma$ is a set theory with universal set $\mathcal{U}$, and $X$ is a subset of $\mathcal{U}$. Let $Γ_X = (X,\Phi,A_1 \cap X,A_2 \cap X,...)$. Since $\Gamma$ is a set theory on $\mathcal{U}$, $\Gamma_X$ must be a set theory on $X$, and thus there will exist a Boolean algebra in $\Gamma_X$.

---

Topology: a family $\Gamma = ( U , \Phi , A _ { 1 } , A _ { 2 } , \ldots )$ is a topology on $\mathcal{U}$ iff

1. when $A_1, A_2 \in \Gamma$ then $A_1 \cap A_2 \in \Gamma$
2. If $A_{j} \in \Gamma$ for all $j$ belonging to some index set $J$ (possibly infinite) then $\bigcup_{j \in J} A_{j} \in \Gamma$
3. Both $\mathcal{U}$ and $\Phi$ belong to $\Gamma$

---

Axioms 1 and 2 may be interpreted as saying that $\Gamma$ is closed under finite intersection and (infinite) union.

1.1.3 Partitions and Covers 集合的划分与覆盖

• cover for $X$ is a family $\Gamma = ( A _ { 1 } , A _ { 2 } , \ldots , A _ { j } , \ldots )$ where $j$ belongs to an index set $J$ (possibly infinite) such that

$$X=\cup \{A_j:j\in J\}$$

• partition for X is a cover which is $disjoint$, i.e.. $A_j\cap A_k=\Phi$ for any distinct $j,k\in J$

1.1.4 The Universal and Existential Quantifiers 普遍性与存在性

$$\left. \begin{array} { l } { \operatorname { not } [ \exists x \text { s.t. } x \text { satisfies } P ] \equiv [ \forall x : x \text { does not satisfy } P ] } \\ { \operatorname { not } [ \forall x : x \text { satisfies } P ] \equiv [ \exists x s . t . x \text { does not satisfy } P ] } \end{array} \right.$$

1.2 Relations, Functions and Operations

1.2.1 Relations 关系

• Cartesian product set 笛卡尔积
  • $X \times Y$ is the set of ordered pairs $(x,y)$ such that $x\in X$ and $y\in Y$.
  • If we let $\mathbb{R}$ be the set of real numbers, then $\mathbb{R}\times \mathbb{R}$ or $\mathbb{R}^2$ is the set

$$\{ ( x , y ) : x \in \mathbb{R} , y \in R \}$$

• Relation
  • A subset of the Cartesian product $Y×X$ is called a relation, $P$ , on $Y×X$. If $(y,x) ∈ P$ then we sometimes write $yPx$ and say that $y$ stands in relation $P$ to $x$. If it is not the case that $(y,x) ∈ P$ then write $(y,x) ∈ / P$ or $not (yPx)$. $X$ is called the domain of $P$ , and $Y$ is called the target or codomain of $P$ .
  • If $V$ is a relation on $Y × X$ and $W$ is a relation on $Z × Y$, then define the relation $W \circ V$ to be the relation on $Z × X$ given by $(z,x) ∈ W \circ V$ iff for some $y ∈ Y$, $(z,y) ∈ W$ and $(y,x) ∈ V$. The new relation $W \circ V$ on $Z \times X$ is called the composition of $W$ and $V$.
• Inverse of Relation $P^{-1}$
  • If $P$ is a relation on $Y \times X$, its inverse is the relation on $X \times Y$ defined by

$$P ^ { - 1 } = \{ ( x , y ) \in X \times Y : ( y , x ) \in P \}$$