\bigvee が二つ重なったような字(latex)

正式に何という字なのか知らないが,たまに数学の本に \bigvee が重なったような記号が出てくる.(メタレベルでの論理和を表すこともあるらしい).総和記号(シグマ)のように真下に添え字が付いてほしいこともあるので\DeclareMathOperator を使ったらどうかと考えてみた.

Wee

\documentclass[]{article}
\usepackage{amsmath}
\DeclareMathOperator*{\Wee}{\bigvee\kern-.7em\bigvee}
\begin{document}
\begin{equation*}
\Wee_i \,p_i
\end{equation*}
\end{document}
広告

Gibbs現象

PDFリンク:Gibbs現象

追記2019/01/29:誤記を修正しました

一万円を崩す方法(Haskell)

一万円を両替して崩す方法は何通りあるだろうか.ただし:
・百円玉,五百円玉,千円札を自由に(好きなだけ)使って良い.
・五百円記念硬貨は10枚までしか使えない.
・二千円札は2枚までしか使えない.

この問題は以前の千円を崩す方法(Haskell)の変種である.新しい要素は五百円記念硬貨(普通の五百円玉と区別される)と二千円札である.どちらも個数(枚数)に制限がある.

答えは1561通りになるはず.

以前の記事では組み合わせ的な考察だけから漸化式を導いて解いたが,今回は母関数を使わねば漸化式を導くことができなかった.

これを求めためのHaskellプログラムは次のようになる:

p n = if n < 0 then 0
      else if n `rem` 100 == 0 then 1
      else 0
q n | (n < 0) = 0
    | otherwise = p n + q (n-500)
r n | (n < 0) = 0
    | otherwise = q n + r (n-1000)
s n | (n < 0) = 0
    | otherwise = r n - r (n-5500) + s (n-500)
t n | (n < 0) = 0
    | otherwise = s n - s (n-6000) + t (n-2000)

問題の答えは t 10000として求まる.

ブログに数式を書くのが面倒になったので,数列を母関数を通して扱う話からはじめて,このプログラムを導く過程をPDFにまとめてみた.(文字を大きくしておいたのでスマホでも読めると思う):数列と母関数

uniq 的な関数(Haskell)

Haskell のリストから重複要素を除去する関数はnubである.「同じかどうか」を判定する関数を引数に取る nubBy を使いたい場合もある.これらの関数はリスト全体を舐めて重複要素を除去する.

扱っている配列がソート済みである場合も多い.その場合,隣接要素だけ見ていけば重複要素を除去できるはずである.そうすれば少しだけ効率が良いかも知れない.そう考えてこんな関数を書いてみた:

uniq :: (Eq a) => [a] -> [a]
uniq = foldr  uniqAux []
  where uniqAux :: (Eq a) => a -> [a] -> [a]
        uniqAux t [] = [t]
        uniqAux t (u:us) = (if t == u then [u] else [t,u]) ++ us

uniqBy を作るのも簡単である.

※効率がどうこうと言ったが,性能比較はまだしていない.

集合論宇宙についてのメモ

■「集合全体の集まり」を「宇宙(universe)」と呼びしばしば{\mathbf{V}}などと書く.ただし,「宇宙」という言葉はもう少し小さな「集合」を指すために使われることもある.以下ではZFCにおける「集合全体の集まり」の意味で{\mathbf{V}}という文字を使う.ところで,なぜ”V”なのかというと,ドイツ語のVollraumから来ているらしい.voll(いっぱいの)/raum(空間) と分解すれば意味は取れる.

{\mathbf{V}}が集合ではないことは,少なくとも二つの方法で示せる.最初に基礎の公理を使う方法を示し,次に分出公理図式を使うものを示す.

■基礎の公理を用いた証明.
基礎の公理は次のようなものであった:
{\forall x \enskip \left(x \not= \varnothing  \Rightarrow \exists y \in x \enskip \forall t \in x \enskip (t \not\in y)\right).}

さて,{\mathbf{V}}が集合であったと仮定すると{X:= \left\lbrace  \mathbf{V}\right\rbrace}も集合である.この{X}に基礎の公理を適用すると{\mathbf{V}\not\in \mathbf{V}}が得られるが,{\mathbf{V}}はすべての集合を含んでいるのだからこれはおかしい.よって,{\mathbf{V}}が集合として存在するという仮定から矛盾が導かれたことになる.よって{\mathbf{V}}は集合ではない.

