타르스키의 고교 대수학 문제

수학 논리학에서 타르스키의 고등학교 대수학 문제는 알프레드 타르스키가 제기한 문제였다.고등수학에서 가르치는 이러한 연산에 대한 11가지 공리를 사용하여 증명할 수 없는 양의 정수보다 덧셈, 곱셈, 강조를 포함하는 정체성이 있는지 묻는다.이 질문은 1980년에 알렉스 윌키에 의해 해결되었는데, 그는 그러한 증명할 수 없는 정체성이 존재한다는 것을 보여주었다.

문제성명

타르스키는 덧셈('+')과 곱셈('·'), 지수에 관한 다음과 같은 11개의 공리를 고등학교에서 가르치는 표준 공리로 생각했다.

1. x + y = y + x
2. (x + y) + z = x + (y + z)
3. x · 1 = x
4. x · y = y · x
5. (x · y) · z = x · (y · z)
6. x · (y + z) = x · y + x ·z
7. 1^x = 1
8. x¹ = x
9. x^{y + z} = x^y · x^z
10. (x · y)^z = x^z · y^z
11. (x^y)^z = x^{y · z}.

고등학교 정체성이라고도 불리는 이 열한 개의 공리는 바이카르트 폐쇄 범주나 지수 링의 공리와 관련이 있다.^[1][2]Tarski의 문제는 오직 덧셈, 곱셈, 강조만을 포함하는 정체성이 모든 양의 정수에 대해 사실이지만 공리 1-11만을 사용하여 증명될 수 없는 것인가?가 된다.

증명 가능한 ID의 예

공리에는 문제의 작전에 관한 모든 기본적인 사실들이 나열되어 있는 것 같기 때문에, 세 가지 작업만을 사용하여 진술할 수 있는, 그러나 공리로는 증명할 수 없는, 증명할 수 있는 확실한 진리가 있어야 한다는 것은 바로 명백하지 않다.그러나 겉보기에는 악의 없어 보이는 진술을 입증하려면 위의 11가지 공리만 사용하여 긴 증거를 요구할 수 있다.(x + 1) ²= x² + 2 · x + 1이라는 다음 증거를 고려하십시오.

${\displaystyle {\displaystyle}(x+1)^{2}&=(x+1)^{1+1}\&=(x+1)^{1}}\cdot (x+1)^{1}&{\text{9시까지.}}\\&=(x+1)\cdot(x+1)&&{\text{{text}{2회 적용 8.}}\\&=(x+1)\cdot x+(x+1)\cdot 1&{\text{{by 6.}}\\&=x\cdot(x+1)+(x+1)+(x+1)&{\text{by 4., 3.}}\\&=(x\cdot x+x\cdot 1)++(x\cdot 1+1)&#{\text{6., 3.}}\\&=x\cdot x+(x\cdot 1+x\cdot 1)+1&{\text{{text}{2의 두 가지 적용으로}}\\&=x^{1}\cdot x^{1}+x\cdot (1+1)+1&{\text{by 6. 2개의 적용 8.}}\\&=x^{1+1}+x\cdot 2+1&{\text{9시까지}}\\&=x^{2}+2\cdot x+1&{\text{by 4.}}}\end{정렬}}$

엄격히 우리가 받침대 없이 한 완전히 형식 증명)정체(x+1)2를 증명할 것(미국+2·))+1(또는(x+1)2)x2+(x+12·))과 x+)⋅()⋅ 1+)⋅ 1)+1{\displaystyle x\cdot x+(x\cdot 1+x\cdot 1)+1}이후로 받침대의 각 선에 여분의 집합이 이상 두 용어의 액수 쓰지 않아야 한다..

증명의 길이는 문제가 되지 않는다; (x + y)¹⁰⁰와 같은 것에 대한 위와 유사한 신분의 증명은 많은 선을 필요로 하지만, 위의 증명에 비하면 거의 관련이 없다.

문제의 역사

