빈 그래프는 수형도인가

트위터에서 empty graph가 tree가 아닌 forest로 분류되어야하는지에 대한 이야기가 있었는데 (원본 트윗은 쓰신 분이 플텍 걸어놔서 보이지 않는다) 여러모로 봤을 때 forest로 보는 것이 타당하다. 이게 문제가 된 이유는 tree의 정의들을 생각해보면 ‘임의의 두 점이 정확히 한 개의 경로로 연결되는 그래프’, ‘연결되고 cycle이 없는 그래프’ 등이 있는데 전자 같은 경우 뽑을 두 점이 애초에 없으니 vacuously true가 될 수 있지 않겠냐는 것.

뭐 일단 가장 간단하게 tree가 아님을 보일 수 있는 방법으로는 유한 tree의 경우 점의 개수를 , 변의 개수를 라 하면 이 성립해야 하는데 empty graph의 경우 이라서 그렇지 않다는 것이 있겠다.

또 다른 간접적인 증거의 예로는 생성함수를 생각해볼 수 있다. 개의 점에 대한 (unordered rooted) tree 개수의 지수생성함수를 라 두면 개의 점에 대한 forest 개수의 지수생성함수는 가 되는데, 여기서 이어야 를 정의할 수 있다. 즉 점의 개수가 0인 tree의 개수가 0으로 정의하는 것이 좋고, 그렇게 정의된 경우 , 즉 점이 0개인 forest의 개수가 1이 되는걸 얻을 수 있고 이것이 곧 empty graph가 된다.

최소한 empty graph는 forest인 것이 자연스러워진다. 실제로 forest의 정의로 ‘cycle이 없는 그래프’란 것이 있고 empty graph도 이를 일단 만족시키니. forest에서 연결된 component의 개수를 라 하면 가 되므로 이 경우는 이 되어, 결국 empty forest는 0개의 tree로 이루어진 forest라 볼 수 있겠고, tree는 1개의 tree로 이루어진 forest여야 하니 tree로 분류되는 것은 자연스럽지 않다.

그러면 empty graph가 tree, 즉 ‘연결되고 cycle이 없는 그래프’가 되지 못한다는 것은 무슨 이유일까. 이는 empty graph가 실은 연결그래프로 보지 않는 편이 자연스럽기 때문이다. empty graph가 tree인지 forest인지에 대한 질문이 math overflow에도 올라온 적이 있는데, (여기서도 앞에서 언급한 생성함수를 이용한 논증이 언급된다) 테런스 타오 선생님도 empty tree의 경우 connected도 disconnected도 아닌 유일한 예로 보는 편이 낫다는 이야기를 하신다. disconnected는 connected한 부분으로 나눌 수 있다는 것을 생각하면, 자연수에서 소수와 합성수로 유비할 수 있는데 이 때 1은 소수도 합성수도 아니라고 하는 것과 비슷한 이야기라는 것.

위 링크에서는 그 외 다른 관점으로도 empty graph가 tree는 아니지만 0개의 tree를 갖는 forest로 보는 편이 타당하다는 이야기들이 나온다. 위상수학적인 관점이나 범주론적인 관점이 그것인데, 후자의 경우는 empty graph가 연결이 아님을 다음과 같이 논증하고 있다. 카테고리 가 있어, coproduct가 finite하고 임의의 두 에 대해 그 coproduct를 $a+b$라 하면 canonical functor 가 equivalence가 될 때 이를 extensive category라 한다. 위상공간의 카테고리나 그래프의 카테고리 등이 extensive한 카테고리의 예이다. 이 때 만약 functor 가 binary coproduct를 유지한다면 를 connected라고 볼 수 있다. 이 관점에서 empty graph, 더 나아가 empty space와 같은 initial object는 connected라고 볼 수 없다.

이 글에서는 이 일반적인 주제인 empty space가 연속인가에 대해 그 답이 부정적임을 뜻하는 여러 정황적 증거들을 제시하고 있다. 많은 것들은 앞의 math overflow에서도 다뤄졌고, 하나 간단한 것도 있는데 만약 empty space가 연속이라면 “가 연속임은 가 모두 연속임과 동치이다”란 명제가 깨져버린다는 것이다. (, 를 연속이 아닌 임의의 집합으로 잡음)

이렇게 1이 prime으로 볼 수 없고 empty graph, empty space가 연결이 아닌 것은 곧 다음과 같은 철학으로 귀결된다.

A trivial object is too simple to be simple.

nLab의 한 글에서 이에 대한 설명이 나타나 있다. 수학에서는 trivial한 것을 “simple”하다고 분류해버리는 것보다는 그렇지 않도록 분류하는 편이 다른 정리들이 더 잘, 혹은 더 깔끔하게 들어맞게 할 수 있다는 것이다. 앞에서 잡은 예들 역시 그렇고, trivial ring이 field가 될 수 없다든지 trivial group이 simple group이 될 수 없다든지 등등. 이런 관점 하에서 공집합은 집합이 아니라고 분류하거나 trivial ring은 환이 아니라고 주장하는 경우가 많았다고 한다.

트윗 타래를 정리. (2019/09/14)

여기서 [x^0]f를 0으로 정의해야 e^f(x)를 정의할 수가 있기 때문에 |V|=0이면 tree는 없다고 생각하고, [x^0]e^f(x)는 1이 되는데 그에 해당하는 설명이 바로 "tree 개수가 0개인 forest 1개"가 되는 것

— 유닼 (@udaqueness) September 14, 2019