ファイル置き場 Sendai Logic Homepage

Hall’s marriage theorem and subsystems of

second order arithmetic

Makoto Fujiwara

Tohoku university

2011.11.18

Contents of my master thesis

Title : Reverse mathematics of

marriage theorem and Kuratowski’s theorem

1 Introduction and Preliminaries

1 Introduction

2 Fundamental Concepts of Recursion Theory

3 Subsystems of Second Order Arithmetic and Reverse Mathematics

2 Reverse Mathematics of Marriage Theorem

1 History of the Study for the Difficulty of Marriage Theorem

2 Expanding Marriage Theorem

3 Bounded Marriage Theorem with Bounding Function as Parameter

3 Reverse Mathematics of Kuratowski’s Theorem

1 Formalization of Planar Graphs

2 RCA₀⊢Kratowski’s Theorem↔WKL₀

Contents of this talk

1

History of the Study for the Difficulty of Marriage

Theorem

2

Reverse mathematics of Expanding Marriage

Theorem

3

Reverse mathematics of Bounded Marriage

Theorem with Bounding Function as Parameter

Marriage Theorem

Abipartite graph(B, G; R)is a 3-tuple where BandGare disjoint sets of vertices andRis a set of edges such that R ⊂ B × G.

LetG = (B, G; R)is a bipartite graph. AsolutionofGis a injection M : B → Gsuch that{(b, M(b))|b ∈ B} ⊂ R. For any X⊂_finBletN_G(X) = {g ∈ G|∃b ∈ X((b, g) ∈ R)}^and S_{G(X) = |NG}(X)| − |X|.

Hall Condition : ∀X⊂

B(S

(X) ≥ 0)

Theorem (P. Hall, 1935)

IfGis a finite bipartite graph then

there is a solution ofGif it satisfies Hall condition. Theorem (M. Hall, 1948)

IfGis a bipartite graph such that for allb ∈ B,|NG(b)| < ∞then there is a solution ofGif it satisfies Hall condition.

Marriage Theorem

Abipartite graph(B, G; R)is a 3-tuple where BandGare disjoint sets of vertices andRis a set of edges such that R ⊂ B × G.

LetG = (B, G; R)is a bipartite graph. AsolutionofGis a injection M : B → Gsuch that{(b, M(b))|b ∈ B} ⊂ R. For any X⊂_finBletN_G(X) = {g ∈ G|∃b ∈ X((b, g) ∈ R)}^and S_{G(X) = |NG}(X)| − |X|.

Hall Condition : ∀X⊂

B(S

(X) ≥ 0)

Theorem (P. Hall, 1935)

IfGis a finite bipartite graph then

there is a solution ofGif it satisfies Hall condition. Theorem (M. Hall, 1948)

IfGis a bipartite graph such that for allb ∈ B,|NG(b)| < ∞then there is a solution ofGif it satisfies Hall condition.

Recursion Theoretic Analysis of Marriage Theorem

LetGbe a recursive baipartite graph such that for allb ∈ B,

|NG(b)| < ∞andGsatisfies Hall condition.

ThenGhas a solution by infinite marriage theorem.

Now can we take the solution recursively? The answer is “no”. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Can we modify this to have a recursive solution?

A graph_{G = (V, E)} ishighly recursiveif the function p : V → ωsuch that _{p(v) = |{v}^′|(v, v^′) ∈ E}|is recursive.

Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a highly recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Recursion Theoretic Analysis of Marriage Theorem

LetGbe a recursive baipartite graph such that for allb ∈ B,

|NG(b)| < ∞andGsatisfies Hall condition.

ThenGhas a solution by infinite marriage theorem.

Now can we take the solution recursively? The answer is “no”. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Can we modify this to have a recursive solution?

A graph_{G = (V, E)} ishighly recursiveif the function p : V → ωsuch that _{p(v) = |{v}^′|(v, v^′) ∈ E}|is recursive.

Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a highly recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Recursion Theoretic Analysis of Marriage Theorem

LetGbe a recursive baipartite graph such that for allb ∈ B,

|NG(b)| < ∞andGsatisfies Hall condition.

ThenGhas a solution by infinite marriage theorem.

Now can we take the solution recursively? The answer is “no”. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Can we modify this to have a recursive solution?

A graph_{G = (V, E)} ishighly recursiveif the function p : V → ωsuch that _{p(v) = |{v}^′|(v, v^′) ∈ E}|is recursive. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a highly recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Recursion Theoretic Analysis of Marriage Theorem

LetGbe a recursive baipartite graph such that for allb ∈ B,

|NG(b)| < ∞andGsatisfies Hall condition.

ThenGhas a solution by infinite marriage theorem.

Now can we take the solution recursively? The answer is “no”. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Can we modify this to have a recursive solution?

