확인해 주시면 감사하겠습니다.


표기법:

V^*는 V의 원소들을 원소로 가지는 모든 finite sequence들의 집합입니다. 즉, V = {'1', '2'}일 때, V^* = {"", "1", "2", "11", "12", "21", "22", "111", ...}입니다.

문자열 α β는 문자열 α 뒤에 문자열 β를 접합한 것입니다. 즉, α = "12"이고 β = "ab"일 때, α β = "12ab"이고 β α = "ab12"입니다.

0 이상의 정수 n에 대하여, 문자열 ω^n은 문자열 ω을 n번 반복한 것입니다. 즉, ω = "oxx"일 때, ω^3 = "oxxoxxoxx"이고 ω^0 = ""입니다.

문자열 ω에 대하여, |ω|는 ω의 길이를 나타냅니다.


문제.

유한 집합 V가 주어졌다고 하자.

임의의 L ⊆ V^*에 대하여 (1)이 성립할 때 그리고 오직 그럴 때에만 (2)가 성립함을 보여라.

(1) (∀α∈L) (∀β∈L) (α β = β α).

(2) (∃ω∈V^*) (L ⊆ { ω^n : n∈{0, 1, 2, ...} }).

증명.

(2) → (1)는 자명하게 성립합니다.

(1) → (2)을 보이기에 앞서, L ⊆ V^*이 (1)를 만족하면, 모든 α∈L에 대하여 f(α) := |α|로 정의된, 함수 f : L → N이 단사임을 보이겠습니다.

|α| = |β|를 만족하는 임의의 α∈L와 β∈L에 대하여:

문자열 α β의 첫 |α|개는 α이고 문자열 β α의 첫 |β|개는 β인데, α β = β α이므로 α = β입니다.

이제 L ⊆ V^*이 (1)를 만족한다고 가정하겠습니다:

먼저 다음과 같이 열 ＜L_n＞_{n∈N}을 정의하겠습니다:

L_0 := L.

L_(n + 1) := L_n ∪ { γ∈V^* : (∃α∈L_n) (∃β∈L_n) (α = β γ) }.

그러면 임의의 n∈N에 대하여 (∀α∈L_n) (∀β∈L_n) (α β = β α)이 성립함을 수학적 귀납법으로 보이겠습니다.:

(1)에 의하여 (∀α∈L_0) (∀β∈L_0) (α β = β α)이 성립합니다.

(∀α∈L_k) (∀β∈L_k) (α β = β α)를 만족하는 임의의 k∈N에 대하여:

먼저 X := { γ∈V^* : (∃α∈L_k) (∃β∈L_k) (α = β γ) }로 둡시다.

그러면 (∀α∈X) (∀β∈L_k) (α β = β α)임과 (∀α∈X) (∀β∈X) (α β = β α)임을 보이면 됩니다.

임의의 α∈X와 β∈L_k에 대하여:

γ = δ α를 만족하는 어떤 γ∈L_k와 δ∈L_k가 존재합니다.

(∀α∈L_k) (∀β∈L_k) (α β = β α)이므로 δ α β = γ β = β γ = β δ α = δ β α이고 α β = β α입니다.

임의의 α∈X와 β∈X에 대하여:

γ = δ α ∧ ε = ζ β를 만족하는 어떤 γ∈L_k, δ∈L_k, ε∈L_k와 ζ∈L_k가 존재합니다.

(∀α∈L_k) (∀β∈L_k) (α β = β α)이고 (∀α∈X) (∀β∈L_k) (α β = β α)이므로 δ α β ζ = γ β ζ = γ ε = ε γ = β ζ γ = β ζ δ α = ζ β δ α = ζ β α δ = ζ β δ α = ζ δ β α = δ ζ β α = δ β ζ α = δ β α ζ이고 α β = β α입니다.

이제 A := { α∈V^* : (∃n∈N) (α ∈ L_n) ∧ α ≠ "" }로 둡시다.

임의의 α∈A와 β∈A에 대하여:

α ∈ L_n를 만족하는 어떤 n∈N과 β ∈ L_m을 만족하는 어떤 m∈N이 존재합니다.

이때 α와 β 모두 L_(max {n, m})의 원소이므로 α β = β α입니다.

A = {}이면:

L ⊆ A ∪ {""}이고 A ∪ {""} = {""}이므로, L = {} ∨ L = {""}입니다.

두 경우 모두 ω := ""에 대하여 L ⊆ { ω^n : n∈N }를 만족함을 알 수 있습니다.

A ≠ {}이면:

ω를 A의 원소들 가운데 가장 짧은 문자열로 둘 수 있습니다.

임의의 α∈L에 대하여:

나눗셈 알고리즘에 의하여, |α| = q * |ω| + r ∧ 0 ≤ r ＜ |ω|인 어떤 q∈Z와 r∈Z이 존재합니다.

여기서 |α| ≥ 0이고 |ω| ＞ 0이므로 q ≥ 0입니다.

이때 ω^q α = α ω^q이므로 어떤 β∈V^*가 존재하여 α = ω^q β입니다.

n := min { k∈N : ω ∈ L_k }에 대하여 β ∈ L_(n + q + 1)이므로, β = "" ∨ β ∈ A임을 알 수 있습니다.

그런데, β ≠ ""이면 ω가 A 중 가장 짧은 문자열이란 사실에 모순되므로, β = ""이고 α = ω^q입니다.

■