■分出公理図式を用いた証明.
分出公理図式は無限個の公理の総称であり,ある集合から部分集合を作ることを可能にする.(分出公理図式は置換公理図式から導くことも可能であり,ZFCの公理群に含めない場合もあるが,何れにせよZFCでは分出「公理」図式は使用可能である).

{\mathrm{V}}が集合だと仮定すると,分出公理図式から{W:=\left\lbrace x \in \mathbf{V} \mid x \not\in x \right\rbrace}も集合となり,特に{W\in \mathbf{V}}である.すると,{W \in W}であると同時に{W \not\in W}であることが導かれてしまう(床屋のパラドックス).よって{\mathbf{V}}は集合ではあり得ない.

■余談
しばしば,{\mathbf{V}}が集合ではないことの直感的な説明として,「{\mathbf{V}}は集合に収まるには巨大過ぎる」と説明されることがある.

ブルバキの位相についてのメモ

大学二年生の夏休みはずっとブルバキの位相の本を読んでいたような記憶がある.Springer から出てた “General Toplogy Chapters 1-4” がそれ.いま思えば別にこれが位相空間を学ぶベストの本ではないと思うが,20歳の頃に悩みながら読んだ記憶が美化されてしまうせいもあってか不思議と嫌いになれず,いまだに手元にこの本が置いてある.

上で《嫌いになれない》と書いた.この本は多くの位相空間の教科書とはなんとなく書き方が違う.なにせ,肝心の位相空間の定義の仕方からして少し変わっている.ややクセがあるのは確かであり,人前で《この本が好き》というのは少し気恥ずかしい.どう書けば《変わってる》感じが伝わるかわからないが,ここでは二点

1.開集合系の定義の仕方
2.フィルターへの偏愛

に絞って説明する.

■1.開集合系の定義の仕方
ブルバキでは集合{X}上の位相構造{T}が次のよう性質を満たすものとして定義されている:
(O1) {T}の集合の合併は{T}に属する.
(O2) {T}の集合の有限交差は{T}に属する.

多くの教科書では{X,\varnothing \in T}も公理になっている.しかし,実はこれは(O1)(O2)から次のように導ける:

・空集合が{T}に属すること:{T}の空部分集合を考える.(O1)により{\bigcup \varnothing \in T}となることから成立.

{X}{T}に属すること:{T}の空部分集合を考える.(O2)により{\bigcap \varnothing \in T}となることから成立.

上の議論には納得が行くだろうか.空集合が{T}に属することの議論には問題がないが,{X}{T}に属することの議論はどうだろうか.そもそも{\bigcap \varnothing}の指示内容は何だろうか——それが存在するとして,それは果たして集合だろうか?

(念のために付言すれば,通常の集合論では{\bigcap \varnothing}を考えない.たとえばキューネン『キューネン数学基礎論講義』p.32とそこにおける議論を見よ).

■2.フィルターへの偏愛
位相空間はフィルターを用いて定義することもできる.この《フィルター》というのはブール代数などでも研究されるフィルターと大体同じ概念である.(Xの冪集合をブール代数とみなしたときの「ブール代数のフィルター」はこの本での「フィルター」になっている).フィルターを通して眺めると連続性の議論がやや代数的な雰囲気になる.とはいえ,この本で扱われている範囲ではあまりフィルターを持ち出して議論する旨味はそんなに感じられない.読んで理解するのが結構大変なわりにはどこへもたどり着けないようなもやもやした気持ちが残る.

■3.おまけ:公理(O3)
先述したように,ブルバキの位相空間の公理は(O1)(O2)で尽くされているのだが,しばらく読み進めるとChap 1 sec8.4 Regular Space Prop.11 に(O3)が登場している.なぜこの公理が(O3)と呼ばれるのにふさわしいのか,などは全く説明されていない.やはりこの本はクセが強い.

vacuous truth

たまにこの言葉を思い出せなくてググってるので自分用メモ.

