『経済研究』（明治学院大学）第 147 号

2014 年【研究ノート】

Szpilrajn の定理と選好関係

高Ⅰ崎仁良序任意の順序に対しそれを含む全順序が存在するという命題は Szpilrajn の定理と呼ばれ，経済学に役立っている。Szpilrajn の元々の定理では irreflexive で transitive な２項関係を扱っており，これは経済学の強選好関係（strict preference）に適用できるが，もうひとつ経済学でよく使う２項関係に，異なるものどうしの無差別な関係を含む弱選好関係（weak preference）がある。そこで例えば Fishburn（1973）では
１．Szpilrajn の定理の原形
２．弱選好関係に適用できるような Szpilrajn の定理の変形をひとつの定理にまとめ，１を定理の前半部分に，２を定理の後半部分に当てている（同書 p. 198
Lemma 15.4）。しかしそこに証明はついていない。１の証明は Fishburn（1970）にある（p. 17 Theorem 2.4）が，２の証明はない。Sen（1970）に２の記述がある（p. 13 Lemma 1 ＊ f）が証明はない。２の最初の証明は Hansson（1968）を見なければならない（Lemma 3）。
一方，既存の諸文献には様々な不統一が見られる。
① １については，irreflexive で transitive な２項関係を含むものとして，Fishburn（1973）では irreflexive で transitive かつ weakly connected な２項関係の存在をいうのに対し，Fishburn（1970）では asymmetric で negatively transitive かつ weakly connected な２項関係の存在をいう（実は同じことになるのではあるが）。
② ２については，reflexive で transitive な２項関係を含むものとして，Fishburn（1973）では transitive で complete な２項関係の存在をいうのに対し，Sen（1970）では reflexive で transitive かつweakly connected な２項関係の存在をいう。
＊

 の研究では本学経済学部の村田玲音教授（純粋数学）と石井坦元教授（純粋数学）から有力な助言をいただ
こいた。記して謝意を表する。
201

『経済研究』（明治学院大学）第 147 号

さ らには，上の英字の用語は各文献間で異なることが多い（例えば Fishburn（1973）での weakly
connected は，Sen（1970）では complete。ここではもっぱら Fishburn（1970）に依拠した）。そのうえ，そうした諸性質をもつ２項関係の名称もまた各文献間で異なることが多いのである（Sen（1970）
p. 9 に照合表がある）。つまりこの定理は参照に不便である。
 そこで本稿ではなるべく統一的な表現を心がけ，ひとつの定理（定理１―上述の２の部分―）を基に他はその系とした。現代数学における順序は reflexive で transitive かつ antisymmetric な２項関係が通常なので，それを扱ったのが系１である。系２は Sen（1970）における表現である。Szpilrajnの定理の原形は系３とした。加えて系１の条件から reflexivity を除外した系４をおいた。また人間の不合理な選択や，多数決原理の不合理（投票の paradox）も考慮して，transitivity を要求しない系５をおいた。
 また先に述べたように，選好関係には無差別関係（同値関係）を含む弱選好関係と，それを含まぬ強選好関係があるが，例えば社会的厚生関数を記述するのに前者を用いる文献（例えば Sen（1970））と後者を用いる文献（例えば Kirman & Sondermann（1972））がある。同じことになるのかどうか気になったことがあるのは筆者だけでないだろう。弱選好関係が complete であれば，前者と後者が一対一に対応することを定理２に示しておいた。

Ⅱ

２項関係の諸条件について

以下で S は空でない任意の集合とする。
（定義１）直積 S 2 の部分集合を S 上の２項関係という。
S 上の２項関係に付帯する諸条件の名称は，序にも述べたように文献によって異なることが多い。ここでは一元的に Fishburn（1970）に依拠し，以下のように定める。
R を S 上の２項関係とする。
R が reflexive⇔∀x∈S（（x, x）∈R）

R が irreflexive⇔∀x∈S（（x, x）∉R）

R が symmetric⇔∀x, y∈S（（x, y）∈R →（ y, x）∈R）

R が asymmetric⇔∀x, y∈S（（x, y）∈R →（ y, x）∉R）

