Finite set

수학(mathematics)에서, 유한 집합(finite set)은 원소(element)의 유한(finite) 숫자를 가지는 집합(set)입니다. 비공식적으로, 유한 집합은 원칙적으로 셀 수 있고 세는 것을 끝마칠 수 있는 집합입니다. 예를 들어,

\{2,4,6,8,10\}

은 5 원소를 가지는 유한 집합입니다. 유한 집합의 원소의 숫자는 자연수(natural number) (비-음의(non-negative) 정수(integer))이며 집합의 카디널리티(cardinality)라고 불립니다. 유한하지 않은 집합은 무한(infinite)이라고 불립니다. 예를 들어, 모든 양의 정수 집합은 무한합니다:

\{1,2,3,\ldots \}.

유한 집합은 조합론(combinatorics), 세는 것(counting)의 수학적 연구에 특히 중요합니다. 유한 집합과 관련된 많은 논증은, 큰 유한 집합에서 작은 유한 집합으로의 단사 함수(injective function)가 존재할 수 없음을 말하는, 비둘기집 원리(pigeonhole principle)에 의존합니다.

Definition and terminology

공식적으로, 집합 $S$ 는 일부 자연수 $n$ 에 대해 다음의 전단사(bijection)가 존재하면 유한이라고 불립니다:

f\colon S\rightarrow \{1,\ldots ,n\}

.

숫자 $n$ 은 집합의 카디널리티이며, | $S$ |로 표시됩니다. 빈 집합(empty set) {} 또는 Ø는 카디널리티 영을 갖는 유한으로 고려됩니다.^[1]^[2]^[3]^[4]

만약 집합이 유한이면, 그것의 원소는 수열(sequence)에서 – 많은 방법으로 – 쓸 수 있습니다:

x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n).

조합론(combinatorics)에서, $n$ 원소를 갖는 유한 집합은 때때로 $n$ -집합이라고 불리고 $k$ 원소를 갖는 부분집합은 $k$ -부분집합이라고 불립니다. 예를 들어, 집합 {5,6,7}은 3-집합 – 셋의 원소를 갖는 유한 집합 – 이고 {6,7}은 그것의 2-부분집합입니다.

(집합 이론, 이른바 폰 노이만 구성(von Neumann construction)에서 관습적인 자연수 자체의 정의에 익숙한 사람들은 동등한 것인 전단사(bijection) $f\colon S\rightarrow n$ 의 존재를 사용하는 것을 선호할 수 있습니다.)

Basic properties

유한 집합 S의 임의의 적절한 부분집합(subset)은 유한하고 S 자체보다 더 적은 원소를 가집니다. 결과적으로, 유한 집합 S와 S의 적절한 부분집합 사이에는 전단사(bijection)가 존재할 수 없습니다. 이 속성을 가진 임의의 집합은 데데킨트-유한(Dedekind-finite)이라고 불립니다. 집합 이론에 표준 ZFC 공리를 사용하여, 모든 각 데데킨트-유한 집합이 역시 유한이지만, 이 의미는 ZF (선택의 공리(axiom of choice)없이 체르멜로–프렝켈 공리(Zermelo–Fraenkel axioms)) 단독으로 입증될 수 없습니다. 셀-수-있는 선택의 공리(axiom of countable choice), 선택의 공리의 약한 버전은 이 동등성을 증명하기에 충분합니다.

같은 카디널리티의 두 유한 집합 사이의 임의의 전단사 함수는 역시 전사 함수(surjective function)입니다. 유사하게, 같은 카디널리티의 두 유한 집합 사이에 임의의 전사는 역시 단사입니다.

두 유한 집합의 합집합(union)은, 다음과 함께, 유한입니다:

|S\cup T|\leq |S|+|T|.

사실, 포함–제외 원리(inclusion–exclusion principle)에 의해:

|S\cup T|=|S|+|T|-|S\cap T|.

보다 일반적으로, 유한 집합의 임의의 유한 숫자의 합집합(union)은 유한입니다. 유한 집합의 데카르트 곱(Cartesian product)은 역시, 다음과 함께, 유한입니다:

|S\times T|=|S|\times |T|.

유사하게, 유한하게 많은 유한 집합의 데카르트 곱은 유한입니다. n 원소를 갖는 유한 집합은 2ⁿ 구별되는 부분집합을 가집니다. 즉, 유한 집합의 거듭제곱 집합(power set)은 카디널리티 2ⁿ을 갖는 유한입니다.