(ここに来た他人用の説明):条件式(A⇒B)のAを「前件」と,そしてBを「後件」と言うのであった.前件が偽ならば後件に何を置いても条件式全体は真と評価される.このような場合に条件式が真になることを特に “vacuous truth” と呼ぶことがある.(決まった訳語はないらしい).古典論理のなかで,入門者を少しばかり悩ませる話題として有名である.

古典論理における条件式は時相のような微妙なニュアンスを含んでいないので日常言語における条件文とそのまま同一視することはできないが,日常言語でも前件として「絶対に起こらない(であろうと思われる)」ことを置いて何かを言うことがある.少し前の話題だがマスコミ各社が「トランプが大統領になるはずがない」と報じていたときに,「トランプが大統領になったら全裸で街を歩く」といった類のツイートしている人たちがいた.前件が絶対に偽だ(とそのときには思われていた)から後件にどんなヤバいことを書いても平気というわけである.

もう一つの「納得方法」として,条件式(A⇒B)を「(Aであって(Bではない))ということはありえない」と言い換えるというものがある.これを論理式で置き換えれば(¬(A∧(¬B)))ということになる.さらに de Morgan を使えばこれは((¬A)∨B) と書き換えられる.この言い換えと置き換えに納得が行くならば,「Aが成り立たない」場合の(A⇒B)の真理表を書いたとき,BがTであってもFであっても
     ((¬F)∨B) = (T ∨ B) = T
となるからvacuous truth も受け入れるべきだということになる.

集合論においても vacuous truth が活躍する場面がある.空集合にはいかなる集合も含まれない.よって,
    {a \in \varnothing}
と書いただけで({a}がなんであれ)偽になる.よって,
    {\forall a \enskip (a \in \varnothing \Rightarrow P(a)).}
という文は任意の述語{P()}について正しい.任意の述語を入れて良いのだから{P()}の代わりにその否定{\neg P()}を入れても良いわけである.よって
    {\forall a \enskip (a \in \varnothing \Rightarrow \neg P(a)).}
つまり,「空集合の任意の要素はいかなる性質をも持ち得る」ということになる.少し騙されたような気持ちになるが,帰納的に構成された集合の列についての命題を証明しようとするときの最初のステップなどでこのような vacuous truth が有効に活用されることもある.

千円を崩す方法(Haskell)

次のような問題を考えてみましょう:

千円を両替して崩す方法は何通りあるだろうか.ただし,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って良いものとする.

まず問題を一般化し,つぎのように考えます.{A_n}によって「{n}円を一円玉で崩す方法の数」を表すことにします.(と言っても{n\ge 0}ならば常に{A_n = 1}なのですが).

また,{B_n}によって「{n}円を一円玉と五円玉で崩す方法の数」を,

{C_n}によって「{n}円を一円玉と五円玉と十円玉で崩す方法の数」を,