11개의 공리의 목록은 분명히 그 훨씬 전에 수학자들에 의해 알려져 있고 사용되었음에도 불구하고 리차드 데데킨드의 작품에서 명시적으로 쓰여져 있는 것을 발견할 수 있다.^[3]그러나 디데킨드는 이 공리들이 그 정수에 대해 우리가 알고 싶은 모든 것을 우리에게 말해주기에 어떤 식으로든 충분한지 묻고 있는 것 같았다.이 문제는 1960년대 알프레드 타르스키에 의해 논리와 모델 이론의 문제로서 확고한 지위에 놓이게 되었고,^[1][4] 1980년대에 이르러 타르스키의 고교 대수학 문제로 알려지게 되었다.

해결책

1980년에 알렉스 윌키는 문제의 모든 정체성이 위의 공리를 사용하여 증명될 수 있는 것은 아니라는 것을 증명했다.^[5]그런 정체성을 노골적으로 찾아내어 이렇게 한 것이다.양수를 양의 숫자에 매핑하는 다항식들에 해당하는 새로운 함수 기호를 도입함으로써 그는 이 정체성을 증명했고, 위의 11개의 공리와 함께 이러한 기능들이 그것을 증명하기에 충분하고 필요하다는 것을 보여주었다.문제의 정체는

${\displaystyle {\displaysty}&\좌측(1+x)^{y}+(1+x+x^{2})^{y}\우측)^{x}\cdot \left(1+x^{3})^{x}+(1+x^{2}+x^{4}^{x}^{x}\right)^{y}\={}&\좌((1+x)^{x}+(1+x+x^{2})^{x}\우)^{y}\cdot \left(1+x^{3})^{y}+(1+x^{2}+x^{4)}}^{y}\오른쪽)^{x}.\end{정렬}}}$

이 정체성은 보통 W(x, y)로 표시되며, 모든 양의 정수 x와 y에 대해 참이며, 2항 중 인수(1- x+ x 2) xy ${\$로 볼 수 있지만, 11개의 고등학교 공리를 사용하여 참임을 증명할 수는 없다.

직관적으로 고등학교 공리는 다항식 1- x+ x 2 ${\$ 다항식 1-x+x^{}을 논할 수 없기 때문에 정체성을 증명할 수 없다. 그 다항식과 하위항 - x${\displaystyle -x}$에 대한 추론에는 부정이나 뺄셈의 개념이 필요하며, 이것들은 고등학교 공리에 존재하지 않는다.이것이 부족하면, 공리를 이용하여 다항식을 조작하고 그것에 대한 진정한 속성을 증명하는 것은 불가능하다.윌키가 논문에서 얻은 결과는 보다 형식적인 언어로 고등학교 공리의 "유일한 격차"가 음의 계수를 가진 다항식을 조작할 수 없다는 것을 보여준다.

R. 구레비치는 1988년에 1, 덧셈, 곱셈, 지수를 갖는 양의 자연수에 대한 유효한 방정식에 대해 유한 공리가 없다는 것을 보여주었다.^[6][7]

일반화

윌키는 위의 11개의 공리를 사용하여 증명할 수 없는 양의 정수에 대한 진술이 있다는 것을 증명했고 그러한 진술이 증명되기 전에 어떤 추가 정보가 필요한지를 보여주었다.네반린나 이론을 사용하여, 만약 어떤 사람이 취하는 지수적인 종류의 것을 제한한다면 위의 11가지 공리는 모든 참된 진술을 입증하기에 충분하다는 것도 증명되었다.^[8]

열린 채로 남아 있는 윌키의 결과에서 비롯된 또 다른 문제는 W(x, y)가 사실이 아닌 위의 11개 공리가 어떤 대수인지 묻는 것이다.1985년에 59개의 원소를 가진 대수학에서 공리는 충족하지만 W(x, y)는 거짓인 것이 발견되었다.^[4]그 이후로 더 작은 알헤브라가 발견되었고, 이제 가장 작은 알헤브라는 11개 또는 12개의 원소를 가지고 있어야 한다는 것이 알려져 있다.^[9]

메모들

참조

• 스탠리 N. 버리스, 캐런 A. 예이츠, 고등학교 정체성의 이야기, 대수학 유니버설리스52 제2-3호, (2004), 페이지 325–342, MR2161657.