A graph_{G = (V, E)} ishighly recursiveif the function p : V → ωsuch that _{p(v) = |{v}^′|(v, v^′) ∈ E}|is recursive. Theorem (A.Manaster and J.Rosenstein, 1972)

There exists a highly recursive bipartite graph that satisfies Hall condition, but has no recursive solution.

Expanding Hall Condition :

there is a function h s.t.

h(0) = 0 & ∀n∀X⊂

B(|X| ≥ h(n) → S

(X) ≥ n)

Theorem (H.Kierstead, 1983)

IfGis highly recursive bipartite graph that satisfies expanding Hall condition with a recursiveh, thenGhas a recursive solution.

Theorem (H.Kierstead, 1983)

There exists a highly recursive bipartite graph which satisfies expanding Hall condition but has no recursive solution.

Kierstead also showed that a bipartite graph which satisfies expanding Hall condition has a solution even if there are boys who know infinite many girls.

Theorem (H.Kierstead, 1983)

IfGis a bipartite graph then there is a solution ofGif it satisfies Expanding Hall condition.

Reverse Mathematics of Marriage Theorem

FMT: IfG = (B, G; R)is a bipartite graph such that|B| < ∞ then there is a solution ofGif it satisfies Hall

condition.

MT: IfG = (B, G; R)is a bipartite graph such that

∀b ∈ B ∃t ∀g((b, g) ∈ R → g < t)then there is a solution ofGif it satisfies Hall condition. BMT: IfG = (B, G; R)is a bipartite graph such that

∃p : B → Ns.t.∀b, g((b, g) ∈ R → g < p(b))then there is a solution ofGif it satisfies Hall condition.

Theorem (J.Hirst, 1987) RCA0 ^⊢ FMT

RCA₀ ⊢ MT ↔ACA₀ RCA₀ ⊢ BMT ↔WKL₀

Symmetric Hall Condition :

∀X⊂_finB(S_G(X) ≥ 0) & ∀Y⊂_finG(S_G(Y) ≥ 0) A symmetric solution is a bijectve solution.

MTsym: IfG = (B, G; R)is a bipartite graph such that

∀v ∈ B∪G ∃t ∀g((v, v^′) ∈ R → v^′ <t) then there is a symmetric solution ofG if it satisfies symmetric Hall condition. BMT_sym: IfG = (B, G; R)is a bipartite graph such that

∃p : B ∪ G → Ns.t.∀v, v^′((v, v^′) ∈ R → v < p(v^′)) then there is a symmetric solution ofG

if it satisfies symmetric Hall condition. Theorem (J.Hirst, 1987)

RCA0 ^⊢ MTsym ^↔ACA0

RCA0 ^⊢ BMTsym ^↔WKL0

Reverse mathematics of Expanding Marriage

Theorem

Expanding Hall Condition :

Hall condition& ∀n∃m∀X⊂_finB(|X| ≥ m → S_G(X) ≥ n)

Strongly Expanding Hall Condition :

Hall condition&

∃h_B:B → Ns.t. ∀n∀X⊂_finB(|X| ≥ h_B(n) → S_G(X) ≥ n)

B -locally finite :

B -bounded :

EMT: IfG = (B, G; R)is a bipartite graph which satisfies expanding Hall condition and B-locally finite then there is a solution ofG.

E_SMT: IfG = (B, G; R)is a bipartite graph which satisfies strongly expanding Hall condition andB-locally finite then there is a solution ofG.

BEMT: IfG = (B, G; R)is a bipartite graph which satisfies expanding Hall condition and B-bounded

then there is a solution ofG.

BE_SMT: IfG = (B, G; R)is a bipartite graph which satisfies strongly expanding Hall condition andB-bounded then there is a solution ofG.

XMT^G: the statement XMT with the assumptionG-locally finite

XMT^GB: the statement XMT with the assumptionG-bounded

We got the following results. ACA₀ MT(Hirst)

   _EMT

ESMT EMT^G

EMT^GB E_SMT^G WKL₀ BMT(Hirst)

   _BEMT

BESMT BEMT^G

BEMT^GB BE_SMT^G

RCA₀ E_SMT^GB ?

BE_SMT^GB(Kierstead) FMT(Hirst)

Conjecture : RCA₀ ⊢ E_SMT^GB

EM^∗T is the statement proved by Kierstead.

EM^∗T: IfG = (B, G; R)is a bipartite graph which satisfies expanding Hall condition

then there is a solution ofG.

E_SM^∗T: IfG = (B, G; R)is a bipartite graph which satisfies strongly expanding Hall condition

then there is a solution ofG. Theorem

ACA₀⊢ EM^∗T

The next figure is given by combining this result with the previous figure.