유한 집합의 임의의 부분집합은 유한입니다. 함수의 값의 집합은 유한 집합의 원소에 적용될 때 유한입니다.

모든 유한 집합은 셀-수-있는(countable) 것이지만, 모든 셀-수-있는 집합이 유한인 것은 아닙니다. (일부 저자는, 어쨌든, "셀-수-있는"을 "셀-수-있게 무한"을 의미하는 것으로 사용하므로, 유한 집합을 셀-수-있는 것으로 고려하지 않습니다.)

유한 집합에 걸쳐 자유 반-격자(free semilattice)는 비-빈 부분집합의 집합이며, 여기서 접합 연산(join operation)은 집합 합집합에 의해 제공됩니다.

Necessary and sufficient conditions for finiteness

선택의 공리 (ZF)없이 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)에서, 다음 조건은 모두 동등한 것입니다:^{[citation needed]}

S는 유한 집합입니다. 즉, S는 어떤 특정 자연수보다 작은 그것들의 자연수의 집합과 일-대-일 대응으로 배치될 수 있습니다.
(카지미에시 쿠라토프스키(Kazimierz Kuratowski)) S는 빈 집합으로 시작하고 한 번에 하나의 새로운 원소를 더하는 수학적 귀납법으로 증명될 수 있는 모든 속성을 가지고 있습니다. (쿠라토프스키 유한성의 집합-이론적 공식에 대해 아래를 참조하십시오.)
(폴 스택클(Paul Stäckel)) S는 앞으로 및 뒤로 양쪽으로 바른-순서(well-order)된 전체 순서화로 주어질 수 있습니다. 즉, S의 모든 각 비-빈 부분집합은 부분집합에서 최소 원소와 최대 원소 둘 다를 가집니다.
P(P(S))에서 자체 안으로의 모든 각 일-대-일 함수는 위로의(onto)입니다. 즉, S의 거듭제곱집합의 거듭제곱집합(powerset)은 데데킨트-유한입니다 (아래를 참조하십시오).^[5]
P(P(S))에서 자체 위로의 모든 각 전사 집합은 일-대-일입니다.
(알프레트 타르스키(Alfred Tarski)) S의 부분집합의 모든 각 비-빈 가족은 포함에 관한 최소 원소(minimal element)를 가집니다.^[6] (동등하게, S의 부분집합의 모든 각 비-빈 가족은 포함에 관해 최대 원소(maximal element)를 가집니다.)
S는 바른-정렬된 것일 수 있고 그것 위에 둘의 바른-순서화는 순서 동형(order isomorphic)입니다. 다시 말해서, S 위에 바른-순서화는 정확하게 하나의 순서 유형(order type)을 가집니다.

만약 선택의 공리(axiom of choice)가 역시 가정되면 (셀-수-있는 선택의 공리(axiom of countable choice)는 충분합니다^[7]^{[citation needed]}), 다음 조건은 모두 동등합니다:

S는 유한 집합입니다.
(리하르트 데데킨트(Richard Dedekind)) S에서 자체안으로의 모든 각 일-대-일 함수는 위로의입니다.
S에서 자체 위로의 모든 각 전사 함수는 일-대-일입니다.
S는 빈 것이거나 S의 모든 각 부분 순서(partial order)화는 최대 원소(maximal element)를 포함합니다.

Foundational issues

게오르크 칸토어(Georg Cantor)는 무한 집합의 수학적 처리를 제공하기 위해 그의 집합의 이론을 시작했습니다. 따라서 유한과 무한 사이의 구별은 집합 이론의 핵심에 놓여 있습니다. 특정 기초주의자들, 엄격한 유한주의자들(strict finitists)은 무한 집합의 존재를 거부하고 따라서 오직 유한 집합에 기반한 수학을 권장합니다. 주류 수학자들은 엄격한 유한성이 너무 제한적이라고 생각하지만, 그것의 상대적인 일관성을 인정합니다: 유전적으로 유한 집합(hereditarily finite set)의 전체 집합은 무한대의 공리(axiom of infinity)를 그것의 부정으로 대체된 것과 함께 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)의 모델을 구성합니다.

