데데킨트 수

수학에서 데데킨드 수는 1897년에 그것을 정의한 리처드 데데킨드의 이름을 딴 정수의 순서가 빠르게 증가하는 것이다.데데킨드 수 M(n)은 n 변수의 단조 부울 함수 수를 카운트한다.동등하게, n-요소 집합의 하위 집합의 반동수, n-발생기가 있는 자유 분배 격자의 요소 수 또는 n-요소가 있는 추상적 단순화 복합체의 수를 계산한다.

M(n)의 정확한 무증상 추정치와 정확한 식을 합산으로 알고 있다.^[1]그러나 M(n)의 값을 계산하는 데데킨드의 문제는 여전히 어렵다. M(n)에 대한 폐쇄형 표현은 알려져 있지 않고, 정확한 M(n)의 값은 n ≤ 8에 대해서만 발견되었다.^[2]

정의들

부울 함수는 입력 n 부울 변수(즉, 거짓 또는 참일 수 있는 값 또는 0 또는 1일 수 있는 동등하게 이진수 값)를 취하여 또 다른 부울 변수를 출력하는 함수다.입력의 모든 조합에 대해 입력 중 하나를 거짓에서 참으로 전환하면 출력이 거짓에서 참으로 전환되고 참에서 거짓으로 전환되지 않을 수 있는 것은 단조롭다.데데킨드 숫자 M(n)은 n 변수에 대한 서로 다른 단조로운 부울 함수의 수입니다.^[3]

집합의 반제(일명 슈페너 계열이라고도 함)는 집합의 계열로, 다른 집합에는 어떤 것도 포함되어 있지 않다.V가 n 부울 변수 집합인 경우, V 하위 집합의 안티체인 A는 단조 부울 함수 f를 정의하는데, 여기서 f의 값은 f에 대한 참 입력의 일부 하위 집합이 A에 속하고 그렇지 않으면 거짓인 경우 주어진 입력 집합에 대해 참이다.반대로 모든 모노톤 부울 함수는 이러한 방식으로 함수 값을 참으로 강제할 수 있는 부울 변수의 최소 하위 집합에 대한 반차를 정의한다.따라서 디데킨드 숫자 M(n)은 n-요소 집합의 하위 집합에 대한 서로 다른 반동수의 수와 같다.^[4]

동일한 종류의 물체를 설명하는 세 번째 동등한 방법은 격자 이론을 사용한다.어떤 두 개의 단조로운 부울함수 f와 g로부터 우리는 각각 논리적 결합과 논리적 분리인 f ∧ g와 f ∨ g의 다른 두 개의 단조로운 부울함수를 찾을 수 있다.n 입력에 대한 모든 모노톤 부울 함수의 집단은 이 두 연산과 함께 분배 격자, 즉 N 변수의 부분 집합에서 부분 순서가 포함된 버크호프의 표현 정리에 의해 주어진 격자를 형성한다.이 건설은 발전기 n개로 무료 분배 격자를 생산한다.^[5]따라서 디데킨드 숫자는 자유분배 선반에서 요소의 수를 계산한다.^[6]

또한 디데킨드 숫자는 n개 요소에 대한 추상적 단순화 콤플렉스의 수, 가족 내 집합의 하위 집합도 가족에 속하는 속성을 가진 집합의 수(하나 이상)를 계산한다.어떤 반물질이라도 반물질 구성원의 하위 집합인 단순화 콤플렉스를 결정하고 반대로 반물질 형태의 최대 단순화를 결정한다.^[7]

예

n = 2의 경우, 2요소 집합 {x,y}의 6개의 단일 부울 함수와 하위 집합의 6개의 반점이 있다.

• f(x,y) = 입력 값을 무시하고 항상 false를 반환하는 false 함수는 빈 안티체인 ø에 해당한다.
• 논리 접속사 f(x,y) = x ∧ y는 단일 집합 {x,y}을(를) 포함하는 반체 {x,y} }에 해당한다.
• f(x,y) = x 함수는 두 번째 인수를 무시하고 첫 번째 인수를 반환하는 것으로 단일 집합 {x}을(를) 포함하는 반체인 {x}에 해당함수 f(x,y) = x
• f(x,y) = 첫 번째 인수를 무시하고 두 번째 인수를 반환하는 함수 y는 단일 집합 {y}을(를) 포함하는 반차인 {y} }에 해당한다.
• 논리적 분리 f(x,y) = x ∨ y는 {x} 및 {y} 두 세트를 포함하는 반체 {x}, {y}에 해당한다.
• f(x,y) = 입력 값을 무시하고 항상 true를 반환하는 함수 f(x,y) = true는 빈 집합만 포함하는 안티체인 {ø}에 해당한다.^{[citation needed]}

가치

디데킨드 숫자의 정확한 값은 0 ≤ n ≤ 8로 알려져 있다.

2, 3, 6, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788(OEIS의 후속 A000372).

이 숫자 중 처음 여섯은 Church(1940)에 의해 주어진다.M(6)은 워드(1946년), M(7)은 교회(1965년), 베르만&쾰러(1976년), M(8)은 위데만(1991년)이 계산했다.