ACA0 MT(Hirst) EM^∗T

   _{EMT ESM}^∗_T EM^∗T^G E_SMT EMT^G

EM^∗T^GB E_SM^∗T^G EMT^GB E_SMT^G WKL₀ BMT(Hirst)

   _BEMT

BESMT BEMT^G

BEMT^GB BE_SMT^G

RCA₀ E_SM^∗T^GB ?

E_SMT^GB ?

BESMT^GB(Kierstead) FMT(Hirst)

Conjecture : RCA_{0 +}some strong induction ⊢ E_SM^∗T^GB

Symmetrical expanding Hall condition :

Expanding Hall condition forB &Expanding Hall condition forG

Half strongly expanding Hall condition :

Symmetrical expanding Hall condition&

strongly expanding Hall condition for one ofBorG

Strongly symmetrical expanding Hall condition :

Strongly expanding Hall condition for B & strongly expanding Hall condition forG

Symmetrically locally finite :

Half bounded :

symmetrically locally finite& (one of BorG)-bounded

Symmetrically bounded :

EMT_sym: IfGis a b.g. which satisfies sym. expanding Hall condition and sym. locally finite

then there is a sym. solution ofG.

E_SMT_sym: IfGis a b.g. which satisfies sym. strong expanding H.c. and sym. locally finite

then there is a sym. solution ofG.

BEMT_sym: IfGis a b.g. which satisfies sym. expanding H.c. and sym. bounded then there is a sym. solution ofG. BESMTsym: IfGis a b.g. which satisfies sym. strongly expanding

H.c. and sym. bounded

then there is a sym. solution ofG.

BEHSMTsym: IfGis a b.g. which satisfies half strongly expanding H.c. and sym. bounded

then there is a sym. solution ofG.

HBESMTsym: If Gis a b.g. which satisfies sym. strongly expanding H.c. and half bounded

then there is a sym. solution ofG.

We got the following results.

ACA0 MTsym(Hirst) EM^∗Tsym ^{· · ·· · · ··}

   _EMTsym · · ·· · · ··

· · ·· · · ·· E_SMT_sym

· · ·· · · ·· · · ··

HBE_SMT_sym WKL₀ BMT_sym(Hirst)

   _BEMTsym

BE_HSMT_sym

RCA₀ BE_SMT_sym

FMT_sym

EM^∗T_sym: IfGis a b.g. which satisfies sym. expanding H.c. then there is a sym. solution ofG.

Theorem

ACA0^⊢ EM^∗Tsym

We got the following results.

ACA0 MTsym(Hirst) EM^∗Tsym ^{· · ·· · · ··}

   _EMTsym · · ·· · · ··

· · ·· · · ·· E_SMT_sym

· · ·· · · ·· · · ··

HBE_SMT_sym WKL₀ BMT_sym(Hirst)

   _BEMTsym

BE_HSMT_sym

RCA₀ BE_SMT_sym

FMT_sym

EM^∗T_sym: IfGis a b.g. which satisfies sym. expanding H.c. then there is a sym. solution ofG.

Theorem

ACA0^⊢ EM^∗Tsym

We got the following results.

ACA0 MTsym(Hirst) EM^∗Tsym ^{· · ·· · · ··}

   _EMTsym · · ·· · · ··

· · ·· · · ·· E_SMT_sym

· · ·· · · ·· · · ··

HBE_SMT_sym WKL₀ BMT_sym(Hirst)

   _BEMTsym

BE_HSMT_sym

RCA₀ BE_SMT_sym

FMT_sym

EM^∗T_sym: IfGis a b.g. which satisfies sym. expanding H.c. then there is a sym. solution ofG.

Theorem

ACA0^⊢ EM^∗Tsym

Corollary.

IfGis highly recursive bipartite graph that satisfies symmetric expanding Hall condition with a recursiveh, thenGhas a recursive symmetric solution.

∵_{)RCA0 ⊢BESMTsym.} Corollary.

There exists a highly recursive bipartite graph which satisfies symmetric expanding Hall condition but does not have a recursive symmetric solution.

∵_{)RCA0 ⊢BEMTsym →WKL0.}

Reverse mathematics of Bounded Marriage Theorem

with Bounding Function as Parameter

Theorem (J.Hirst, 1987) RCA0 ^⊢ BMT ↔WKL0

In our formal system Z₂, we fix p : N → Nand consider the following statement : ifG = (B = {b^i|i ∈ N}, G = {gⁱ|i ∈ N}; R)be a bipartite graph which satisfies Hall condition and

∀i, j((b(i), g( j)) ∈ R ⇒ j ≤ p(i)), then there is a solution ofG. We regard the bounding function pas parameter and consider the bounded marriage theorem dependent on p. With no restriction of