R が antisymmetric⇔

R が complete∀x, y∈S（（x, y）∈R∨（ y, x）∈R）⇔R が weakly connected∀x, y∈S（（x, y）∈R∧（ y, x）∈R → x＝y）⇔∀x, y∈S（x≠y →（x, y）∈R∨（ y, x）∈R）202

Szpilrajn の定理と選好関係

R が transitive⇔∀x, y, z∈S（（x, y）∈R∧（ y, z）∈R →（x, z）∈R）

R が negatively transitive⇔∀x, y, z∈S（（x, y）∉R∧（ y, z）∉R →（x, z）∉R）

上記の内，特定の諸条件を満たす２項関係には固有の名称が与えられている。例として
R が reflexive かつ transitive なときは，R を Fishburn（1973）では quasi-order といい，Sen（1970）
では quasi-ordering といい，他の文献では preorder，pre-ordering などという。
R が reflexive かつ transitive かつ complete なときは，Sen（1970）では ordering といい，他の文献では complete pre-ordering，complete quasi-ordering，weak ordering などという。
ここでは混乱を避けるために，上記の２例に関しては次の定義２と定義３を採用し，それ以外の２項関係については諸文献にある名称をあえて使わず，上記の諸条件をそのまま列挙することにした。
（定義２）S 上の２項関係 R が reflexive で transitive なとき，本稿では R を quasi-order という。
（定義３）S 上の２項関係 R が reflexive で transitive かつ complete なとき，本稿では R を order という。
以下，断る必要のないときは「S 上の」という語を省略することが多い。

ⅢSzpilrajn の定理（定義４）quasi-order Q1，Q2 が次の⑴ ⑵を満たすとき，Q2 は Q1 に compatible であるという。
⑴

Q1⊂Q2

⑵

2
∀（x, y）∈S（（x, y）∈Q1∧（ y, x）∉Q1 →（ y, x）∉Q2）

Sen（1970）における compatibility の定義（p. 13 Definition 1 ＊ 5, 1 ＊ 6）では，上の Q2 が order である場合に限定されるが，本稿ではこだわらない。
（定理１Hansson）S 上の任意の quasi-order Q に対し，Q に compatible な order R が存在する。

この定理の Hansson（1968）による証明は，Q に compatible な quasi-order の集合の中に極大元があることを Zorn の補題によって示し，それが order であることをいうのだが，本稿ではそういう集合の全順序部分集合の元の和集合が所望のものであることをいう。Kratowski の補題に依拠した。両補題と203

『経済研究』（明治学院大学）第 147 号

も選択公理に同値なことが知られる。
（証明）Q に compatible な quasi-order の集合をＡとする。Q∈ＡだからＡは空でない。Ａを⊂に関する順序集合とみると，Ａは極大な全順序部分集合Ｂをもつ（Kratowski）。R＝∪Ｂで R を定義する。
この R が求めるものである。以下そのことを示す。
⑴ Ｂが全順序だから R は transitive である。R が reflexive なことは明らか。つまり R は quasi-orderである。
⑵ R が Q に compatible なことを示す。Q ⊂ R は明らか。（x, y）∈Q∧（ y, x）∉Q なのに（ y, x）∈R だとすると∃Q′（（ y, x）∈Q′∧Q′∈Ｂ）。Ｂ⊂Ａだから Q′∈Ａ。これはＡの定義に反する。
⑶ R が complete なことを示すために，背理法の仮定として（α, β）∉R∧（β, α）∉R である（α, β）があったとして，R1 と R′を次のように定義する。
R1＝{（u, v）｜（u, α）∈R∧（β, v）∈R }R′＝ R ∪ R1

R は reflexive だから（α, β）∈R1。したがって R≠R′。
以下，R′が Q に compatible な quasi-order である（R′∈Ａ）ことをいう。
⑷

R′が reflexive なことは定義から明らか。