{D_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を,

{E_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を,

最後に{F_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします.

このように定式化すると,クイズの答えは{F_{1000}}と表されます.あとはこの具体的な数値を求めれば良いわけです.

さて,{F_n}はを「n円を五百円玉を一枚も使わないで表した場合の数」と「(n-500)円をすべてのコインを好きなだけ使って表した場合の数」の和だと考えられます.
(追記2018/08/27 少し説明を補います.{n}円を全てのコインを使って崩した場合を全て列挙した集合を{X}としましょう.{X}を (i)五百円玉を一つも含まないもの (ii)少なくとも1枚の五百円玉を含むもの に分割できます.それぞれの場合からなる集合を{X_1,X_2}としましょう.{X = X_1 + X_2} (非交和)ですから,{|X| = |X_1| + |X_2|} となります.明らかに{|X_1| = E_n}です.{X_2}の全ての要素から五百円玉を一つ抜くと,それぞれは{n-500}円を崩したものになっています.したがって{|X_2| = F_{n-500}}です.
).よって

{F_n = E_n + F_{n-500}}

となります.よって,{F_n}の計算を{E_{n},\,F_{n-500}}の計算に還元できます.

同様に考えれば
{E_n = D_n + E_{n-100}}などの式が得られます.ただし,負のインデックスに対しては{A_n, B_n, C_n, D_n, E_n, F_n}はいずれもゼロとします.この考えをそのままHaskellコードにすれば次のようになります:

fA n | (n < 0) = 0
     | otherwise = 1

fB n | (n < 0) = 0
     | otherwise = fA n + fB (n-5)

fC n | (n < 0) = 0
     | otherwise = fB n + fC (n-10)

fD n | (n < 0) = 0
     | otherwise = fC n + fD (n-50)

fE n | (n < 0) = 0
     | otherwise = fD n + fE (n-100)

fF n | (n < 0) = 0
     | otherwise = fE n + fF (n-500)

これらの定義を書いてGHCiで:l 1000yen.hs してやってから fF 1000 を計算させると248908という答えが得られます.

したがって,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って千円を両替する方法は全部で248908通りあることになります.

この問題はポリア他『組合せ論入門』p.11(近代科学社)で扱われている問題を改変したものです.(元の問題は1ドルを1セント,5セント,10セント,25セント,50セントで崩す問題です.)この問題はポリアのお気に入りだったのか,Pólya & Szegö “Problems and Theorems in Analysis I” にも収録されています.)

この記事では漸化式を組み合わせ論的な考えで導きましたが,ポリアの本では母関数を利用して漸化式を導いています.興味のある方は是非ポリアの『組合せ論入門』を読んでみてください.

無限小を用いた記述を標準的な記述に還元することについて

これはMath Advent Calendar 2017の12/8の記事です: mathAdventCalendar2017  (←リンク先PDF)

改訂情報

  • 2017/12/09: 式(24), 式(26)の脱字と誤字を訂正しました.(@waidotto 様,ありがとうございました.)
  • 2017/12/20: ISTの公理図式などの記述において,「FV」のような用語を使わないようにしました.

 

cos(x)+sin(x√2)の「周期っぽい長さ」を作る方法

{f(x) := \cos(x)+\sin(\sqrt{2}x)}とすると,これは明らかに周期関数ではないが,「周期っぽい長さ」が存在する.ある{l_\varepsilon}{f(x)}の「{\varepsilon}精度で周期っぽい長さ」であるということを次の条件で定義しよう:

\displaystyle{\sup_{x\in\Bbb{R}}\lvert f(x) - f(x+l_\varepsilon) \rvert < \varepsilon.}

このような「周期っぽい長さ」を機械的に作ってみよう.{\cos(x)}は周期{2\pi}で,{\sin(\sqrt{2}x)}は周期{\sqrt{2}\pi}なので
{\cos(x+l_\varepsilon) \fallingdotseq \cos(x),}
{\sin(\sqrt{2}x + \sqrt{2}l_\varepsilon) \fallingdotseq \sin(\sqrt{2}x).}
であればよい.よって
{l_\varepsilon \fallingdotseq 0\enskip(\mod 2\pi),\enskip l_\varepsilon \fallingdotseq 0\enskip(\mod \sqrt{2}\pi).}
そこである{a,b\in\Bbb{Z}}があって
{l_\varepsilon \fallingdotseq 2a\pi \fallingdotseq \sqrt{2}b\pi}
となっていれば良いことになる.

補足:近似({\fallingdotseq})による「アバウトな」議論がうまく行く事は,{\cos(x)}{\sin(\sqrt{2}x)}{\Bbb{R}}上一様連続であることを使えばうまく説明できる.

このような整数{a,b}を上手く見つけるために{\Bbb{Z}[\sqrt{2}]}が積について閉じていることに注目する.また,{0 < \sqrt{2}-1 < 1}という不等式にも注目する.よく知られているように,絶対値が{1}より小さい数のべき乗はゼロに収束する.そこで例えば
{(\sqrt{2}-1)^{2n} = b_n - \sqrt{2}a_n}
としてやれば,{2a_n \fallingdotseq \sqrt{2}b_n}となるような整数{a_n,\,b_n}を作り出すことができるはずである.{(\sqrt{2}-1)^{2n}}の二項展開を利用して具体形を求めれば

\displaystyle{a_n = \sum_{k=1}^n \binom{2n}{2k-1}2^{k-1},}

\displaystyle{b_n = \sum_{k=1}^n \binom{2n}{2k} 2^k.}

となる.