어떤 중요한 문맥에서, 무한한 집합을 수용하는 수학자들에게조차, 유한과 무한 사이의 형식적인 구별은 미묘한 문제로 남아있을 수 있습니다. 그 어려움은 괴델의 불완전성 정리(Gödel's incompleteness theorems)에서 비롯됩니다. 우리는 페아노 산술(Peano arithmetic) 내에서 유전적으로 유한 집합 이론을 해석할 수 있으므로 (확실히 그 반대도 마찬가지임), 페아노 산술 이론의 불완전성은 유전적으로 유한 집합의 이론의 불완전성을 암시합니다. 특히, 두 이론 모두의 소위 비-표준 모델(non-standard models)이 많이 존재합니다. 역설적으로 보이는 것은 무한 집합을 포함하는 유전적으로 유한 집합의 이론의 비-표준 모델이 있지만, 이들 무한 집합은 모델 내에서 유한하게 보인다는 것입니다. (이것은 모델이 이러한 집합의 무한성을 목격하는 데 필요한 집합 또는 함수가 없을 때 발생할 수 있습니다.) 불완전성 정리로 인해, 일-차 술어 또는 일-차 술어의 임의의 재귀 체계조차 모든 그러한 모델의 표준 일부를 특성화할 수 없습니다. 따라서, 적어도 일-차 논리의 관점에서 보면, 우리는 근사적으로 유한성을 설명할 수 있을뿐입니다.

보다 일반적으로, 집합과 특히 유한 집합과 같은 비공식적 개념은 그들의 공리학과 논리적 기구에서 다양한 형식 시스템(formal system)의 범위에 걸쳐 해석을 받을 수 있습니다. 가장 잘 알려진 공리적 집합 이론은 체르멜로–프렝켈 집합 이론 (ZF), 선택의 공리를 갖는 체르멜로–프렝켈 집합 이론 (ZFC), 폰 노이만-베르나이스-괴델 집합 이론(Von Neumann–Bernays–Gödel set theory) (NBG), 비-바른-토대된 집합 이론(Non-well-founded set theory), 버트런드 러셀(Bertrand Russell)의 유형 이론(Type theory)과 그것들의 다양한 모델의 모든 이론을 포함합니다. 우리는 역시 고전적 일-차 논리, 다양한 고차원 논리 및 직관적 논리(intuitionistic logic) 중에서 선택할 수 있습니다.

형식주의자(formalist)는 시스템에서 시스템으로 변하는 집합의 의미^{[citation needed]}를 볼 수 있습니다. 어떤 종류의 플라톤주의자들(Platonist)은 특정 형식 시스템을 놓여있는 현실에 근사하는 것으로 볼 수 있습니다.

Set-theoretic definitions of finiteness

자연수(natural number)의 개념이 집합의 임의의 개념보다 논리적으로 앞서 있는 상황에서, 우리는 집합 S를 만약 그것이 형식 $\{x\,|\,x<n\}$ 의 자연수의 일부 집합과 전단사(bijection)를 허용하면 유한으로 정의할 수 있습니다. 수학자들은 보다 전형적으로 집합 이론(set theory)에서 숫자의 개념을 기반으로 선택하는데, 예를 들어, 그것들은 유한 바른-순서화된(well-ordered) 집합의 순서 유형에 의해 자연수를 모델링할 수 있습니다. 그러한 접근 방식은 자연수에 의존하지 않는 유한성의 구조적 정의를 요구합니다.

ZFC 이론에서 모든 집합 중에서 유한 집합을 발탁하는 다양한 속성은 ZF 또는 직관적 집합 이론과 같은 약한 시스템에서 논리적으로 동등하지 않음이 밝혀졌습니다. 두 가지 정의가 문헌에서 두드러지게 나타납니다. 하나는 리하르트 데데킨트(Richard Dedekind)에 기인하고, 다른 하나는 카지미에시 쿠라토프스키(Kazimierz Kuratowski)에 기인입니다. (쿠라토프스키의 정의가 위에 사용된 것입니다.)

집합 S는 만약 단사, 비-전사 함수 $f:S\rightarrow S$ 가 존재하면 데데킨트 무한(Dedekind infinite)이라고 불립니다. 그러한 함수는 S와 S의 적절한 부분집합, 즉 f의 이미지 사이에 전단사를 나타냅니다. 데데킨트 무한 집합 S, 함수 f, alc f의 이미지 안에 있지 않은 원소 x가 주어지면, 우리는 S의 구별되는 원소의 무한 수열, 즉 $x,f(x),f(f(x)),...$ 을 형성할 수 있습니다. 반대로, 구별되는 원소 $x_{1},x_{2},x_{3},...$ 를 구성하는 S에서 수열이 주어지면, 우리는 수열 $f(x_{i})=x_{i+1}$ 에서 원소이고 그렇지 않으면 f는 항등 함수처럼 행동함을 만족하는 함수 f를 정의할 수 있습니다. 따라서 데데킨트 무한 집합은 자연수와 전단사적으로 대응하는 부분집합을 포함합니다. 데데킨트 유한은 자연스럽게 모든 각 단사 자기-맵이 역시 전사임을 의미합니다.

쿠라토프스키 유한성은 다음처럼 정의됩니다. 임의의 집합 S가 주어지면, 합집합의 이항 연산은 반격자(semilattice)의 구조를 가진 거듭제곱집합(powerset) P(S)를 부여합니다. 빈 집합과 한원소에 의해 생성된 부분-반격자에 대해 K(S)를 쓰면, 만약 S 자체가 K(S)에 속하면 집합 S 쿠라토프스키 집합이라고 부릅니다.^[8] 직관적으로, K(S)는 S의 유한 부분집합으로 구성합니다. 결정적으로, 우리는 무엇에 의해 생성된을 정의하기 위해 자연수의 귀납법, 재귀 또는 정의가 필요하지 않은데, 왜냐하면 우리는 빈 집합과 한원소(singletons)를 포함하는 모든 부분-반격자의 교집합을 단순히 취함으로써 K(S)를 얻을 수 있기 때문입니다.

반격자 및 다른 추상 대수의 개념에 익숙하지 않은 독자는 전적으로 기본 공식화를 선호할 수 있습니다. 쿠라토프스키 유한은 S가 다음처럼 구성된 집합 K(S)에 놓임을 의미합니다. 다음을 만족하는 P(S)의 모든 부분집합 X에 대해 M을 쓰십시오:

X는 빈 집합을 포함합니다;
P(S)에서 모든 각 집합 T에 대해, 만약 X가 T를 포함하면 X는 역시 임의의 한원소를 갖는 T의 합집합을 포함합니다.

그런-다음 K(S)는 M의 교집합으로 정의될 수 있습니다.

ZF에서, 쿠라토프스키 유한은 데데킨트 유한을 의미하지만, 반대는 그렇지 않습니다. 인기있는 교육학적 공식화의 말투로, 선택의 공리가 심하게 실패하면, 우리는 유한하게 많은 쌍 이상에서 하나의 양말을 선택할 방법이 없는 무한한 양말의 가족을 가질 수 있습니다. 그것은 그러한 양말 데데킨트 유한의 집합을 만들 것입니다: 무한 수열의 양말이 있을 수 없는데, 왜냐하면 그러한 수열은 수열에서 첫 번째 양말을 선택함으로써 무한한 많은 쌍에 대해 하나의 양말의 선택을 허용하기 때문입니다. 어쨌든, 쿠라토프스키 유한성은 같은 양말의 집합에 대해 실패합니다.

Other concepts of finiteness

선택의 공리없이 ZF 집합 이론에서, 집합 S에 대해 다음 유한성의 개념이 구별됩니다. 그것들은 엄격하게 감소하는 강도의 순서로 정렬됩니다. 즉, 만약 집합 S가 목록에서 기준을 만족시키면, 그것은 다음 기준의 모두를 충족합니다. 선택의 공리의 부재에서 그 뒤집은 의미는 모두 증명할 수 없지만, 만약 선택의 공리가 가정되면 이들 개념의 모두는 동등합니다.^[9] (이들 정의 중 어느 것도 유한 순서 숫자의 집합을 먼저 정의될 필요가 없습니다; 그것들은 ω를 포함하지 않는 상등과 구성원 관계의 관점에서 모두 순수한 "집합-이론적" 정의입니다.)

I-유한. S의 부분집합의 모든 각 비-빈 집합은 ⊆-최대 원소를 가집니다. (이것은 ⊆-최소 원소의 존재를 요구하는 것과 동등합니다. 그것은 역시 유한성의 표준 수치적 개념과 동등합니다.)
Ia-유한. 둘의 집합으로 S의 모든 각 분할에 대해, 두 집합 중 적어도 하나가 I-유한입니다.
II-유한. S의 부분집합의 모든 각 비-빈 ⊆-단조 집합은 ⊆-최대 원소를 가집니다.
III-유한. P(S)의 거듭제곱 집합은 데데킨트 유한입니다.
IV-유한. S는 데데킨트 유한입니다.
V-유한. ∣S∣ = 0 또는 2⋅∣S∣ > ∣S|.
VI-유한. ∣S∣ = 0 또는 ∣S∣ = 1 또는 ∣S∣² > ∣S∣.
VII-유한. S는 I-유한 또는 바른-순서화할 수 없습니다.

순방향 의미 (강한 것에서 약한 것까지)는 ZF 내의 정리입니다. 원시-원소(urelements)를 갖는 ZF에서 뒤집은 의미 (약한 것에서 강한 것까지)에 대한 반대-예제는 모델 이론(model theory)을 사용하여 발견됩니다.^[10]

이들 유한성 정의와 그 이름의 대부분은 Howard & Rubin 1998, p. 278에 의한 Tarski 1954에 기인합니다. 어쨌든, 정의 I, II, III, IV 및 V는 순방향 의미에 대해 증명 (또는 증명에 대한 참조)과 함께, Tarski 1924, pp. 49, 93에 제시되었습니다. 그 당시에, 모델 이론은 반대-예제를 찾기에 충분하게 진보되지 않았습니다.

속성 I-유한에서 IV-유한까지의 각각은 그러한 속성을 가진 집합의 임의의 부분집합이 역시 속성을 가질 것이라는 의미에서 작은 개념입니다. 이것은 V-유한에서 VII-유한까지에 대해 참이 아닌데 왜냐하면 그것들은 셀-수-있게 무한한 부분집합을 가질 수 있기 때문입니다.

Notes

^ Apostol (1974, p. 38)
^ Cohn (1981, p. 7)
^ Labarre (1968, p. 41)
^ Rudin (1976, p. 25)
^ The equivalence of the standard numerical definition of finite sets to the Dedekind-finiteness of the power set of the power set was shown in 1912 by Whitehead & Russell 2009, p. 288. This Whitehead/Russell theorem is described in more modern language by Tarski 1924, pp. 73–74.
^ Tarski 1924, pp. 48–58, demonstrated that his definition (which is also known as I-finite) is equivalent to Kuratowski's set-theoretical definition, which he then noted is equivalent to the standard numerical definition via the proof by Kuratowski 1920, pp. 130–131.
^ Canada, A.; Drabek, P.; Fonda, A. (2005-09-02). Handbook of Differential Equations: Ordinary Differential Equations. Elsevier. ISBN 9780080461083.
^
The original paper by Kuratowski 1920 defined a set S to be finite when
P(S)∖{∅} = ⋂{X ∈ P(P(S)∖{∅}); (∀x∈S, {x}∈X) and (∀A,B∈X, A∪B∈X)}.
In other words, S is finite when the set of all non-empty subsets of S is equal to the intersection of all classes X which satisfy:
- all elements of X are non-empty subsets of S,
- the set {x} is an element of X for all x in S,
- X is closed under pairwise unions.
Kuratowski showed that this is equivalent to the numerical definition of a finite set.
^ This list of 8 finiteness concepts is presented with this numbering scheme by both Howard & Rubin 1998, pp. 278–280, and Lévy 1958, pp. 2–3, although the details of the presentation of the definitions differ in some respects which do not affect the meanings of the concepts.
^ Lévy 1958 found counter-examples to each of the reverse implications in Mostowski models. Lévy attributes most of the results to earlier papers by Mostowski and Lindenbaum.

References

Apostol, Tom M. (1974), Mathematical Analysis (2nd ed.), Menlo Park: Addison-Wesley, LCCN 72011473
Cohn, Paul Moritz, F.R.S. (1981), Universal Algebra, Dordrecht: D. Reidel, ISBN 90-277-1254-9, LCCN 80-29568{{citation}}: CS1 maint: multiple names: authors list (link)
Dedekind, Richard (2012), Was sind und was sollen die Zahlen?, Cambridge Library Collection (Paperback ed.), Cambridge, UK: Cambridge University Press, ISBN 978-1-108-05038-8
Dedekind, Richard (1963), Essays on the Theory of Numbers, Dover Books on Mathematics, Beman, Wooster Woodruff (Paperback ed.), Dover Publications Inc., ISBN 0-486-21010-3
Herrlich, Horst (2006), Axiom of Choice, Lecture Notes in Math. 1876, Berlin: Springer-Verlag, ISBN 3-540-30989-6
Howard, Paul; Rubin, Jean E. (1998). Consequences of the axiom of choice. Providence, Rhode Island: American Mathematical Society. ISBN 9780821809778.
Kuratowski, Kazimierz (1920), "Sur la notion d'ensemble fini" (PDF), Fundamenta Mathematicae, 1: 129–131, doi:10.4064/fm-1-1-129-131
Labarre, Jr., Anthony E. (1968), Intermediate Mathematical Analysis, New York: Holt, Rinehart and Winston, LCCN 68019130
Lévy, Azriel (1958). "The independence of various definitions of finiteness" (PDF). Fundamenta Mathematicae. 46: 1–13. doi:10.4064/fm-46-1-1-13.
Rudin, Walter (1976), Principles Of Mathematical Analysis (3rd ed.), New York: McGraw-Hill, ISBN 0-07-054235-X
Suppes, Patrick (1972) [1960], Axiomatic Set Theory, Dover Books on Mathematics (Paperback ed.), Dover Publications Inc., ISBN 0-486-61630-4
Tarski, Alfred (1924). "Sur les ensembles finis" (PDF). Fundamenta Mathematicae. 6: 45–95. doi:10.4064/fm-6-1-45-95.
Tarski, Alfred (1954). "Theorems on the existence of successors of cardinals, and the axiom of choice". Nederl. Akad. Wetensch. Proc. Ser. A., Indagationes Math. 16: 26–32. doi:10.1016/S1385-7258(54)50005-3. MR 0060555.
Whitehead, Alfred North; Russell, Bertrand (February 2009) [1912]. Principia Mathematica. Vol. Volume Two. Merchant Books. ISBN 978-1-60386-183-0. {{cite book}}: |volume= has extra text (help)

External links

Barile, Margherita. "Finite Set". MathWorld.

[1] Apostol (1974, p. 38)

[2] Cohn (1981, p. 7)

[3] Labarre (1968, p. 41)

[4] Rudin (1976, p. 25)

[5] The equivalence of the standard numerical definition of finite sets to the Dedekind-finiteness of the power set of the power set was shown in 1912 by Whitehead & Russell 2009, p. 288. This Whitehead/Russell theorem is described in more modern language by Tarski 1924, pp. 73–74.

[6] Tarski 1924, pp. 48–58, demonstrated that his definition (which is also known as I-finite) is equivalent to Kuratowski's set-theoretical definition, which he then noted is equivalent to the standard numerical definition via the proof by Kuratowski 1920, pp. 130–131.

[7] Canada, A.; Drabek, P.; Fonda, A. (2005-09-02). Handbook of Differential Equations: Ordinary Differential Equations. Elsevier. ISBN 9780080461083.

[8] The original paper by Kuratowski 1920 defined a set S to be finite when
P(S)∖{∅} = ⋂{X ∈ P(P(S)∖{∅}); (∀x∈S, {x}∈X) and (∀A,B∈X, A∪B∈X)}.
In other words, S is finite when the set of all non-empty subsets of S is equal to the intersection of all classes X which satisfy:
all elements of X are non-empty subsets of S,

the set {x} is an element of X for all x in S,

X is closed under pairwise unions.
Kuratowski showed that this is equivalent to the numerical definition of a finite set.

[9] ts of X are non-empty subsets of S,

[10] the set {x} is an element of X for all x in S,

[11] X is closed under pairwise unions.

[9] This list of 8 finiteness concepts is presented with this numbering scheme by both Howard & Rubin 1998, pp. 278–280, and Lévy 1958, pp. 2–3, although the details of the presentation of the definitions differ in some respects which do not affect the meanings of the concepts.

[10] Lévy 1958 found counter-examples to each of the reverse implications in Mostowski models. Lévy attributes most of the results to earlier papers by Mostowski and Lindenbaum.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]