p, it is equivalent to WKL₀ over RCA₀. p(x) ≡ xseems to be the most simple function which satisfy the situation since H.c. requires∀x¬∀x^′ ≤ x(p(x^′) < x). It is easily founded that in this case, we can get the solution within RCA₀. Therefore, our interet is where is the boundary.

BMT[P]: IfG = (B = {bi^|i ∈ N}, G = {gi|i ∈ N}; R)be a bipartite graph which satisfies Hall condition and

∀i, j((b(i), g( j)) ∈ R ⇒ j ≤ p(i))and P(p), then there is a solution ofG.

Theorem

RCA0^⊢BMT[∀x(p(x) ≤ x + ¯k)]^. Theorem

RCA_0+Π⁰₂-IND ⊢BMT[∃k∀x(p(x) ≤ x + k)]^.

Question.

RCA₀⊢BMT[∃k∀x(p(x) ≤ x + k)]^{? or not?} Theorem

RCA₀⊢ ∀p : N → N

(BMT[∀t∃x(p(x) > x + t) ∧ ∀x, x^{′(x < x′ → p(x) ≤ p(x′))] ↔WKL0).}

We can consider the symmetric type of this sort of problems. BMT_sym[P]: IfG = (B = {bi^|i ∈ N}, G = {gi|i ∈ N}; R)be a bipartite

graph which satisfies symmetric Hall condition and

∀i, j((b(i), g( j)) ∈ R ⇒ j ≤ p(i) ∧ i ≤ p( j))and P(p), then there is a symmetric solution ofG.

Theorem

RCA₀⊢ BMT_sym[∀x(p(x) ≤ x + ¯k)]^. Theorem

RCA_0+Π⁰₂-IND ⊢ BMT_sym[∃k∀x(p(x) ≤ x + k)]^. Theorem

RCA₀⊢ ∀p : N → N

(BMT_sym[∀t∃x(p(x) > x + t) ∧ ∀x, x^{′(x < x′ → p(x) ≤ p(x′))] ↔} WKL0).

Bibliography

1 W. Gasarch, “A survey of recursive combinatorics”, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland(1998), pp. 1041–1176.

2 A. Manaster and J. Rosenstein, Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. Amer. Math. Soc.,25(1972), pp. 615–654

3 H. A. Kierstead, An Effecttive Version of Hall’s Theorem, American Mathematical Society, 88(1983), pp. 124–128.

4 J. R. Hirst, Combinatrics in Subsystems of Second Order Arithmetic, Ph.D. thesis, Pennsylvania State University, 1987.

Thank you for your attention.

おまけ

村上くんが持ってきた₇頭の象のパズル。このパズル、意外と簡 単には解けない。しかし修論に追われる我々はなるべく早くこ のパズルを解きたい。度重なる検証の結果、我々は像を₈₅回回 転させるだけでこのパズルを解くことができた。₍なかなかの時 間を要した。₎では一般にn 頭の象のパズルを解くには像を何回 回転させなければならないのか？

定理(Omoto-Fujiwara-Hoshino, 2011)

n 頭の像のパズルを解くのに必要な手数 an^は高々

{ a

₌

⁽⁴

^{− 1)}

a

₌

(4

− 1)

未解決問題

n 頭の像のパズルを解くのに最低限必要な手数は？

おまけ

村上くんが持ってきた₇頭の象のパズル。このパズル、意外と簡 単には解けない。しかし修論に追われる我々はなるべく早くこ のパズルを解きたい。度重なる検証の結果、我々は像を₈₅回回 転させるだけでこのパズルを解くことができた。₍なかなかの時 間を要した。₎では一般にn 頭の象のパズルを解くには像を何回 回転させなければならないのか？

定理(Omoto-Fujiwara-Hoshino, 2011)

n 頭の像のパズルを解くのに必要な手数 an^は高々

{ a

₌

⁽⁴

^{− 1)}

a

₌

(4

− 1)

未解決問題

n 頭の像のパズルを解くのに最低限必要な手数は？

おまけ

村上くんが持ってきた₇頭の象のパズル。このパズル、意外と簡 単には解けない。しかし修論に追われる我々はなるべく早くこ のパズルを解きたい。度重なる検証の結果、我々は像を₈₅回回 転させるだけでこのパズルを解くことができた。₍なかなかの時 間を要した。₎では一般にn 頭の象のパズルを解くには像を何回 回転させなければならないのか？

定理(Omoto-Fujiwara-Hoshino, 2011)

n 頭の像のパズルを解くのに必要な手数 an^は高々

{ a

₌

⁽⁴

^{− 1)}

a

₌

(4

− 1)

未解決問題

n 頭の像のパズルを解くのに最低限必要な手数は？