hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
실질 비함의 정의
비함의는 실질 함축의 부정으로 정의될 수 있다.
고전 논리에서는 와 의 논리합의 부정과도 동치이며, 와 의 논리곱과도 동치이다.
실질 비함의 속성
거짓 보존: 모든 변수에 "거짓"의 진릿값이 할당되는 해석은 비함의의 결과로 "거짓"의 진릿값을 산출한다.
실질 비함의 기호
비함의의 기호는 단순히 실질 함축 기호에 줄을 그은 것이다. 유니코드 기호는 219B16 (십진수 8603): ↛이다.
실질 비함의 자연어
"p 마이너스 q."
"p 빼기 q."
"p 그러나 q는 아님."
"p에도 불구하고 q는 거짓이다."
실질 비함의 컴퓨터 과학
비트 단위 연산: A & ~B. 이는 보통 "비트 클리어"(BIC) 또는 "앤드 낫"(ANDN)이라고 부른다.
논리 연산: A && !B.
진리 함수
논리학에서 진리 함수(truth function)는 진릿값을 입력으로 받아 고유한 진릿값을 출력하는 함수이다. 다시 말해, 진리 함수의 입력과 출력은 모두 진릿값이다. 진리 함수는 항상 정확히 하나의 진릿값을 출력하며, 동일한 진릿값(들)을 입력하면 항상 동일한 진릿값이 출력된다. 전형적인 예는 명제 논리에서 복합 명제가 논리 연산으로 연결된 개별 명제들을 사용하여 구성되는 경우이다. 만약 복합 명제의 진릿값이 구성 명제(들)의 진릿값에 의해 전적으로 결정된다면, 복합 명제는 진리 함수라고 불리며, 사용된 모든 논리 연산은 진리 함수적이라고 한다.
고전 명제 논리는 진리 함수적 논리이다. 이는 모든 명제가 참 또는 거짓 중 정확히 하나의 진릿값을 가지며, 모든 논리 연산이 진리 함수적(대응하는 진리표를 가짐)이므로 모든 복합 명제가 진리 함수이기 때문이다. 반면에 양상 논리는 비진리 함수적이다.
진리 함수 개요
복합 문장의 진릿값이 하위 문장의 진릿값의 함수인 경우, 논리 연산은 진리 함수적이다. 논리 연산의 집합은 각 구성원이 진리 함수적일 경우 진리 함수적이다. 예를 들어, "그리고" 연산은 진리 함수적이다. 왜냐하면 "사과는 과일이고 당근은 채소이다"와 같은 문장은 "사과는 과일이다"와 "당근은 채소이다"라는 각 하위 문장이 참일 때만 참이고, 그렇지 않으면 거짓이기 때문이다. 영어와 같은 자연어의 일부 논리 연산은 진리 함수적이 아니다.
"x는 ...라고 믿는다" 형식의 논리 연산은 진리 함수적이 아닌 연산의 전형적인 예이다. 예를 들어 메리가 2000년 4월 20일에 앨 고어가 미국 대통령이었다고 잘못 믿지만, 달이 녹색 치즈로 만들어졌다고는 믿지 않는다고 가정하자. 그렇다면 다음 문장은
"메리는 앨 고어가 2000년 4월 20일에 미국 대통령이었다고 믿는다"
진리 함수 개요
는 참이지만, 다음 문장은
"메리는 달이 녹색 치즈로 만들어졌다고 믿는다"
는 거짓이다. 두 경우 모두, 각 구성 문장(즉, "앨 고어는 2000년 4월 20일에 미국 대통령이었다"와 "달은 녹색 치즈로 만들어졌다")은 거짓이지만, "메리는 ...라고 믿는다"라는 구를 접두사로 붙여 형성된 각 복합 문장은 진릿값이 다르다. 즉, "메리는 ...라고 믿는다" 형식의 문장의 진릿값은 구성 문장의 진릿값만으로는 결정되지 않으므로, (단항) 논리 연산 (또는 단항이므로 단순히 연산자)은 비진리 함수적이다.
공식 구성에 사용되는 고전 논리 연산(예: &, →)은 진리 함수적이다. 인수로 다양한 진릿값을 사용할 때의 값은 일반적으로 진리표로 주어진다. 진리 함수적 명제 논리는 공식이 참 또는 거짓으로 해석될 수 있는 형식 체계이다.
진리 함수 이항 진리 함수 표
2가 논리에서 두 입력 P와 Q에 대한 16가지 가능한 진리 함수가 있으며, 이를 불 함수라고도 한다. 이 함수들 각각은 고전 논리에서 특정 논리 연산의 진리표에 해당하며, 인수의 하나 또는 둘 모두에 의존하지 않는 함수와 같은 몇 가지 퇴화된 경우도 포함한다. 다음 진리표에서는 간결성을 위해 참은 1, 거짓은 0으로 표시한다.
진리 함수 함수적 완전성
함수는 합성으로 표현될 수 있으므로, 진리 함수적 논리 계산은 함수적으로 완전하기 위해 위에 언급된 모든 함수에 대한 전용 기호를 가질 필요가 없다. 이는 명제 논리에서 특정 복합 명제의 논리적 동치로 표현된다. 예를 들어, 고전 논리에서 ¬P ∨ Q는 P → Q와 동치이다. 따라서 "¬"(부정)와 "∨"(논리합)가 이미 사용 중이라면 조건 연산자 "→"는 고전 기반 논리 체계에 필수적이지 않다.
명제 논리에서 표현 가능한 모든 명제를 표현할 수 있는 최소 연산자 집합을 최소 함수적 완전 집합이라고 한다. 최소 완전 집합의 연산자는 NAND만 {↑} 또는 NOR만 {↓}으로 달성된다.
아리티가 2를 초과하지 않는 최소 함수적 완전 연산자 집합은 다음과 같다.
하나의 원소
{↑}, {↓}.
두 개의 원소
, , , , , , , , , , , , , , , , , .
세 개의 원소
, , , , , .
진리 함수 대수적 속성
일부 진리 함수는 해당 논리 연산을 포함하는 정리로 표현될 수 있는 속성을 가지고 있다. 이항 진리 함수(또는 해당 논리 연산)가 가질 수 있는 속성 중 일부는 다음과 같다.
진리 함수 집합은 다음 다섯 가지 속성 각각에 대해 이를 결여하는 구성원을 적어도 하나 포함할 때에만 함수적으로 완전하다.
구체적인 함수는 연산자로도 지칭될 수 있다. 2가 논리에는 2개의 널항 연산자(상수), 4개의 단항연산, 16개의 이항 연산자, 256개의 삼항 연산자, 그리고 개의 n항 연산자가 있다. 3가 논리에는 3개의 널항 연산자(상수), 27개의 단항연산, 19683개의 이항 연산자, 7625597484987개의 삼항 연산자, 그리고 개의 n항 연산자가 있다. k가 논리에는 k개의 널항 연산자, 개의 단항 연산자, 개의 이항 연산자, 개의 삼항 연산자, 그리고 개의 n항 연산자가 있다. k가 논리의 n항 연산자는  함수이다. 따라서 이러한 연산자의 수는 이며, 위의 숫자들이 여기서 유도되었다.
진리 함수 대수적 속성
그러나 특정 항수를 가진 일부 연산자는 실제로 일부 입력에 대해 더 낮은 항수 연산을 수행하고 나머지 입력은 무시하는 퇴화된 형태이다. 위에 언급된 256개의 삼항 불 연산자 중 개는 포함배제의 원리를 사용하여 이항 또는 그 이하 항수 연산자의 퇴화된 형태이다. 삼항 연산자 는 실제로 하나의 입력에 적용되고 다른 두 입력은 무시하는 단항 연산자이다.
"부정"은 단항 연산자이며, 단일 항(¬P)을 취한다. 나머지는 이항 연산자이며, 두 항을 취하여 복합 명제(P ∧ Q, P ∨ Q, P → Q, P ↔ Q)를 만든다.
논리 연산자 집합 Ω는 다음과 같이 서로소 부분 집합으로 분할될 수 있다.
이 분할에서 는 항수 j의 연산자 기호 집합이다.
더 익숙한 명제 논리에서는 가 일반적으로 다음과 같이 분할된다.
널항 연산자:
단항 연산자:
이항 연산자:
진리 함수 구성성 원리
진리표를 사용하는 대신, 논리 연산 기호는 의미의 구성성 원리에 의해 상세히 설명된 바와 같이, 해석 함수와 함수적으로 완전한 진리 함수 집합(Gamut 1991)을 통해 해석될 수 있다.
I를 해석 함수라 하고, Φ, Ψ를 두 임의의 문장이라 하며, 진리 함수 fnand를 다음과 같이 정의하자.
그러면 편의를 위해 fnot, for, fand 등은 fnand를 통해 다음과 같이 정의된다.
또는 대안적으로 fnot, for, fand 등은 직접 다음과 같이 정의된다.
그러면
등.
따라서 S가 논리 연산자를 나타내는 논리 기호 v1...vn과 비논리 기호 c1...cn으로 구성된 기호열인 문장이라고 하자. 그러면 I(v1)...I(vn)이 fnand(또는 다른 함수적으로 완전한 진리 함수 집합)를 통해 v1부터 vn까지를 해석하도록 제공된 경우에만 의 진릿값은 c1...cn의 진릿값, 즉 I(c1)...I(cn)에 의해 전적으로 결정된다. 다시 말해, 예상대로 S는 모든 비논리 기호의 해석 하에서만 참 또는 거짓이다.
진리 함수 정의
위에 정의된 함수들을 사용하여, 명제의 진리 함수에 대한 형식적인 정의를 내릴 수 있다.
PROP를 모든 명제 변수의 집합이라고 하자.
진리 할당은 임의의 함수 로 정의한다. 진리 할당은 따라서 각 명제 변수를 특정 진릿값과 연결하는 것이다. 이는 명제의 진리표의 특정 행과 실질적으로 동일하다.
진리 할당 에 대해, 그 확장된 진리 할당 를 다음과 같이 정의한다. 이는 를 모든 명제 형식의 집합과 동일한 정의역을 갖는 새로운 함수 로 확장한다. 의 치역은 여전히 이다.
마지막으로, 확장된 진리 할당을 정의했으므로, 이를 사용하여 명제의 진리 함수를 정의할 수 있다. 명제 A에 대한 진리 함수 는 모든 진리 할당의 집합과 동일한 정의역을 가지며, 를 치역으로 가진다.
이는 각 진리 할당 에 대해 로 정의된다. 에 의해 주어진 값은 로 식별된 행에 있는 A의 진리표의 마지막 열에 표시된 값과 동일하다.
진리 함수 컴퓨터 과학
논리 연산자는 디지털 회로에서 논리 회로로 구현된다. 거의 모든 디지털 회로(주요 예외는 DRAM)는 NAND, NOR, NOT, 그리고 전송 게이트로 구성된다. 일반적으로 2개 입력 대신 3개 이상의 입력을 가진 NAND 및 NOR 게이트는 상당히 일반적이지만, 논리적으로는 2개 입력 게이트의 캐스케이드와 동등하다. 다른 모든 연산자는 위의 2개 이상의 논리 게이트의 논리적으로 동등한 조합으로 분해하여 구현된다.
"NAND만", "NOR만", "NOT과 AND"의 "논리적 동등성"은 튜링 동치와 유사하다.
모든 진리 함수가 NOR만으로 표현될 수 있다는 사실은 아폴로 가이던스 컴퓨터에 의해 입증되었다.
성 마태오의 영감
성 마태오의 영감(The Inspiration of Saint Matthew, 이탈리아어: San Matteo e angelo)은 이탈리아 바로크 대가 미켈란젤로 메리시 다 카라바조가 1602년에 그린 캔버스 유화이다. 프랑스 추기경 마티외 캥테렐의 의뢰로 제작된 이 그림은 로마의 프랑스 교단 산 루이지 데이 프란체시 성당의 콘타렐리 예배당 제단에 걸려 있다.
이 그림은 예배당에 있는 카라바조의 세 작품 중 하나로, 이전에 그려진 성 마태오의 순교와 성 마태오를 부르심 사이에 걸려 있다. 이것은 카라바조에게 쉬운 의뢰가 아니었으며, 세 그림 중 적어도 두 개는 후원자인 프란체스코 마리아 델 몬테 추기경가 만족하지 못해 교체되거나 다시 그려져야 했다.
성 마태오의 영감 제작
1602년 2월, 예배당에 그의 첫 두 작품이 설치된 후 카라바조는 그 해 오순절까지 납품될 제단화를 제작하라는 의뢰를 받았다. 그가 처음 그린 그림인 성 마태오와 천사는 거부되었다. (이 작품은 제2차 세계 대전 중에 우연히 파괴되었다.)
그 후 이 작품은 비교적 빠르게 완성하였으며, 카라바조는 1602년 9월에 대금을 받았다.
성 마태오의 영감 묘사
천사는 공중에 떠 있는 숭고한 차원에 속하며, 물결치는 주름진 시트에 둘러싸여 있다. 불안해하는 마태오는 작업대에 몸을 기울이고, 천사는 그에게 앞으로 해야할 작업을 설명한다. 두 개의 큰 인물을 제외하고 모든 것이 어둠이다. 마태오는 서둘러 책상으로 달려온 듯하고, 그의 의자는 그림 공간 바깥으로 튀어나와 기울어져 있다. 마태오는 진지한 표정을 짓고 있다.
성 마태오의 영감 더 읽어보기
Jürgen Müller, Das geöffnete Buch. Caravaggios Altargemälde ‚Die Inspiration des Evangelisten Matthäus durch den Engel‘ in der Contarelli-Kapelle und die Laienlektüre der Bibel, in: Kunstgeschichte. Open Peer Reviewed Journal, 2021
도메인 특화 모델링
도메인 특화 모델링(domain-specific modeling, DSM)은 컴퓨터 소프트웨어와 같은 시스템을 설계하고 개발하는 소프트웨어 공학 방법론이다. 이 방법론은 도메인 특화 언어를 체계적으로 사용하여 시스템의 다양한 측면을 나타낸다.
도메인 특화 모델링 언어는 범용 모델링 언어보다 높은 수준의 추상화를 지원하는 경향이 있으므로, 주어진 시스템을 지정하는 데 더 적은 노력과 낮은 수준의 세부 정보가 필요하다.
도메인 특화 모델링 개요
도메인 특화 모델링은 종종 코드 생성의 개념, 즉 도메인 특화 언어 모델에서 실행 가능한 소스 코드 생성을 자동화하는 것을 포함한다. 소스 코드의 수동 생성 및 유지 관리로부터 자유로워진다는 것은 도메인 특화 언어가 개발자 생산성을 크게 향상시킬 수 있음을 의미한다. 수동 코딩에 비해 자동 생성의 신뢰성은 결과 프로그램의 결함 수를 줄여 품질을 향상시킬 것이다.
도메인 특화 언어는 1980년대의 CASE 도구나 1990년대의 UML 도구에서 시도된 이전의 코드 생성 시도와는 다르다. 이 두 가지 모두에서 코드 생성기와 모델링 언어는 도구 공급업체에 의해 구축되었다. 도구 공급업체가 도메인 특화 언어 및 생성기를 만들 수 있지만, 도메인 특화 언어가 하나의 조직 내에서 발생하는 것이 더 일반적이다. 한두 명의 전문 개발자가 모델링 언어와 생성기를 만들고, 나머지 개발자가 이를 사용한다.
도메인 특화 모델링 개요
모델링 언어와 생성기를 사용할 조직이 구축하면, 해당 도메인의 정확한 요구 사항에 밀접하게 부합하고 도메인 변경에 대응할 수 있다.
도메인 특화 언어는 일반적으로 특정 도메인에 대한 다양한 추상화 수준을 포괄할 수 있다. 예를 들어, 휴대폰용 도메인 특화 모델링 언어는 사용자가 사용자 인터페이스에 대한 고수준 추상화를 지정할 뿐만 아니라 전화번호나 설정과 같은 데이터 저장에 대한 저수준 추상화를 지정할 수 있게 해준다. 마찬가지로, 금융 서비스용 도메인 특화 모델링 언어는 사용자가 클라이언트에 대한 고수준 추상화를 지정할 뿐만 아니라 주식 및 채권 거래 알고리즘 구현을 위한 저수준 추상화를 지정할 수 있게 해준다.
도메인 특화 모델링 주제
언어를 정의하려면 정의를 작성할 언어가 필요하다. 모델의 언어는 종종 메타모델이라고 불리므로, 모델링 언어를 정의하기 위한 언어는 메타-메타모델이다. 메타-메타모델은 두 그룹으로 나눌 수 있다: 기존 언어에서 파생되거나 사용자 정의된 언어와 특히 메타-메타모델로 개발된 언어이다.
파생된 메타-메타모델에는 개체-관계 모델, 형식 언어, EBNF, 온톨로지 언어, XML 스키마, 그리고 메타 오브젝트 퍼실리티 (MOF)가 포함된다. 이 언어들의 강점은 원본 언어의 친숙함과 표준화에 있다.
도메인 특화 모델링의 정신은 특정 작업을 위한 새로운 언어의 생성을 선호하므로, 메타-메타모델로 설계된 새로운 언어가 있다는 것은 놀라운 일이 아니다. 이러한 언어 중 가장 널리 사용되는 계열은 OPRR, GOPRR 및 GOPPRR이며, 이들은 최소한의 노력으로 모델링 언어에서 발견되는 것을 지원하는 데 중점을 둔다.
도메인 특화 모델링 주제
많은 범용 모델링 언어는 이미 CASE 도구의 형태로 도구 지원을 제공하고 있다. 도메인 특화 언어는 맞춤형 CASE 도구를 처음부터 구축하기에는 시장 규모가 너무 작은 경향이 있다. 대신, 도메인 특화 언어에 대한 대부분의 도구 지원은 기존 도메인 특화 언어 프레임워크를 기반으로 하거나 도메인 특화 언어 환경을 통해 구축된다.
도메인 특화 언어 환경은 메타모델링 도구, 즉 모델링 도구 또는 CASE 도구를 정의하는 데 사용되는 모델링 도구로 생각할 수 있다. 결과 도구는 도메인 특화 언어 환경 내에서 작동하거나, 덜 일반적으로는 별도의 독립 실행형 프로그램으로 생성될 수 있다. 더 일반적인 경우, 도메인 특화 언어 환경은 기존 CASE 도구에 비해 추가적인 추상화 계층을 지원한다.
도메인 특화 모델링 주제
도메인 특화 언어 환경을 사용하면 도메인 특화 언어에 대한 도구 지원을 얻는 비용을 크게 낮출 수 있다. 잘 설계된 도메인 특화 언어 환경은 도메인 특화 편집기, 브라우저 및 구성 요소와 같이 처음부터 구축하기에 비용이 많이 드는 프로그램 부분의 생성을 자동화하기 때문이다. 도메인 전문가는 도메인 특화 구성 요소 및 규칙만 지정하면 되며, 도메인 특화 언어 환경은 대상 도메인에 맞춤화된 모델링 도구를 제공한다.
대부분의 기존 도메인 특화 언어는 MetaEdit+ 또는 Actifsource와 같은 상용, GEMS와 같은 오픈 소스, 또는 GME와 같은 학술 도메인 특화 언어 환경에서 이루어진다. 도메인 특화 언어의 인기가 높아짐에 따라 EMF 및 GMF를 포함하는 Eclipse Modeling Project (EMP) 또는 Microsoft의 소프트웨어 팩토리용 DSL Tools와 같이 기존 IDE에 도메인 특화 언어 프레임워크가 추가되었다.
도메인 특화 모델링 도메인 특화 언어 및 UML
통합 모델링 언어 (UML)는 소프트웨어 집약적인 시스템을 위한 범용 모델링 언어로, 주로 객체 지향 프로그래밍을 지원하도록 설계되었다. 결과적으로, 도메인 특화 언어와는 달리 UML은 광범위한 도메인에 걸쳐 다양한 목적으로 사용된다. UML이 제공하는 기본 요소는 객체 지향 프로그래밍의 것이지만, 도메인 특화 언어는 해당 도메인의 모든 실무자에게 익숙한 의미론을 가진 기본 요소를 제공한다. 예를 들어, 자동차공학 도메인에서는 ABS 또는 스티어링 휠 등의 속성을 나타내는 소프트웨어 모델이 있을 것이다.
UML은 특정 도메인 및 플랫폼에 대해 제한하고 사용자 정의할 수 있는 프로파일 메커니즘을 포함한다. UML 프로파일은 스테레오타입, 스테레오타입 속성(UML 2.0 이전에는 태그 값으로 알려짐), 및 제약 조건을 사용하여 UML의 범위를 특정 도메인으로 제한하고 확장한다. 특정 도메인에 대해 UML을 사용자 정의한 가장 잘 알려진 예는 시스템 공학을 위한 도메인 특화 언어인 SysML이다.
도메인 특화 모델링 도메인 특화 언어 및 UML
UML은 소스 코드, 문서, 테스트 등과 같은 기술적 아티팩트가 도메인 모델에서 알고리즘적으로 생성되는 다양한 모델 기반 개발 접근 방식에서 널리 사용된다. 예를 들어, 법률 문서 표준 Akoma Ntoso의 애플리케이션 프로파일은 UML 클래스 객체에서 법률 개념 및 온톨로지를 표현함으로써 개발될 수 있다.
라이스의 정리
계산 가능성 이론에서 라이스의 정리(Rice's theorem)는 프로그램의 모든 비자명한 의미론적 속성이 판단 불가능하다고 말한다. 의미론적 속성은 프로그램의 동작에 관한 것이다 (예를 들어, "프로그램이 모든 입력에 대해 종료하는가?"), 이는 구문적 속성 (예를 들어, "프로그램에 if-then-else 문이 포함되어 있는가?")과는 다르다. 비자명한 속성은 모든 프로그램에 대해 참이거나 모든 프로그램에 대해 거짓이 아닌 속성이다.
이 정리는 정지 문제의 판단 불가능성을 일반화한다. 이는 프로그램의 정적 분석의 실현 가능성에 광범위한 영향을 미친다. 이는 예를 들어, 주어진 프로그램이 정확한지 또는 오류 없이 실행되는지 확인하는 도구를 구현하는 것이 불가능함을 의미한다 (항상 과대평가하거나 과소평가하는 도구를 구현하는 것은 가능하므로, 실제로는 어떤 것이 덜 문제인지 결정해야 한다).
이 정리는 1951년 시러큐스 대학교 박사 학위 논문에서 이를 증명한 헨리 고든 라이스의 이름을 따서 명명되었다.
라이스의 정리 서론
라이스의 정리는 어떤 유형의 정적 프로그램 분석을 자동으로 수행할 수 있는지에 대한 이론적 한계를 설정한다. 프로그램의 구문과 의미론을 구별할 수 있다. 구문은 프로그램이 작성되는 방식, 즉 "내포"의 세부 사항이며, 의미론은 프로그램이 실행될 때 어떻게 동작하는지, 즉 "외연"이다. 라이스의 정리는 속성이 자명하지 않은 한 (모든 프로그램에 대해 참이거나 모든 프로그램에 대해 거짓), 구문에 의존하지 않고 의미론에만 의존하는 프로그램의 속성을 결정하는 것이 불가능하다고 주장한다.
라이스의 정리에 따르면, 프로그램과 명세를 입력으로 받아 프로그램이 명세를 만족하는지 확인하여 다른 프로그램에서 버그의 부재를 자동으로 검증하는 프로그램을 작성하는 것은 불가능하다.
라이스의 정리 서론
이것이 특정 유형의 버그를 방지하는 것이 불가능하다는 것을 의미하지는 않는다. 예를 들어, 라이스의 정리는 튜링 완전한 동적 프로그래밍 언어에서 자료형 오류의 부재를 검증하는 것이 불가능하다는 것을 의미한다. 반면에, 정적 자료형 프로그래밍 언어는 자료형 오류를 정적으로 방지하는 자료형 시스템을 특징으로 한다. 본질적으로, 이것은 해당 언어의 구문(광범위한 의미에서)의 특징으로 이해되어야 한다. 프로그램을 자료형 검사하려면 소스 코드를 검사해야 한다; 이 작업은 프로그램의 가설적인 의미론에만 의존하지 않는다.
일반적인 소프트웨어 검증 측면에서, 이는 주어진 프로그램이 주어진 명세를 만족하는지 알고리즘적으로 확인할 수는 없지만, 프로그램이 정확함을 증명하는 추가 정보로 주석을 달거나, 검증을 가능하게 하는 특정 제한된 형태로 작성되도록 요구하고, 이런 방식으로 검증된 프로그램만 받아들일 수 있음을 의미한다. 자료형 안전성의 경우, 전자는 자료형 주석에 해당하고, 후자는 자료형 추론에 해당한다. 자료형 안전성을 넘어, 이 아이디어는 호어 논리와 같은 증명 주석을 통한 프로그램의 정확성 증명으로 이어진다.
라이스의 정리를 우회하는 또 다른 방법은 완전하지는 않지만 많은 버그를 잡는 방법을 찾는 것이다. 이것이 추상 해석 이론이다.
검증의 또 다른 방향은 모델 검사이며, 이는 튜링 완전 언어에는 적용할 수 없고 유한 상태 프로그램에만 적용할 수 있다.
라이스의 정리 정의
를 부분 계산 가능한 함수의 허용 가능한 번호 매기기라고 하고, 를 의 부분 집합이라고 하자. 다음을 가정한다:
그러면 는 판단 불가능하다.
더 간결한 진술은  색인 집합 측면에서 할 수 있다: 유일하게 결정 가능한 색인 집합은 와 이다.
라이스의 정리 예시
자연수 n을 받아 자연수 P(n)을 반환하는 프로그램 P가 주어졌을 때, 다음 질문들은 판단 불가능하다:
라이스의 정리 클레이니 재귀 정리에 의한 증명
가 자연수의 비자명하고 확장적이며 계산 가능한 집합이라고 모순적으로 가정해 보자. 자연수 와 자연수 가 존재한다. 일 때 이고 일 때 로 함수 를 정의한다. 클레이니 재귀 정리에 의해, 인 가 존재한다. 그러면, 만약 이면, 가 되어 이므로 의 확장성에 모순되며, 반대로, 만약 이면, 가 되어 이므로 다시 확장성에 모순된다.
라이스의 정리 정지 문제로부터의 환원을 통한 증명
구체적으로, 프로그램 p를 검사하여 p가 정수 d를 받아 d2을 반환하는 제곱 함수의 구현인지 정확하게 판별하는 알고리즘이 있다고 가정해 보자. 이 증명은 프로그램 동작의 다른 비자명한 속성(즉, 의미론적이고 비자명한 속성)을 결정하는 알고리즘이 있는 경우에도 마찬가지로 잘 작동하며, 아래에 일반적인 형태로 제시된다.
주장은 제곱 프로그램을 식별하는 알고리즘을 정지하는 함수를 식별하는 알고리즘으로 변환할 수 있다는 것이다. 우리는 입력 a와 i를 받아 프로그램 a가 입력 i에서 정지하는지 여부를 결정하는 알고리즘을 설명할 것이다.
라이스의 정리 정지 문제로부터의 환원을 통한 증명
이를 결정하는 알고리즘은 개념적으로 간단하다: 인자 n을 받는 새 프로그램 t의 (설명)을 구성하는데, 이는 (1) 먼저 입력 i에서 프로그램 a를 실행하고 (a와 i는 모두 t의 정의에 하드코딩된다), (2) 그 다음 n의 제곱을 반환한다. 만약 a(i)가 영원히 실행된다면, t는 n에 관계없이 단계 (2)에 도달하지 못한다. 그러면 분명히, t는 단계 (1)이 종료하는 경우에만 제곱을 계산하는 함수이다. 제곱을 계산하는 프로그램을 정확하게 식별할 수 있다고 가정했으므로, a와 i에 의존하는 t가 그런 프로그램인지 결정할 수 있다; 따라서 우리는 프로그램 a가 입력 i에서 정지하는지 결정하는 프로그램을 얻었다. 우리의 정지 결정 알고리즘은 t를 실행하지 않고, 단지 그 설명을 제곱 식별 프로그램에 전달하며, 이 프로그램은 가정에 따라 항상 종료한다; t의 설명을 구성하는 것 또한 항상 종료하는 방식으로 수행될 수 있으므로, 정지 결정도 정지하지 않을 수 없다.
라이스의 정리 정지 문제로부터의 환원을 통한 증명
이 방법은 제곱을 계산하는 함수를 인식할 수 있는지 여부에 특별히 의존하지 않는다; 우리가 인식하려는 것을 어떤 프로그램이 할 수 있는 한, 우리는 a에 대한 호출을 추가하여 t를 얻을 수 있다. 우리는 제곱근을 계산하는 프로그램을 인식하는 방법, 또는 월급을 계산하는 프로그램, 또는 입력 "Abraxas"가 주어졌을 때 정지하는 프로그램을 인식하는 방법을 가질 수 있었다; 각 경우에, 우리는 정지 문제를 유사하게 해결할 수 있었을 것이다.
정식 증명을 위해, 알고리즘은 문자열에 대한 부분 함수를 정의하고 스스로 문자열로 표현된다고 가정한다. 문자열 a로 표현되는 알고리즘에 의해 계산되는 부분 함수는 Fa로 표기된다. 이 증명은 귀류법으로 진행된다: 우리는 알고리즘에 의해 결정되는 비자명한 속성이 있다고 가정하고, 그 다음 우리가 정지 문제를 결정할 수 있다는 것을 보여주는데, 이는 불가능하므로 모순이다.
이제 P(a)가 Fa의 비자명한 속성을 결정하는 알고리즘이라고 가정해 보자. 일반성을 잃지 않고 P(no-halt) = "no"라고 가정할 수 있으며, no-halt는 결코 정지하지 않는 알고리즘의 표현이다. 만약 이것이 사실이 아니라면, 속성 P의 부정을 계산하는 알고리즘 P에 대해 이것이 성립한다. 이제 P가 비자명한 속성을 결정하므로, 알고리즘 Fb를 나타내는 문자열 b가 존재하고 P(b) = "yes"이다. 그러면 H(a, i) 알고리즘을 다음과 같이 정의할 수 있다:
1. 알고리즘 T(j)를 나타내는 문자열 t를 구성한다.
T는 먼저 Fa(i)의 계산을 시뮬레이션하고,
그 다음 T는 Fb(j)의 계산을 시뮬레이션하고 그 결과를 반환한다.
2. P(t)를 반환한다.
이제 H가 정지 문제를 결정한다는 것을 보여줄 수 있다:
정지 문제는 판단 불가능하다고 알려져 있으므로, 이것은 모순이며, a로 표현되는 함수에 대한 비자명한 속성을 결정하는 알고리즘 P(a)가 존재한다는 가정은 거짓이어야 한다.
라이스의 정리 각주
Rice, H. G. (1953), “Classes of recursively enumerable sets and their decision problems”, 《Transactions of the American Mathematical Society》 74 (2): 358–366, doi:10.1090/s0002-9947-1953-0053041-6, JSTOR 1990888
왕 타일
왕 타일(Wang tile) 또는 왕 도미노(Wang dominoes)는 수학자, 논리학자, 철학자 왕 하오가 1961년에 처음 제안한 형식 체계의 한 종류이다. 각 면에 색이 있는 정사각형 타일로 시각적으로 모델링된다. 이러한 타일 세트가 선택되고, 타일 복사본은 회전하거나 반사하지 않고 일치하는 색상으로 나란히 배열된다.
왕 타일 세트에 대한 기본적인 질문은 평면을 타일링할 수 있는지 여부, 즉 전체 무한 평면을 이런 방식으로 채울 수 있는지 여부이다. 다음 질문은 이것이 주기적인 패턴으로 수행될 수 있는지 여부이다.
왕 타일 도미노 문제
1961년, 왕은 유한한 왕 타일 세트가 평면을 타일링할 수 있다면, 주기적 타일링도 존재할 것이라고 추측했다. 주기적 타일링은 수학적으로 2차원 격자의 벡터에 의한 변환에 불변인 타일링이다. 이는 전체 패턴이 더 작은 패턴의 반복인 벽지 패턴의 주기적 타일링과 유사할 수 있다. 그는 또한 이 추측이 주어진 유한한 왕 타일 세트가 평면을 타일링할 수 있는지 여부를 결정하는 알고리즘의 존재를 의미할 것이라고 관찰했다. 인접한 타일이 서로 일치하도록 제한하는 아이디어는 도미노 게임에서 발생하므로 왕 타일은 왕 도미노라고도 알려져 있다. 타일 세트가 평면을 타일링할 수 있는지 여부를 결정하는 알고리즘 문제는 도미노 문제로 알려지게 되었다.
왕의 학생인 로버트 버거에 따르면,
도미노 문제는 모든 도미노 세트의 클래스를 다룬다. 각 도미노 세트에 대해 풀 수 있는지 여부를 결정하는 것으로 구성된다. 우리는 임의의 도미노 세트의 사양이 주어졌을 때, 그 세트가 풀 수 있는지 여부를 결정하는 알고리즘이 존재하거나 존재하지 않는지에 따라 도미노 문제가 결정 가능하거나 결정 불가능하다고 말한다.
왕 타일 도미노 문제
즉, 도미노 문제는 주어진 모든 도미노 세트에 대해 문제를 올바르게 해결하는 효과적인 절차가 있는지 묻는 것이다.
1966년, 버거는 도미노 문제를 부정적으로 해결했다. 그는 튜링 기계가 멈추지 않는 경우에만 평면을 타일링하는 왕 타일 세트로 모든 튜링 기계를 번역하는 방법을 보여줌으로써 문제에 대한 알고리즘이 존재할 수 없음을 증명했다. 정지 문제 (튜링 기계가 결국 멈추는지 여부를 테스트하는 문제)의 결정 불가능성은 왕의 타일링 문제의 결정 불가능성을 의미한다.
왕 타일 비주기적 타일 세트
버거의 결정 불가능성 결과와 왕의 관찰을 결합하면 평면을 타일링하지만 비주기적으로만 타일링하는 유한한 왕 타일 세트가 존재해야 한다는 것을 보여준다. 이것은 펜로즈 테셀레이션이나 준결정의 원자 배열과 유사하다. 버거의 원래 세트에는 20,426개의 타일이 포함되어 있었지만, 그는 그의 세트의 하위 세트를 포함하여 더 작은 세트가 작동할 것이라고 추측했으며, 그의 미출판 박사 학위 논문에서 타일 수를 104개로 줄였다. 이후 몇 년 동안 점점 더 작은 세트가 발견되었다. 예를 들어, 13개의 비주기적 타일 세트는 1996년 카렐 쿨릭 2세에 의해 발표되었다.
가장 작은 비주기적 타일 세트는 2015년 에마뉘엘 장델과 미카엘 라오에 의해 11개의 타일과 4개의 색상으로 발견되었다. 그들은 10개의 타일이나 3개의 색상으로는 비주기성을 강제하기에 불충분하다는 것을 증명하기 위해 철저한 컴퓨터 탐색을 사용했다. 제목 이미지에 표시된 이 세트는 파일: Wang 11 tiles.svg에서 더 자세히 볼 수 있다.
왕 타일 일반화
왕 타일은 다양한 방식으로 일반화될 수 있으며, 이 모든 것은 위에서 언급한 의미에서 결정 불가능하다. 예를 들어, 왕 큐브는 색상이 있는 면을 가진 동일한 크기의 큐브이며, 면 색상은 어떤 다각형 테셀레이션에서도 일치시킬 수 있다.
쿨릭과 카리는 왕 큐브의 비주기적 세트를 시연했다. 윈프리 외는 왕 타일 역할을 할 수 있는 DNA (디옥시리보핵산)로 만들어진 분자 "타일"을 만드는 가능성을 시연했다. 미탈 외는 이러한 타일이 펩타이드 핵산 (PNA), 즉 안정적인 인공 DNA 모방체로도 구성될 수 있음을 보여주었다.
왕 타일 응용
왕 타일은 절차적 합성으로 절차적 텍스처, 높이 필드 및 기타 크고 비반복적인 2차원 데이터 세트를 생성하는 데 사용되었다. 미리 계산되거나 수작업으로 만든 작은 소스 타일 세트는 너무 명백한 반복과 주기성 없이 매우 저렴하게 조립될 수 있다.
이 경우 전통적인 비주기적 테셀레이션은 매우 규칙적인 구조를 보여줄 것이다. 타일링 가능성이 쉽게 보장되고 각 타일을 유사 무작위로 선택할 수 있으므로 주어진 두 면 색상에 대해 최소한 두 가지 타일 선택을 보장하는 훨씬 덜 제약적인 세트가 일반적이다.
왕 타일은 세포 자동자 이론의 결정 문제 결정 가능성 증명에도 사용되었다.
왕 타일 대중 문화에서
그레그 이건의 단편 소설 "왕의 카펫"은 나중에 소설 디아스포라로 확장되었는데, 복합 분자 패턴으로 구현된 왕 타일로 구현된 거주 생물과 지능 있는 존재가 있는 우주를 가정한다.
에르브랑의 정리
에르브랑의 정리(Herbrand's theorem)는 자크 에르브랑이 1930년에 발표한 수리논리학의 근본적인 결과이다. 본질적으로 1차 논리를 명제 논리로 특정 유형의 환원을 가능하게 한다. 에르브랑 정리는 대부분의 자동 정리 증명기의 논리적 기초이다. 에르브랑은 원래 1차 논리의 임의의 공식에 대해 자신의 정리를 증명했지만 여기 제시된 더 간단한 버전은 프레넥스 형식으로 된 존재 기호만을 포함하는 공식으로 제한되어 더 인기를 얻었다.
에르브랑의 정리 서술
다음과 같은 1차 논리 공식이 있다고 하자.
여기서 는 양화사(quantifier)가 없는 식이지만, 추가적인 자유 변수를 포함할 수 있다.
에르브랑 정리의 이 버전은 위 공식이 타당한 것은
다음과 같은 유한한 항열 가 존재하는 경우에만 해당된다는 것을 진술한다.
이 항열은 언어의 확장 안에 있을 수 있으며,
및 ,
다음과 같은 조건이 충족된다:
이 타당하다. 만약 타당하다면, 이를 다음의 에르브랑 분리합이라고 부른다.
비공식적으로: 존재 양화사만을 포함하는 프레넥스 형식의 공식 가 1차 논리에서 증명 가능(타당)한 것은 의 양화사 없는 하위 공식의 치환 인스턴스로 구성된 분리합이 항진식 (명제적으로 도출 가능)인 경우에만 해당된다.
존재 양화사만을 포함하는 프레넥스 형식의 공식으로 제한하는 것은 정리의 일반성을 제한하지 않는다. 공식은 프레넥스 형식으로 변환될 수 있고, 보편 양화사는 에르브랑화를 통해 제거될 수 있기 때문이다. 구조적 에르브랑화를 수행하면 프레넥스 형식으로의 변환을 피할 수 있다. 에르브랑 분리합에 허용되는 변수 의존성에 추가적인 제한을 가함으로써 에르브랑화를 피할 수도 있다.
에르브랑의 정리 증명 스케치
정리의 비자명한 방향에 대한 증명은 다음 단계에 따라 구성될 수 있다:
그러나 에르브랑이 증명을 하던 당시에는 시퀀트 계산과 자름-제거가 알려지지 않았기 때문에, 에르브랑은 더 복잡한 방식으로 자신의 정리를 증명해야 했다.
아벨-루피니 정리
수학에서 아벨-루피니 정리(Abel–Ruffini theorem) 또는 아벨의 불가능성 정리(Abel's impossibility theorem)는 임의의 계수를 갖는 5차 이상의 일반적인 다항 방정식에는 근호를 이용한 해가 존재하지 않는다는 것을 말한다. 여기서 일반적이라는 것은 방정식의 계수가 부정원으로 간주되고 조작된다는 것을 의미한다.
이 정리는 1799년에 불완전한 증명을 제시한 파올로 루피니(1813년에 보완되고 완성되었으며 오귀스탱 루이 코시에게 인정됨)과 1824년에 증명을 제시한 닐스 헨리크 아벨의 이름을 따서 명명되었다.
이 용어는 5차 이상의 방정식 중 근호를 이용해 풀 수 없는 방정식이 있다는 약간 더 강한 결과도 지칭할 수 있다. 이는 아벨의 정리 진술에서 도출되는 것은 아니지만, 그의 증명의 귀결이다. 왜냐하면 그의 증명은 방정식 계수의 일부 다항식이 영 다항식이 아니라는 사실에 기반하기 때문이다. 이 개선된 진술은 갈루아 이론 § 해결 불가능한 5차 방정식의 예시에서 직접적으로 이어진다. 갈루아 이론은 또한
아벨-루피니 정리
이 근호를 이용하여 풀 수 없는 가장 간단한 방정식이며, 5차 이상의 거의 모든 다항식이 근호를 이용하여 풀 수 없음을 의미한다.
5차 이상 방정식의 불가능성은 저차 방정식의 경우와 대조된다. 2차, 3차, 4차 방정식에는 각각 이차 근의 공식, 삼차 근의 공식, 사차 근의 공식이 있다.
아벨-루피니 정리 배경
2차 다항 방정식은 이차 근의 공식으로 풀 수 있으며, 이는 고대사 이래로 알려져 있었다. 마찬가지로 3차 방정식의 삼차 근의 공식과 4차 방정식의 사차 근의 공식은 16세기에 발견되었다. 그 당시 근본적인 문제는 고차 방정식도 비슷한 방법으로 풀 수 있는지 여부였다.
양의 차수를 가진 모든 다항 방정식에 실수가 아닌 해가 있을 수 있다는 사실은 17세기에 주장되었지만, 19세기 초에 이르러서야 완전히 증명되었다. 이것이 대수학의 기본 정리인데, 이는 해를 계산하는 도구를 제공하지는 않지만, 모든 해를 원하는 정확도로 근사하는 몇 가지 방법이 알려져 있다.
16세기부터 19세기 초까지 대수학의 주요 문제는 5차 이상의 다항 방정식 해에 대한 공식을 찾는 것이었다. 그래서 "대수학의 기본 정리"라는 이름이 붙었다. 이는 근호를 이용한 해를 의미했으며, 즉 방정식의 계수와 덧셈, 뺄셈, 곱셈, 나눗셈, 그리고 n제곱근 연산만을 포함하는 수식을 의미했다.
아벨-루피니 정리 배경
아벨-루피니 정리는 이것이 불가능하다는 것을 증명한다. 그러나 이 불가능성은 어떤 특정 차수의 방정식이 근호로 풀 수 없다는 것을 의미하지는 않는다. 오히려 근호로 풀 수 있는 모든 차수의 방정식이 존재한다. 이는 모든 n에 대한 방정식 과 원분 다항식으로 정의된 방정식의 경우이며, 이들 모두의 해는 근호로 표현될 수 있다.
아벨의 정리 증명은 근호로 풀 수 없는 특정 방정식이 있다는 주장을 명시적으로 포함하지 않는다. 이러한 주장은 아벨의 정리 진술의 결과가 아니다. 왜냐하면 그 진술은 "모든 특정 오차 방정식이 각 방정식에 대한 특별한 공식으로 풀 수 있다"는 가능성을 배제하지 않기 때문이다. 그러나 근호로 풀 수 없는 특정 방정식의 존재는 아벨의 증명의 결과인 것으로 보인다. 왜냐하면 증명은 계수의 일부 다항식이 영 다항식이 아니라는 사실을 사용하며, 유한한 수의 다항식이 주어지면 변수 중 어느 것도 영의 값을 취하지 않는 값이 존재하기 때문이다.
아벨-루피니 정리 배경
아벨이 증명을 발표한 직후, 에바리스트 갈루아는 현재 갈루아 이론이라고 불리는 이론을 도입하여 주어진 방정식이 근호로 풀 수 있는지 여부를 결정할 수 있게 했다. 이는 전자 계산기의 등장 이전에는 순전히 이론적이었다. 현대 컴퓨터와 프로그램을 사용하면 100차 이상의 다항식에 대해 다항식이 근호로 풀 수 있는지 여부를 결정할 수 있다. 풀 수 있는 다항식의 근호 해를 계산하려면 엄청난 계산이 필요하다. 5차의 경우에도 해의 표현은 너무 커서 실제적인 관심이 없다.
아벨-루피니 정리 증명
아벨-루피니 정리의 증명은 갈루아 이론보다 앞선다. 그러나 갈루아 이론은 이 주제를 더 잘 이해하게 해주며, 현대적 증명은 일반적으로 갈루아 이론에 기반한다. 반면 아벨-루피니 정리의 원래 증명은 역사적인 목적으로 여전히 제시된다.
갈루아 이론에 기반한 증명은 네 가지 주요 단계로 구성된다. 체론의 관점에서 가해 방정식의 특징화; 주어진 체의 부분체와 그 갈루아 군의 부분군 사이의 갈루아 대응을 사용하여 이 특징화를 가해군의 관점에서 표현하는 것; 대칭군이 차수가 5 이상이면 가해가 아니라는 증명; 그리고 대칭 갈루아 군을 갖는 다항식의 존재.
다항 방정식의 대수적 해는 네 가지 기본 사칙연산 (덧셈, 뺄셈, 곱셈, 나눗셈)과 거듭제곱근을 포함하는 수식이다. 이러한 수식은 풀고자 하는 방정식의 계수에서 시작하여 차례로 숫자를 계산하는 과정으로 볼 수 있다.
계산의 각 단계에서 지금까지 계산된 모든 숫자를 포함하는 가장 작은 체를 고려할 수 있다. 이 체는 n차 제곱근 계산을 포함하는 단계에서만 변경된다.
따라서 대수적 해는 다음과 같은 수열을 생성한다.
아벨-루피니 정리 증명
의 체와  원소로, 에 대해 이며, 어떤 정수 에 대해 이다. 초기 다항 방정식의 대수적 해는 가 해를 포함하는 그러한 체의 수열이 존재할 때 그리고 그 때에만 존재한다.
이론의 기본인 정규 확대를 얻으려면 체의 수열을 다음과 같이 세분화해야 한다. 만약 이 모든 차 단위근을 포함하지 않는다면, 원시 단위근으로 을 확장하는 체 를 도입하고, 를 로 재정의한다.
따라서 근호를 이용한 해에서 시작하면 마지막에 해를 포함하고, 각각이 선행하는 체의 정규 확대이며 갈루아 군이 순환군인 체의 증가 수열을 얻게 된다.
반대로, 그러한 체의 수열이 있다면 방정식은 근호를 이용하여 풀 수 있다. 이를 증명하려면, 순환 갈루아 군을 갖는 정규 확대가 연속적인 근호 확대로부터 구성될 수 있음을 증명하는 것으로 충분하다.
갈루아 대응은 정규 체 확장 의 부분확대체와 그 확장의 갈루아 군의 부분군 사이에 일대일 대응을 설정한다. 이 대응은 와 같은 체 K를 K를 고정하는 F의 자기동형사상의 갈루아 군 에 매핑하고, 반대로 의 부분군 H를 H에 의해 고정되는 F의 원소들의 체에 매핑한다.
아벨-루피니 정리 증명
앞선 절은 방정식이 근호를 이용하여 풀 수 있는 경우에만 분해체(모든 근을 포함하는 가장 작은 체)의 갈루아 군이 가해군이며, 즉 각 부분이 선행하는 부분군의 정규 부분군이고, 몫군이 순환군인 부분군의 수열을 포함한다는 것을 보여준다. (가해군은 일반적으로 순환 몫군 대신 아벨 몫군으로 정의되지만, 유한 아벨 군의 기본 정리는 두 정의가 동등함을 보여준다.)
따라서 아벨-루피니 정리를 증명하기 위해, 대칭군 (군론) 가 가해가 아니라는 것과 대칭 갈루아 군을 갖는 다항식이 존재한다는 것을 보여주는 것이 남았다.
n ≥ 5에 대해, 차수 n의 대칭군 (군론) 은 교대군 만을 비자명 정규 부분군으로 갖는다 (Symmetric group § Normal subgroups 참조). n ≥ 5에 대해, 교대군 은 단순군 (즉, 비자명 정규 부분군을 갖지 않음)이며 아벨 군이 아니다. 이는 n ≥ 5에 대해 과  모두 가해군이 아님을 의미한다. 따라서 아벨-루피니 정리는 대칭 갈루아 군을 갖는 다항식의 존재로부터 도출된다; 이것은 다음 절에서 보여줄 것이다.
아벨-루피니 정리 증명
다른 한편으로, n ≤ 4에 대해서는 대칭군과 그 모든 부분군이 가해군이다. 이는 갈루아 이론의 주요 결과가 다항 방정식이 근호를 이용한 해를 갖는 경우에만 그 갈루아 군이 가해군이라는 것이기 때문에, 이차, 삼차, 사차 공식의 존재를 설명한다 (용어 "가해군"은 이 정리에서 유래한다).
차수 n의 일반 또는 일반적인 다항 방정식은 다음과 같은 방정식이다.
여기서 은 서로 다른 부정원이다. 이것은 유리수 계수를 갖는 에 대한 유리 함수의 체  위에서 정의된 방정식이다. 원래의 아벨-루피니 정리는 n ≥ 5에 대해 이 방정식이 근호로 풀 수 없다고 주장한다. 앞선 절들을 고려할 때, 이는 이 방정식의 F 위의 갈루아 군이 대칭군 (군론) 이라는 사실에서 비롯된다 (이 갈루아 군은 방정식의 분해체의 체 자기동형사상의 군으로, 분해체는 방정식의 모든 근을 포함하는 가장 작은 체이다).
갈루아 군이 임을 증명하기 위해서는 근에서 시작하는 것이 더 간단하다. 을 근이 될 새로운 부정원으로 두고, 다항식
아벨-루피니 정리 증명
를 고려한다. 를 의 유리 함수의 체라고 하고, 를 의 계수들로 생성되는 부분체라고 하자. 의 순열은 H의 자기동형사상을 유도한다. 비에트 정리는 K의 모든 원소가 의 대칭 함수이며, 따라서 이 모든 자기동형사상에 의해 고정된다는 것을 의미한다. 따라서 갈루아 군 은 대칭군 이다.
대칭 다항식의 기본 정리는 가 대수적으로 독립임을 의미하며, 따라서 각 를 해당하는 로 보내는 사상은 F에서 K로의 체 동형사상이다. 이는 을 일반적인 방정식으로 간주할 수 있음을 의미한다. 이것으로 일반 방정식의 갈루아 군이 대칭군임을 증명하고, 따라서 n ≥ 5에 대해 일반 다항 방정식이 근호로 풀 수 없다고 주장하는 원래의 아벨-루피니 정리를 증명한다.
방정식 은 아래에 설명된 대로 근호로 풀 수 없다.
q를 이라고 하자.
G를 그 갈루아 군이라고 하자. 이것은 q의 복소수 근 집합에 충실하게 작용한다.
근에 번호를 매기면 G를 대칭군 의 부분군과 동일시할 수 있다.
가 에서 로 인수분해되므로, 군 G는 길이가 2와 3인 서로소 순환의 곱인 순열 를 포함한다 (일반적으로 단항 정수 다항식이 소수를 법으로 했을 때 서로 다른 단항 기약 다항식의 곱으로 축소될 때, 인수의 차수는 갈루아 군에 속하는 어떤 순열에서 서로소 순환의 길이를 제공한다). 그러면 G는 또한 을 포함하는데, 이것은 전치이다. 이 에서 기약이므로, 같은 원리는 G가 5-순환을 포함함을 보여준다. 5는 소수이므로, 의 어떤 전치와 5-순환은 전체 군을 생성한다. 따라서 이다. 군 는 가해군이 아니므로 방정식 은 근호로 풀 수 없다.
아벨-루피니 정리 케일리의 해소식
특정 5차 방정식이 근호로 풀 수 있는지 여부를 테스트하는 것은 케일리의 해소식을 사용하여 수행할 수 있다. 이것은 6차 다항식으로, 계수는 일반 5차 방정식의 계수의 다항식이다. 특정 기약 5차 방정식은 근호로 풀 수 있는 경우에만, 그 계수를 케일리의 해소식에 대입했을 때, 결과로 나오는 6차 다항식이 유리수 근을 가지며, 이는 유리근 정리를 사용하여 쉽게 테스트할 수 있다.
아벨-루피니 정리 역사
1770년경, 조제프 루이 라그랑주는 라그랑주 분해식의 형태로 순열 군 이론과 관련하여 그 시점까지 방정식 해결에 사용되었던 여러 가지 다른 방법들을 통합하는 기초 작업을 시작했다. 라그랑주의 이 혁신적인 작업은 갈루아 이론의 전신이었으며, 5차 이상의 방정식에 대한 해법을 개발하는 데 실패한 것은 그러한 해법이 불가능할 수 있음을 암시했지만, 결정적인 증거를 제공하지는 않았다. 5차 방정식의 근호를 이용한 해결 문제가 불가능할 수 있다고 처음 추측한 사람은 카를 프리드리히 가우스였다. 그는 1798년 자신의 저서 정수론 연구 (1801년에 출판될 예정이었음) 359절에서 "이 문제는 현대 분석 방법을 거부한다기보다는 불가능한 것을 제안하는 것에 가깝다는 의심이 거의 없다"고 썼다. 다음 해, 그의 학위논문에서 그는 "많은 기하학자들이 일반 방정식을 대수적으로 해결할 희망을 거의 남기지 않은 후, 이 해결은 불가능하고 모순된다는 것이 점점 더 확실해 보인다"고 썼다. 그리고 그는 "5차에 대한 불가능성을 모든 엄격함으로 증명하는 것이 그렇게 어렵지 않을 것이다. 나는 이에 대한 나의 연구를 다른 곳에서 더 자세히 설명할 것이다"라고 덧붙였다. 실제로 가우스는 이 주제에 대해 더 이상 아무것도 발표하지 않았다.
아벨-루피니 정리 역사
이 정리는 1799년 파올로 루피니에 의해 처음으로 거의 증명되었다. 그는 자신의 증명을 여러 수학자들에게 보내 인정을 받으려 했으며, 그 중에는 라그랑주(답변하지 않음)와 오귀스탱 루이 코시가 있었다. 코시는 그에게 편지를 보내 "방정식의 일반해에 대한 당신의 논문은 내가 항상 수학자들에게 기억되어야 한다고 믿어왔던 작품이며, 내 생각으로는 4차보다 높은 차수의 일반 방정식의 대수적 불가능성을 결정적으로 증명한다"고 말했다. 그러나 일반적으로 루피니의 증명은 설득력이 있다고 여겨지지 않았다. 아벨은 다음과 같이 썼다: "나보다 먼저 일반 방정식의 대수적 해의 불가능성을 증명하려 한 첫 번째이자, 내가 틀리지 않았다면 유일한 사람은 수학자 루피니다. 그러나 그의 논문은 너무 복잡해서 그의 주장의 유효성을 판단하기 매우 어렵다. 내 생각에는 그의 주장이 완전히 만족스럽지 않다."
아벨-루피니 정리 역사
증명은 또한 나중에 밝혀졌듯이 불완전했다. 루피니는 그가 다루는 모든 근호가 체 연산만 사용하여 다항식의 근에서 표현될 수 있다고 가정했다. 현대 용어로 말하면, 그는 근호가 다항식의 분해체에 속한다고 가정했다. 이것이 왜 실제로 추가적인 가정인지 이해하려면, 예를 들어 다항식 을 고려해보라. 카르다노의 공식에 따르면, 그 근 중 하나(실제로는 모든 근)는 의 세제곱근과 의 세제곱근의 합으로 표현될 수 있다. 다른 한편으로, , , , 이므로 의 근 , , 는 모두 실수이고 따라서 체 는 의 부분체이다. 그러나 그러면 숫자 는 에 속할 수 없다. 코시는 루피니의 가정을 알아차리지 못했거나 사소하다고 느꼈지만, 대부분의 역사가들은 아벨이 일반 다항식의 경우에 가정이 성립한다고 주장하는 자연적 무리수 이론에 대한 정리를 증명하기 전까지는 증명이 완전하지 않았다고 믿는다.
아벨-루피니 정리는 따라서 일반적으로 아벨에게 귀속되며, 그는 1824년에 단 6페이지로 압축된 증명을 발표했다. (아벨은 종이와 비용을 절약하기 위해 매우 간결한 스타일을 채택했다. 증명은 자비로 인쇄되었다.) 더 정교한 버전의 증명은 1826년에 발표되었다.
아벨-루피니 정리 역사
일반 5차(및 고차) 방정식이 근호로 풀 수 없음을 증명하는 것으로 문제가 완전히 해결된 것은 아니었다. 왜냐하면 아벨-루피니 정리는 정확히 어떤 5차(및 고차) 방정식이 근호로 풀 수 없는지를 말하는 필요충분조건을 제공하지 않기 때문이다. 아벨은 1829년에 사망했을 때 완전한 특징화를 연구하고 있었다.
아벨-루피니 정리 역사
네이선 제이컵슨에 따르면, "루피니와 아벨의 증명은 [...] 이 연구 분야의 가장 뛰어난 성과인 갈루아의 방정식 이론 발견으로 곧 대체되었다." 1830년, 갈루아(18세)는 자신의 근호를 이용한 가해성 이론에 대한 논문을 프랑스 과학 아카데미에 제출했지만, 결국 1831년에 너무 개략적이고 방정식의 계수 대신 근에 대한 조건을 제시한다는 이유로 거부되었다. 갈루아는 루피니와 아벨의 공헌을 알고 있었는데, 그는 "4차보다 큰 차수의 일반 방정식은 근호로 풀 수 없다는 것은 오늘날 흔한 진실이다... 이 진실은 기하학자들이 아벨과 루피니의 증명을 무시했음에도 불구하고 (소문으로) 흔해졌다..."라고 썼다. 갈루아는 1832년에 사망했고 그의 논문 Mémoire sur les conditions de resolubilité des équations par radicaux는 1846년 조제프 리우빌이 자신의 설명과 함께 출판할 때까지 미출판 상태로 남아 있었다. 이 출판 이전에 리우빌은 1843년 7월 4일에 한 연설에서 갈루아의 결과를 아카데미에 발표했다. 아벨 증명의 간략화는 피에르 방첼에 의해 1845년에 출판되었다. 방첼이 이를 출판했을 때 그는 이미 갈루아의 공헌을 알고 있었고, 아벨의 증명은 일반 다항식에 대해서만 유효하지만 갈루아의 접근 방식은 근호를 이용하여 계수에서 표현할 수 없는 구체적인 5차 다항식을 제공하는 데 사용될 수 있다고 언급했다.
1963년, 블라디미르 아르놀트는 아벨-루피니 정리의 위상학적 증명을 발견했으며, 이는 위상 갈루아 이론의 출발점이 되었다.