⑸ 次に R′が transitive であることをいう。（x, y）∈R′∧（ y, z）∈R′とする。（x, y）∈R∧（ y, z）∈R のと
きは R が transitive なので（x, z）∈R⊂R′。そこで（x, y）か（ y, z）のいずれかが R に属さないときをみる。
y）∉R のとき〉このときは（x, y）∈R1 である。また（ y, z）∉R1 でなければならない。なぜなら（ y, z）〈（x,∈R1 だとすると（ y, α）∈R だが（x, y）∈R1 なので（β, y）∈R。R は transitive だから（β, α）∈R となり矛盾する。したがって（ y, z）∈R となるが，（x, y）∈R1 により（β, y）∈R だから（β, z）∈R。同様に（x, y）∈
R1 から（ x, α）∈R。R1 の定義により（x, z）∈R1 ⊂ R′。
〈（ y, z）∉R のとき〉このときは（ y, z）∈R1 である。また（x, y）∉R1 である。なぜなら（x, y）∈R1 ならば（β,y）∈R で，（ y, z）∈R1 により（ y, α）∈R となるが，R が transitive なので（β, α）∈R となり矛盾する。
したがって（x, y）∈R。（ y, z）∈R1 により（ y, α）∈R∧（ β, z）∈R だから，（ x, α）∈R∧（β, z）∈R。R1 の定義により（x, z）∈R1 ⊂ R′。
以上で R′が reflexive で transitive，つまり quasi-order であることがわかった。
⑹ 次に R′が Q に compatible であることをいう。Q⊂R′は明らか。（x, y）∈Q∧（ y, x）∉Q なのに（ y, x）∈R′である（ y, x）があれば，R は Q に compatible なので，（ y, x）∈R1。したがって（ y, α）∈R∧（β, x）∈R。（x, y）∈R だから（β, y）∈R。（ y, α）∈R とあわせて（β, α）∈R となる。これは矛盾である。以上
で R′∈Ａが示された。
⑺ Ｃ＝Ｂ∪{R′} を定義すると，（α, β）∈R′と（α, β）∉R からＢ≠Ｃであることがわかる。Ｃが全順序であることをみるには，Q ∈Ｂならば Q ⊂ R ⊂ R′であることに注意すればよい。R′∈ＡだからＣはＡの全順序部分集合である。これはＢの極大性に反する。それは R が complete でないとしたためである。
QED204

Szpilrajn の定理と選好関係（系 １）Q を reflexive，transitive，antisymmetric な ２ 項 関 係 と す る。Q を 含 む reflexive，transitive，antisymmetric，complete な２項関係 R が存在する。
（証明）定理１の証明の各部に対応して以下の変更を施せばよい。
Q を含む reflexive，transitive，antisymmetric な２項関係の集合をＡとし，その極大な全順序部分集合Ｂに対し，R＝∪Ｂを定義する。
⑴

R が reflexive，transitive，antisymmetric であることは容易にわかる。

⑵

は不要。

⑶

R が complete でないと仮定し，定理１の証明と同様に R′＝R ∪ R1 を定義すると（α, β）∈R1 ⊂ R′
だから R ≠ R′。

⑷

R′が reflexive なことは明らか。

⑸ R′が transitive であることの証明は前と同じである。ここでは R′が antisymmetric であることを示す。（x, y）∈R′∧（ y, x）∈R′とする。このとき（x, y）∈R∧（ y, x）∈R でなければならないことが次のように示される。（x, y）∉R∨（ y, x）∉R としてみよう。
y）∉R のとき〉〈（x,
（x, y）∈R1 となるが R1 の定義により（x, α）∈R∧（β, y）∈R。このとき（ y, x）∈R なら，R が transitive なので（β, α）∈R となって矛盾。また（ y, x）∈R1 なら（ y, α）∈R∧（β, x）∈R よりやはり（β, α）∈R となる。
（ y, α）∈R∧（β, x）∈R。
このとき（x, y）∈R なら，〈（ y, x）∉R のとき〉
（ y, x）∈R1 となるが R1 の定義によりR が transitive なので（β, α）∈R となって矛盾。また（x, y）∈R1 なら（x, α）∈R∧（β, y）∈R よりやはり（β, α）∈R となる。
（x, y）∈R∧（ y, x）∈R であることがわかり，R が antisymmetric なので x ＝ y。R′は antisymmetric である。
⑹

は不要。

⑺

