▲

무한의 기묘한 수학과 컴퓨터 과학을 잇는 새로운 다리

 (quantamagazine.org)
2P by GN⁺ 7일전 | ★ favorite | 댓글 1개
  • 무한 집합의 구조를 연구하는 기술적 분야인 기술적 집합론이 알고리듬 언어로 재해석될 수 있음이 밝혀짐
  • 수학자 Anton Bernshteyn은 무한 그래프의 문제가 컴퓨터 네트워크의 통신 문제로 다시 쓸 수 있음을 증명
  • 이 연결은 측정 가능성(measurability) 과 분산 알고리듬 효율성 사이의 대응 관계를 보여줌
  • 연구자들은 이 다리를 통해 양쪽 분야의 정리와 문제를 상호 변환하며 새로운 결과를 도출 중
  • 무한과 계산의 경계를 재정의하며, 수학과 컴퓨터 과학의 협력 가능성을 확장하는 발견

서론: 집합론과 무한의 세계

  • 현대 수학의 기초는 집합론에 기반하며, 대부분의 수학자는 이를 전제로 문제를 다룸
  • 그러나 기술적 집합론자(descriptive set theorists) 는 무한 집합의 본질을 계속 탐구하는 소수의 연구자 집단임
  • 2023년 Anton Bernshteyn은 기술적 집합론과 컴퓨터 과학 간의 깊은 연결을 발견
    • 특정 무한 집합의 문제를 컴퓨터 네트워크의 통신 문제로 변환 가능함을 보임
  • 이 결과는 논리와 알고리듬, 무한과 유한이라는 상반된 언어를 잇는 다리로 평가됨

기술적 집합론의 배경

  • 집합론의 기원은 게오르크 칸토어(Georg Cantor) 의 연구로, 서로 다른 무한의 크기를 증명한 데서 시작
  • 집합의 크기를 나타내는 개념에는 기수(cardinality) 와 측도(measure) 가 있음
    • 예: 0~1 구간의 실수 집합과 0~10 구간의 실수 집합은 같은 기수를 가지지만, 측도는 각각 1과 10
  • 기술적 집합론은 측정 가능한 집합과 비측정 집합을 구분하고, 이를 복잡도 계층(hierarchy) 으로 분류
  • 이 계층은 다른 수학 분야(예: 확률론, 동역학계, 군론)에서 적절한 도구 선택의 기준이 됨

무한 그래프와 색칠 문제

  • Bernshteyn은 무한 그래프를 연구하며, 각 그래프의 노드와 간선을 무한히 연결된 구조로 모델링
  • 예시: 원 위의 점들을 일정한 간격으로 연결하면, 유리수 간격일 때는 닫힌 고리, 무리수 간격일 때는 무한 연결 구조 형성
  • 그래프의 노드를 두 가지 색으로 칠할 때, 선택 공리(axiom of choice) 를 사용하면 가능하지만 비측정 집합이 됨
  • 반면, 연속적 색칠 방식을 사용하면 세 가지 색이 필요하지만 측정 가능한 집합을 얻을 수 있음
  • 이 차이는 집합론적 복잡도 계층의 위치를 결정하는 핵심 요소로 작용

분산 알고리듬과의 만남

  • 2019년 Bernshteyn은 분산 알고리듬(distributed algorithms) 에 관한 컴퓨터 과학 강연을 듣고 유사성을 발견
    • 예: Wi-Fi 라우터가 서로 간섭하지 않도록 주파수(색상) 를 다르게 선택하는 문제
  • 각 노드는 이웃 노드와만 통신하며 색을 정하는 지역 알고리듬(local algorithm) 을 사용
  • 두 가지 색으로는 비효율적이지만, 세 가지 색을 허용하면 효율적 해결 가능
  • Bernshteyn은 이 색상 수의 임계값(threshold) 이 기술적 집합론의 측정 가능한 색칠 문제의 임계값과 동일함을 인식

두 세계의 등가성 증명

  • Bernshteyn은 효율적인 지역 알고리듬 ↔ 측정 가능한 색칠 방식 간의 등가성을 수학적으로 증명
  • 유한 그래프에서는 각 노드에 고유 번호를 부여할 수 있지만, 비가산 무한 그래프에서는 불가능
  • 그는 인접 노드 간 중복되지 않는 라벨링 방식을 고안해, 알고리듬을 무한 그래프에도 확장 가능하게 함
  • 결과적으로 “모든 지역 알고리듬은 기술적 집합론의 측정 가능한 색칠 방식에 대응”함이 증명됨
  • 이는 계산 가능성과 정의 가능성(definability) 사이의 깊은 수학적 연결을 보여줌

연구 확장과 응용

  • Václav Rozhoň 등은 이 연결을 이용해 트리(tree) 그래프 색칠 문제를 해결하고, 동역학계 연구 도구를 도출
  • 반대로, 집합론의 방법을 사용해 문제 난이도 추정을 개선한 연구도 진행됨
  • 이 다리는 단순한 문제 해결 도구를 넘어, 집합론의 분류 체계 재정립에 기여
  • 기술적 집합론자들은 이제 컴퓨터 과학의 체계적 분류 방식을 참고해 미분류 문제를 정리 가능
  • Bernshteyn은 이 연구가 무한 개념을 실질적 수학의 일부로 인식시키는 계기가 되길 기대함