n이 짝수라면 M(n)도 짝수여야 한다.^[8]다섯 번째 데데킨드 수 M(5) = 7581의 계산은 개럿 비르코프의 추측에 의하면 M(n)^[9]은 항상 (2n - 1)(2n - 2)로 나누어진다.

합계식

키슬레위츠(1988)는 반제점의 논리적 정의를 데데킨트 숫자에 대한 다음과 같은 산술 공식으로 다시 썼다.

${\displaystyle M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j}\오른쪽),}$

여기서 b $i{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$는 숫자 $k$의 i ${\displaystyle i$ th 비트로서 바닥 기능을 사용하여 기록할 수 있다.

${\displaystyle b_{i}^{k}=\왼쪽\lfrac {k}{2^{i}}\오른쪽\frac {k}{2^{i+1}}\오른쪽\loor .}$

그러나 이 공식은 합계의 항 수가 많기 때문에 large n에 대한 M(n) 값을 계산하는 데 도움이 되지 않는다.^{[citation needed]}

점증약학

디데킨드 숫자의 로그는 경계를 통해 정확하게 추정할 수 있다.

${\displaystyle {n \lfloor }\leq \log_{2}M(n)\leq {n \n \n \loor }\{+O\lefloor }\좌측(1+O\log n}{n}\오른쪽)을 선택하십시오.}$

여기서 왼쪽 불평등은 각 세트가 정확히 $\lfloor {\displaystyle }$ ${\displaystyle n}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor n/2\rfloor }$개의$$ 원소를 가지고 있는 반창고의 수를 세고, 오른쪽 불평등은 클리트만 & 마르코우스키(1975)에 의해 증명되었다.

코르슈노프(1981)는 훨씬 더 정확한 추정치를^[10] 제공했다.

${\displaystyle M(n)=(1+o(1)^{n \lfloor \lfloor }\exp a(n)}을(를) 선택하십시오.$

짝수 n, 그리고

${\displaystyle M(n)=(1+o(1))2^{n \lfloor 선택 n/2\rfloor +1}\exp(b)(n)+c(n))}$

홀수 n, 어디에

${\displaystyle a(n)={n \n 선택 n/2-1}(2^{-n/2}+n^{2}^{2^{-n-5}-n2^{-n-4}),}$

${\displaystyle b(n)={n \선택 (n-3)/2}(2^{-(n+3)/2}+n^{2}^{-n-6}-n2}^{-n-3}),}$

그리고

${\displaystyle c(n)={n \선택(n-1)/2}(2^{-(n+1)/2+n^{2}^{-2^{-n-4})}$

이러한 추정을 뒷받침하는 주요 아이디어는 대부분의 항적에서 모든 세트의 크기가 n/2에 매우 가깝다는 것이다.^[10]n = 2, 4, 6, 8 Korshunov의 공식은 각각 9.8%, 10.2%, 4.1%, -3.3%의 인수로 부정확한 추정치를 제공한다.^[11]

메모들

참조

• Berman, Joel; Köhler, Peter (1976), "Cardinalities of finite distributive lattices", Mitt. Math. Sem. Giessen, 121: 103–124, MR 0485609.
• Church, Randolph (1940), "Numerical analysis of certain free distributive structures", Duke Mathematical Journal, 6 (3): 732–734, doi:10.1215/s0012-7094-40-00655-x, MR 0002842.
• Church, Randolph (1965), "Enumeration by rank of the free distributive lattice with 7 generators", Notices of the American Mathematical Society, 11: 724. Widemann(1991년)이 인용한 바와 같다.
• Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler", Gesammelte Werke, vol. 2, pp. 103–148.
• Kahn, Jeff (2002), "Entropy, independent sets and antichains: a new approach to Dedekind's problem", Proceedings of the American Mathematical Society, 130 (2): 371–378, doi:10.1090/S0002-9939-01-06058-0, MR 1862115.
• Kisielewicz, Andrzej (1988), "A solution of Dedekind's problem on the number of isotone Boolean functions", Journal für die Reine und Angewandte Mathematik, 1988 (386): 139–144, doi:10.1515/crll.1988.386.139, MR 0936995, S2CID 115293297
• Kleitman, D.; Markowsky, G. (1975), "On Dedekind's problem: the number of isotone Boolean functions. II", Transactions of the American Mathematical Society, 213: 373–390, doi:10.2307/1998052, JSTOR 1998052, MR 0382107.
• Korshunov, A. D. (1981), "The number of monotone Boolean functions", Problemy Kibernet., 38: 5–108, MR 0640855.
• Ward, Morgan (1946), "Note on the order of free distributive lattices", Bulletin of the American Mathematical Society, 52: 423, doi:10.1090/S0002-9904-1946-08568-7.
• Wiedemann, Doug (1991), "A computation of the eighth Dedekind number", Order, 8 (1): 5–6, doi:10.1007/BF00385808, MR 1129608, S2CID 120878757.
• Yamamoto, Koichi (1953), "Note on the order of free distributive lattices", Science Reports of the Kanazawa University, 2 (1): 5–6, MR 0070608.
• Zaguia, Nejib (1993), "Isotone maps: enumeration and structure", in Sauer, N. W.; Woodrow, R. E.; Sands, B. (eds.), Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421–430, MR 1261220.