はそのまま。

QED（系 ２Sen）Q を quasi-order と す る。Q に compatible で weakly connected な quasi-order R が 存在する。
（証明）complete なら weakly connected である。
QED（系３Szpilrajn）Q を irreflexive，transitive な２項関係とする。Q を含む irreflexive，transitive，weakly connected な２項関係 R が存在する。

205

『経済研究』（明治学院大学）第 147 号（証明）定理１の証明の各部に対応して以下の変更を施す。
Q を含む irreflexive，transitive な２項関係の集合をＡとし，その極大な全順序部分集合Ｂに対し，R＝∪Ｂを定義する。
⑴

R が irreflexive，transitive であることは容易にわかる。

⑵

は不要。

⑶

⑷

⑸

R が weakly connected でないとすると，（α, β）∉R∧（β, α）∉R で，α≠βである（α, β）がある。これを用いて R″を以下のように定義する。
R″＝R ∪ R1 ∪ R2 ∪ R3 ∪ R4
R1＝{（u, v）｜（u, α）∈R∧（β, v）∈R }（定理１の証明と同じ）
R2＝{（u, β）｜（u, α）∈R }R3＝{（α, v）｜（β, v）∈R }R4＝{（α, β）}
また諸前提を以下の（＊）にまとめる。
（＊）〈R は irreflexive。R は transitive。α≠β。
（α, β）∉ R。（β, α）∉R。〉
以下，上の（＊）を念頭に進めていく。これにより R″が irreflexive であることはすぐにわかる。次にR″が transitive であることを示そう。
（x, y）∈R″かつ（ y, z）∈R″とする。
１〈（x, y）∈R のとき〉
１―① （ y, z）∈R なら，（x, z）∈R⊂R″。
（ y, α）∈R∧（β, z）∈R。
（x, y）∈R により（x, α）∈R。
（β, z）∈R とあわせて（x, z）
１―② （ y, z）∈R1 なら，∈R1⊂R″。
１―③ （ y, z）∈R2 なら，z＝β，（ y, α）∈R。（x, y）∈R だから（x, α）∈R。したがって（x, β）∈R2 。β＝zだから（x, z）∈R2 ⊂ R″。
∈R だから（x, α）∈R。したがって（x, z）∈R1⊂R″。
１―④ （ y, z）∈R3 なら，y＝α，（β, z）∈R。（x, y）
１―⑤ （ y, z）∈R4 なら y＝αかつ z＝β。（x, y）∈R だから（x, α）∈R。したがって（x, β）∈R2 。β＝z だから（x, z）∈R2⊂R″。
２〈（x, y）∈R1 のとき〉
（β, z）∈R。（x, α）∈R と２―① （ y, z）∈R なら，（x, α）∈R∧（β, y）∈R（（x, y）∈R1 による）とあわせあわせ（x, z）∈R1⊂R″。
（x, y）∈R1 だから（β, y）∈R。
（β, α）∈R となっ２―② （ y, z）∈R1 はおこらない。もしそうなら（ y, α）∈R。て矛盾。
２―③ （ y, z）∈R2 なら z＝β，（ y, α）∈R。（x, y）∈R1 だから（β, y）∈R。（β, α）∈R となって矛盾。
２―④ （ y, z）∈R3 なら y＝α。（x, y）∈R1 だから（β, y）∈R。（β, α）∈R となって矛盾。
２―⑤ （ y, z）∈R4 なら y ＝α。（x, y）∈R1 だから（β, y）∈R。上と同じで矛盾。
３〈（x, y）∈R2 のとき〉
206

Szpilrajn の定理と選好関係