▲
GN⁺ 7일전  [-]
Hacker News 의견

  • 이런 결과가 분산 컴퓨팅 같은 실제 분야에 응용될 수 있는지 궁금함. 아니면 순수 수학적인 흥미로만 존재하는 것인지 의문임

    • 전혀 바보 같은 질문이 아님. 기술적 통찰이 분산 알고리즘이나 계산 복잡도 이론에서 새로운 불가능성 정리로 이어질 수도 있음. 메시 네트워킹 같은 응용 가능성도 흥미로움

  • “모든 현대 수학은 집합론 위에 세워졌다”는 말은 너무 단정적임. Lean이나 Rocq 같은 현대 수학 도구들은 형식화된 수학(formalized mathematics) 기반으로 발전 중이며, 이는 형식 이론(type theory) 위에 세워져 있음

    • 나는 수학자는 아니지만, ZFC는 여전히 유효한 기초 체계라고 생각함. 종속형(dependent types) 은 정리 증명 관리에 유용하지만, 더 많은 정리를 증명하게 해주지는 않음. Lawrence Paulson의 Isabelle/HOL은 타입 기반이 아니지만 대부분의 수학을 증명할 수 있음
    • 하지만 실제 수학자들은 형식화된 수학을 거의 사용하지 않음. 알고 있어도 불편함 때문에 기초 언어로 쓰지 않음
    • 수학의 언어와 그 언어에 대해 증명하는 형식 언어를 혼동하면 안 됨. 전자는 거의 전적으로 집합을, 후자는 필연적으로 타입을 사용함
    • 보다 정확히 말하면, 수학의 기초 위기는 집합론의 형식화로 일단락되었다고 보는 게 맞음

  • “cons’es all the way down”이라는 농담식 표현으로, 재귀적 구조를 풍자함

  • “드디어 무한을 계산할 수 있다”는 말에 감격함

    • 다음 달 Bay Area에서 The Dillinger Escape Plan의 Calculating Infinity 투어가 열린다고 함. 공연 링크. 수학, 해킹, mathcore 팬층이 겹칠 것 같아 공유함
    • “무한을 계산한다”는 말에 “그리고 그 너머로!”라고 응답하며 농담을 이어감
    • Haskell에서는 let x = x in x 한 줄로 가산 무한(countable infinity) 을 표현할 수 있다고 함
    • “Chuck Norris가 1부터 무한까지 두 번 셌다”는 밈으로 유머를 덧붙임
    • “이건 정말 오래 걸렸음 /s”라며 풍자적 표현을 덧붙임

  • “컴퓨터 과학은 유한한 것만 다룬다”는 주장에 동의하지 않음. 실제로 컴퓨터 과학은 무한에 깊이 관여함

    • Quanta가 이런 식으로 다루는 건 흔한 일임. 대중 과학식 서술로 인물 중심 이야기에 집중하고, 세부 내용은 생략하는 경향이 있음
    • 다만 컴퓨터 과학은 비가산 무한(uncountable infinity) 에는 관심이 적음. 측도론(measure theory) 은 주로 그쪽을 다룸
    • 나도 처음엔 “CS는 무한을 근사한다”고 생각했지만, 실제로는 근사(approximation) 라는 말이 핵심임. 우리는 항상 유한한 경계 안에서만 일함. 우주가 무한하더라도 우리가 관측할 수 있는 범위는 빛의 속도로 제한됨
    • “컴퓨터 과학은 논리를 사용하지 않는다”는 식의 문장은 너무 게으른 표현임. Boolean 논리가 바로 그 증거임

  • 나는 오랫동안 수학을 공부했는데, 무한(infinity) 은 존재하지 않는다고 믿게 되었음. 수학은 무한이 없을 때 더 나을 수도 있다고 생각함

    • 나도 공학 수준의 수학만 배웠지만, 무한은 숫자가 아니라 과정(process) 이라고 생각함. {1, 2, 3, ...}의 “...”는 끝이 없는 확장 과정을 의미함. 무한번째 소수 같은 건 없고, 더 큰 소수가 항상 존재한다는 생성 규칙만 있을 뿐임
    • 하지만 무한을 제거하면 수학이 끔찍하게 복잡해짐. 자연수를 끝없이 확장하지 않는다면 계산이 매우 불편해짐
    • 수학은 존재 여부보다는 개념적 유용성에 관심이 있음. 원도 현실에 존재하지 않지만 유용함. 무한이 없다면 결국 “x가 매우 매우 큰 수로 갈 때의 극한” 같은 형태로 다시 발명해야 함
    • “8에서 멈추면 된다”는 농담으로 무한의 불필요함을 풍자함
    • 무한은 끝나지 않는 과정을 가리키는 이름일 뿐임. 어떤 과정은 더 빠르게 증가하기 때문에 더 큰 무한이 존재함. 개인적으로는 Riemann 구 모델의 무한 개념을 좋아함

  • “node_modules”가 내 파일 시스템에 무한의 수학을 연결해놓았다는 농담으로, 의존성 폭증을 풍자함

  • “모든 현대 수학은 집합론 위에 세워졌다”는 문장에 반박하며, 형식 이론(Type Theory) 도 있다고 지적함

    • Type Theory는 ZFC보다 더 강력한 공리 체계임. 관련 설명은 MathOverflow 답변 참고
    • 하지만 ZF나 ZFC만큼 영향력 있는 형식 이론 공리 집합은 아직 없음
    • 기술적으로 기술적 집합론(descriptive set theory) 은 기초적 집합론과는 별개임. 타입과 공간 개념으로 쉽게 재구성할 수 있으며, 이는 종종 더 유리함. 수학적 무한을 계산적 관점으로 재해석하는 건 새로운 시도가 아님
    • “추상적 객체의 집합을 조직하는 학문”이라는 설명은 집합론을 너무 단순화한 표현임. 그래도 대부분의 수학은 여전히 집합 공리로부터 정의되는 것이 사실임
답변달기