このとき y＝βで（x, α）∈R。（ y, z）＝（β, z）。（β, z）は R1，R2，R3，R4 のいずれにも属さないことは容易に見てとれる。したがって（β, z）∈R。（x, α）∈R であったから（x, z）∈R1 ⊂ R″。
４〈（x, y）∈R3 のとき〉
このとき x＝α，（β, y）∈R。一方（ y, z）は R1，R2，R3，R4 のいずれにも属さないことが次のように示される。（ y, z）∈R1 なら（ y, α）∈R で，（β, α）∈R となって矛盾。（ y, z）∈R2 なら（ y, α）∈R で（β, y）∈
R とあわせ（β, α）∈R となり矛盾。
（β, y）∈R だったから（β, α）∈R となって矛盾。
（ y, z）∈R3 なら y＝α。
（ y, z）∈R4 なら y＝αでやはり（β, y）∈R により（β, α）∈R となって矛盾。したがって（ y, z）∈R。（β, y）∈R とあわせ（β, z）∈R。したがって（x, z）＝（α, z）∈R3 ⊂ R″。
５〈（x, y）∈R4 のとき〉
（x, y）＝（α, β）で（ y, z）＝（β, z）。（β, z）が R1，R2，R3，R4 のいずれにも属さないことは容易にわかる。したがって（β, z）∈R しかない。すると（α, z）∈R3 。α＝x だから（x, z）∈R3⊂R″。
⑹

は不要。

⑺

ではＣ＝Ｂ∪{R″} としてＣを定義すればよい。

QED系１の条件のうち reflexivity を除外したものが次の系４である。
（系 ４）Q を transitive，antisymmetric な ２ 項 関 係 と す る。Q を 含 む transitive，antisymmetric，

complete な２項関係 R が存在する。
（証明）定理１の証明の各部に対応して以下の変更を施せばよい。
Q を含む transitive，antisymmetric な２項関係の集合をＡとし，その極大な全順序部分集合Ｂに対し，R ＝∪Ｂを定義する。
⑴ R が transitive，antisymmetric であることは容易にわかる。
⑵

は不要。

⑶ R が complete でないと仮定し，系３の証明と同様に R″＝ R ∪ R1 ∪ R2 ∪ R3 ∪ R4 を定義する。ただしα≠βは要求しない。（α, β）∈R″だから R ≠ R″。
⑷

は不要。

⑸ R″が transitive なことは系３の証明と同様（irreflexivity に依存しない）。しかし R″が antisymmetric なことをいわねばならない。R″が antisymmetric であることを見るために（x, y）∈R″かつ（ y, x）∈R″とする。
〈（x, y）∈R のとき〉
R が antisymmetric であるから（ y, x）∈R なら x＝y。以下，（ y, x）が R1，R2，R3，R4 のいずれに属しても（β, α）∈R となって矛盾することが示される。
（ y, x）∈R1 なら（x, y）∈R∧（ y, α）∈R∧（β, x）∈R で，（β, α）∈R となる。
207

『経済研究』（明治学院大学）第 147 号（ y, x）∈R2 なら（ y, α）∈R∧x ＝βで，（x, y）＝（β, y）∈R により（β, α）∈R。
（ y, x）∈R3 なら（β, x）∈R∧y＝α∧（x, y）∈R だから（β, α）∈R。
（ y, x）∈R4 なら（ y, x）＝（α,β）。（x, y）＝（β, α）∈R。
〈（x, y）∈R1 のとき〉
この場合も，（ y, x）が R，R1，R2，R3，R4 のいずれに属しても（β, α）∈R となって矛盾する。
（ y, x）∈R なら（x, α）∈R∧（β, y）∈R とあわせ（β, α）∈R となる。
（ y, x）∈R1 なら（β, y）∈R∧（ y, α）∈R が導かれ（β, α）∈R。
（ y, x）∈R2 なら x＝βだから（x, y）＝（β, y）∈R1。（β, α）∈R。
（ y, x）∈R3 なら y＝α。（x, y）∈R1 より（β, y）∈R。（β, α）∈R。
（ y, x）∈R4 なら x＝β。（x, y）∈R1 より（x, α）∈R。（β, α）∈R。
〈（x, y）∈R2 のとき〉
このとき y＝β，（x, α）∈R で（ y, x）＝（β, x）。（β, x）∈R なら（β, α）∈R。（β, x）∈R1 でも（β, α）∈R。
（β, x）∈R2 でも（β, α）∈R。（β, x）∈R3 なら（β, x）∈R。（x, α）∈R だから（β, α）∈R。（β, x）∈R4 なら x＝βで（x, α）∈R により（β, α）∈R である。
〈（x, y）∈R3 のとき〉
このとき x＝α，（β, y）∈R，（ y, x）＝（ y, α）である。（ y, α）∈R なら（β, α）∈R。（ y, α）∈R1 ならやはり（β, y）∈R だから（β, α）∈R。
（ y, α）∈R3 ならやはり（β, α）∈R。
（β, α）∈R。
（ y, α）∈R2 なら（ y, α）∈R。
（ y, α）∈R4 なら y＝αで（β, α）∈R となる。
〈（x, y）∈R4 のとき〉
（x, y）＝（α, β），（ y, x）＝（β, α）∉R ∪ R1 ∪ R2 ∪ R3 だから（β, α）∈R4 。するとα＝βだから x＝y である。
したがって R″は antisymmetric である。
⑹

は不要。

⑺

は系３の証明と同じ。

QED
人間の不合理な選択や，多数決原理の不合理（投票の paradox）も考慮して次の系５をおく。
（系５）Q を asymmetric（または antisymmetric）な２項関係とする。Q を含む asymmetric（または antisymmetric），complete な２項関係 R が存在する。
{ β）}を用いればよい。他は同様。
（証明）定理１の証明の R´のかわりに R ∪ R4 ＝ R ∪（α,QED208Szpilrajn の定理と選好関係

Ⅳ

弱選好と強選好R を order とする。弱選好関係がその例である。P と I を次のように定義する。
１．（x, y）∈P

⇔ （x, y）∈R∧（ y, x）∉R

２．（x, y）∈I ⇔ （x, y）∈R∧（ y, x）∈R
すると次の３，４，５が成立する。
３．（x, y）∈R

⇔ （x, y）∈P∨（x, y）∈I

４．（x, y）∈ I⇒ （ y, x）∈ I

５．（x, y）∈ P⇒ （x, y）∉ I∧（ y, x）∉ P

逆に２項関係 P と I が４と５を満たすように与えられ，R が３で定義されると１と２を満たす。証明は読者にゆだねる。R ＝ P ∪ I である。強選好関係が P の例である。P は asymmetric である。次の定理が成立する。
（定理２）R1，R2 を order とする。これらに対し上記のように P1，P2 が定義されたとする。すると R1＝R2 ⇔ P1＝P2 。
（証明）〈⇒について〉（x, y）∈P1 なら（x, y）∈R1。R1＝R2 だから（x, y）∈R2 。このとき（x, y）∈I2 なら（ y,x）∈I2 だから（ y, x）∈R2 で（ y, x）∈R1。これは（x, y）∈P1 に矛盾。したがって（x, y）∈P1 なら（x, y）∈P2 。（x,y）∈P2 なら（x, y）∈P1 も同様。
〈⇐ に つ い て〉（x, y）∈R1 な ら（x, y）∈P1 か（x, y）∈I1 。 前 者 な ら P1＝P2 だ か ら（x, y）∈P2 で（x, y）∈
R2 。後者なら（x, y）∈P1 とはならない（そうなれば上の５により矛盾する）から，P1＝P2 により（x, y）（ y, x）∈P2 なら（ y, x）∈P1 となり（x, y）∈P2 ともならない。R2 は complete だから（ y, x）∈ P2 か（x, y）∈ I2 。
∈R1 に矛盾。したがって（x, y）∈I2 なので（x, y）∈R2 。（x, y）∈R2 なら（x, y）∈R1 も同様。
QED（参考文献）
Fishburn, P.C., ‘Utility theory for decision making’, New York : Wiley.（1970）.
Fishburn, P.C., ‘The theory of social choice’, Princeton University Press.（1973）.
Hansson, B., ‘Choice structures and preference relation’, Synthese 18（1968）443-458.
Kirman, A.P., and D. Sondermann, ‘Arrow’s theorem, many agents, and invisible dictators’, Journal of Economic
Theory 5（1972）267-277.
Sen, A.K., ‘Collective choice and social welfare’, San Francisco : Holdenday.（1970）.
Szpilrajn, E., ‘Sur l’extension de l’ordre partiel’, Fundamenta Mathematicae 16（1930）386-389.
209