수학의 세트이론 구현

이 글은 세트 이론에서 수학 개념의 구현을 고찰한다.다수의 기초 수학 개념의 구현은 ZFC(주요 세트 이론)와 NFU에서 병행하여 수행되며, 콰인의 새로운 기초는 1969년 R. B. Jensen에 의해 일관성이 있는 것으로 나타났다(여기서는 최소한 인피니티와 초이스의 공리를 포함하는 것으로 이해됨).

여기서 언급된 것은 또한 두 개의 정해진 이론들에도 적용된다: 한편으로, 저울 하단에 가까운 저멜로 세트 이론을 포함한 다양한 이론들과 "측정이 가능한 추기경이 있다"와 같은 큰 기본 가설들과 함께 확장된 ZFC까지 가는 이론들 그리고 다른 한편으로, 뉴 포에서 조사된 NFU의 확장 계층 구조.유통 기물이것들은 집합이론적 우주가 어떤 것인지에 대한 다른 일반적인 견해에 해당하며, 비교되고 대조되고 있는 것은 이 두 가지 일반적인 견해에 따른 수학적 개념의 구현에 대한 접근법이다.

수학의 기초로서 이들 이론의 상대적 장점에 대해 뭐라고 말하는 것이 이 글의 주된 목적은 아니다.두 가지 서로 다른 세트 이론을 사용하는 이유는 수학의 구현에 대한 다중 접근법이 실현 가능하다는 것을 설명하기 위함이다.정확히 이 접근법 때문에, 이 기사는 어떤 수학 개념에 대한 "공식적인" 정의의 출처가 아니다.

예선

다음 절에서는 두 이론 ZFC와 NFU의 특정 구성을 수행하고 특정 수학 구조(자연수 등)의 구현 결과를 비교한다.

수학 이론은 이론들을 증명한다.그래서 어떤 이론이 어떤 물체의 구성을 허용한다고 하는 것은 그 물체가 존재한다는 것이 그 이론의 정리라는 것을 의미한다.이 $이론$은$$"[\disp] {\$displaystyle \pi }$이(가) 존재하는 x" 형식의 정의에$$ 대한 진술이다$$. 여기서 $\varphi {\displaystyle }$ ${\displaystyle$ $\pi$$}$은(는) 우리 언어의 공식이다: " theory {\$disp$}이라는 정리만 있다면 "$"$의 존재를 증명한다.$레이스타일 \phi }$ ".$$ (버트랜드 러셀의 서술 이론 참조)느슨하게, 이론은 이 경우에 이 물체를 "defines" 또는 "construction"한다.만약 그 진술이 정리가 아니라면, 그 이론은 그 물체가 존재한다는 것을 증명할 수 없다. 만약 그 진술이 이론에서 명백히 거짓이라면, 그것은 그 물체가 존재할 수 없다는 것을 증명한다. 느슨하게, 그 물체는 구성될 수 없다.

ZFC와 NFU는 집합 이론의 언어를 공유하기 때문에 두 이론에서 동일한 공식 정의 "$x$와 같은 형식적 정의 $"{\displaystyle \pi$를 고려할 수 있다.세트 이론 언어의 특정한 ${\displaystyle \mathrm{정의}}$ 형태는 세트빌더 표기법이다:${\displaystyle }${ x ${\displaystyle \mid }$ ${\displaystyle \varphi }$ ϕ${\displaystyle }$} ${\displaystyle \{x\mid \phi \}}}$은 "모든 x, $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle A}$ $↔ {\$$displaystystyle$ $x\in$$\phi$$\}"$과 같은 집합 A를 의미한다$.$This notation admits certain conventional extensions: ${\displaystyle \{x\in B\mid \phi \}}$ is synonymous with ${\displaystyle \{x\mid x\in B\wedge \phi \}}$; ${\displaystyle \{f(x_{1},\ldots ,x_{n})\mid \phi \}}$ is defined as ${\displaystyle \{z\mid \mathrm{\exists }{x}_1,\dots ,x_n}$${\displaystyle \{z\mid \exists x_{1},\ldots ,x_{n}\,(z=f(x_{1},\dots ,x_{n})\wedge \phi )\}}$, where ${\displaystyle f(x_{1},\ldots ,x_{n})}$ is an expression already defined.

세트빌더 표기법으로 정의할 수 있는 표현은 ZFC와 NFU 모두에서 이치에 맞을 수 있다: 두 이론 모두 주어진 정의가 성공한다는 것을 증명하거나 둘 다 그렇지 않다는 것을 증명하는 것일 수 있다$({x\mid x\not x\in\}}).$ 고전적 논리가 있는 어떤 세트 이론의 어떤 것도 참조하지 못한다$$. NBG와 같은 클래스 이론에서 이 표기법에서는클래스를 가리키지만 클래스는 다르게 정의된다) 또는 클래스와 클래스는 다르게 정의된다.또한 ZFC와 NFU에서 동일한 방법으로 정의된 물체는 두 이론에서 서로 다른 성질을 가질 수 있다(또는 그 성질들 사이에 증명할 수 있는 성질의 차이가 있을 수 있다).

또한, 집합 이론은 수학의 다른 분야(의도적으로, 수학의 모든 분야)에서 개념을 가져온다.경우에 따라서는 ZFC와 NFU로 개념을 가져오는 방법이 다른 경우도 있다. 예를 들어, ZFC의$$ 첫 번째 무한 서수 $\Omega {\displaystyle }$ ${\displaystyle \omega$}의 통상적인 정의는 개체(모든 유한한 폰 노이만 서수의 집합으로 순수하게 설정된 이론적 언어로 정의됨)가 NFU에 존재한다고 표시할 수 없기 때문에 NFU에 적합하지 않다.FU. NFU에서$$ $\Omega {\displaystyle }$ ${\displaystyle \omega }$의 통상적인 정의는 (순전히 설정된 이론적 언어로) 적절한 초기 세그먼트가 유한한 모든 무한 웰 오더의 집합이며, ZFC에는 존재하지 않는다는 것을 나타낼 수 있다.그러한 수입물체의 경우 ZFC 및 관련 이론에 사용하기 위한 정의와 NFU 및 관련 이론에 사용하기 위한 정의가 다를 수 있다.이러한 수입 수학 개념의 "이행"이 이치에 맞도록 하려면, 예를 들어 ZFC와 NFU에서 자연수의 구현은 다르지만, 두 해석 모두 동일한 수학 구조의 구현이라는 두 가지 병렬 해석의 특성을 가질 수 있음을 보여줄 필요가 있다.e Peano 산술의 모든 원시성에 대한 정의와 Peano 공리의 번역을 만족한다.그런 다음 ZFC에 적합한 정의가 ZFC 컨텍스트에서 사용되고 NFU에 적합한 정의가 NFU 컨텍스트에서 사용되는 것으로 이해되는 한, 정해진 이론 언어만 사용 중일 때 두 이론에서 일어나는 일을 비교할 수 있다.

이론에 존재하는 것으로 입증된 것은 그 이론의 어떤 확장에도 분명히 존재한다. 더욱이, 주어진 이론에 어떤 물체가 존재한다는 증거의 분석은 그 이론의 약한 버전에도 그것이 존재한다는 것을 보여줄 수 있다(예를 들어, 이 글에서 행해지는 많은 것에 대해 ZFC 대신에 Zermelo 세트 이론을 고려할 수도 있다).

빈 세트, 싱글톤, 정렬되지 않은 쌍 및 튜플

이러한 구성들은 집합 이론에서 가장 단순한 구성이기 때문에 먼저 나타나는 것이지 수학에서 가장 먼저 떠오르는 구성이기 때문이 아니다(한정 집합의 개념은 확실히 기본이지만).NFU는 또한 세트 소자 구성을 허용하지만 세트의 멤버가 될 수는 없다. 빈 세트는 멤버가 없는 독특한 세트다.

$왼쪽.\varnothing \right.\,{\overset {\mathrm {def.}}}{=}\}왼쪽\{x:x\neq x\오른쪽\}}}$

각 개체 $x{\displaystyle }$ ${\displaystyle x}$에 대해$,$ 집합 { x ${\displaystyle \}}${\$displaystyle$\{$x\}$이(가) 있고 $x$는 ${\displaystyle$ x$}$을(를) 유일한 요소로 한다$$.

${\displaystyle \left\{x\right\}{\overset {\mathrm {def.}}}{}}\왼쪽\{y:y=x\오른쪽\}}}$

개체 $x{\displaystyle }$ ${\displaystyle x}$ $및$ y ${\displaystyle y}$의 경우$,$ $x{\displaystyle }${\$displaystyle x}$ 및 $y{\displaystyle }${\$displaystyle y}$을(를$)$ 포함하는 집합${\displaystyle }${ x${\displaystyle }$, $}$이$(가)$ 있다.

${\displaystyle \left\{x,y\right\}{\overset {\mathrm {def.}}{}}\}\왼쪽\{z:z=x\vee z=y\right\}}}}$

두 세트의 결합은 통상적인 방법으로 정의된다.

$왼쪽.x\cup y\right.\,{\overset {\mathrm {def.}}{}}}\{}\왼쪽\{z:z\in x\vee z\in y\right\}}}$

이는 콘크리트 $n{\displaystyle }$ ${\displaystyle n}$에 대해 순서가 지정되지 $않은{\displaystyle }$ n ${\displaystyle$ n$}$ -tuple에$$ 대한 재귀적 정의($$원소 목록으로 제공된 최종 세트:)이다.

${\displaystyle \left\{x_{1},\ldots,x_{n},x_{n+1}\right\}{\overset {\mathrm {def.}}{}}}\{}}\{x_{1},\ldots,x_{n}\right\}\cup \{x_{n+1}\right\}}컵\{x_{n+1}\}}}}}}}}}}}}$

NFU에서는 계층화된 이해에 의해 주어진 모든 설정 정의, ZFC에서는 순서 없는 쌍의 존재는 쌍의 공리에 의해 주어지고, 빈 집합의 존재는 어떤 집합과의 분리에 의해 뒤따르며, 두 집합의 2진 조합은 쌍과 결합의 공리에 의해 존재한다(${\displaystyle }$∪${\displaystyle y}$ = ${\displaystyle \bigcup }$ ⋃ ⋃ ⋃ { ${\displaystyle \{}$ {${\displaystyle }${ { { { { { ${\displaystyle yy}$ $y$ { { { { { { { { { { { { ${$ { { { { { { { { { { { {$x\cup$ y$=\bigcup \{x,y\}}.$

순서쌍

먼저, 주문한 쌍을 고려하십시오.이것이 우선인 이유는 기술적인 것이다: 관계와 기능을 구현하기 위해 순서 쌍이 필요하며, 이는 이전처럼 보일 수 있는 다른 개념을 구현하기 위해 필요하다.The first definition of the ordered pair was the definition ${\displaystyle (x,y){\overset {\mathrm {def} }{=}}\{\{\{x\},\emptyset \},\{\{y\}\}\}}$ proposed by Norbert Wiener in 1914 in the context of the type theory of Principia Mathematica.Wiener는 이것이 n > 1에 대한 n-ari 관계의 유형을 해당 작업 시스템에서 제거할 수 있다고 보았다.정의$({\displaystyle x}$, ${\displaystyle y}$)${\displaystyle \stackrel{}{}}$= ${\displaystyle \stackrel{}{\mathrm{d}}}$ ${\displaystyle \stackrel{}{\mathrm{e}}}$ .${\displaystyle \stackrel{}{}}${${\displaystyle \stackrel{}{}}$x${\displaystyle \},}${${\displaystyle }$x }, { ${\displaystyle x}$ ${\displaystyle \},}$ ${\displaystyle y}$ ${\displaystyle \}}$ ${\displaystyle (x,y){\overset {\mathrm$ {$def$}을(를) 사용하는 것이 지금은 더 일반적이다$.$$}}{=}}\{}\{x\}}\{x,y\}\}}}}}$ 쿠라토프스키 때문에$.$이 두 정의 중 하나는 ZFC나 NFU에서 통한다.NFU에서 이 두 정의는 기술적 단점이 있다: 쿠라토프스키 주문 쌍은 그 예상보다 두 가지 유형이 높은 반면, 위너 주문 쌍은 세 가지 유형이다.NFU에서 유형 수준의 순서 쌍(쌍$({\displaystyle x}$, y${\displaystyle }$) ${\displaystyle(x,y)})$의 존재를 가정하는 것이 일반적이다.형식 수준 쌍의 사용이 정식으로 정당화될 때까지 두 시스템 모두에서 쿠라토프스키 쌍을 사용하는 것이 편리하다.이러한 정의의 내부적인 세부사항들은 그들의 실제 수학적 함수와는 아무런 관계가 없다.순서 쌍$({\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle (x,y)}$의 개념에서 중요한 것은 정의 조건을 만족한다는 것이다.

$\displaystyle (x,y)=(z,w)\\equiv \x=z\j\buff y=w}$

…순서된 쌍을 세트로 수집하는 것이 합리적으로 쉽다는 것.

관계

관계는 모든 멤버가 쌍으로 정렬된 집합이다.Where possible, a relation ${\displaystyle R}$ (understood as a binary predicate) is implemented as ${\displaystyle \{(x,y)\mid xRy\}}$ (which may be written as ${\displaystyle \{z\mid \pi _{1}(z)R\pi _{2}(z)\}}$).$R{\displaystyle }$ ${\displaystyle R}$이(가) 관계인$$ 경우 표기법 $x{\displaystyle }$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle$ ${\displaystyle \mathrm{xRy}}$$}$은${\displaystyle (}$ x${\displaystyle }$, ${\displaystyle y}$) ${\displaystyle R}$ ${\displaystyle \left(x,y\right)\in$ R$}$을 의미한다$.$

ZFC에서 일부 관계(예: 일반 평등 관계 또는 세트의 부분 집합적 관계)는 '너무 커서 집합할 수 없다'(단, 해롭지 않게 적절한 등급으로 재조정될 수 있다).NFU에서 일부 관계(${\displaystyle 예}$: 멤버십 관계)는 정의가 계층화되지 않기 때문에 설정되지 않는다.${\displaystyle }${${\displaystyle }$( x${\displaystyle }$,${\displaystyle y}$ )${\displaystyle x}$ x ${\displaystyle \in }$ ${\displaystyle y}$} ${\displaystyle \{(x,y)\mid$ x$\in$ y$\}}$ x ${\$$displaysty x$$}$ 및$$ y$}}$은(같은 쌍의 투영으로 나타나기 때문에)가 같아야 하지만$$ 성공하기도 한다.sive 유형($x{\displaystyle }$ ${\displaystyle x}$이(가) $y{\displaystyle }$ ${\displaystyle y}$의 요소로 간주되기$$ 때문에).$$

관련 정의

$R{\displaystyle }$ ${\displaystyle R}$과 $S{\displaystyle }$ ${\displaystyle S}$에게 이진 관계를 부여하십시오$$.그렇다면 다음과 같은 개념이 유용하다.

$R{\displaystyle }$ ${\displaystyle R}$의 반향은${\displaystyle }$관계${\displaystyle }${ (${\displaystyle y}$ ,${\displaystyle x}$) : ${\displaystyle x}$ $}$ {\$displaystyle \left\{\\put(y,x\right):$$XRY\right$

$R{\displaystyle }$ ${\displaystyle R}$의 도메인은${\displaystyle }${ x :${\displaystyle \mathrm{\exists }}$ ${\displaystyle y}$(${\displaystyle x}$ ${\displaystyle R}$ y${\displaystyle )\}}$ ${\$의 집합이다$.$

$R{\displaystyle }$ ${\displaystyle R}$의 범위는 $R$ ${\displaystyle R}$의 역방향 영역$.$ 즉$,{\displaystyle }$ 세트 {${\displaystyle y}$ :${\displaystyle \mathrm{}x}$x (${\displaystyle \mathrm{xRy}}$\right${\$ x$\reft(xRy\right$

$R{\displaystyle }$ ${\displaystyle R}$의 필드는 $R{\displaystyle }$ ${\displaystyle R}$의 도메인과 범위의 결합이다$.$

$R{\displaystyle }$ ${\displaystyle R}$ 필드의$$ $멤버{\displaystyle }$ x ${\displaystyle x}$ 사전 이미지는${\displaystyle }${${\displaystyle y}$: ${\displaystyle y}$ : y${\displaystyle }$x $}$ {\$displaystyle \{y:yRx\$right$\}}}$ 세트(아래 '잘 근거된'의 정의에서 사용됨)이다$$.

$R{\displaystyle }$ ${\displaystyle R}$ 필드의$$ $멤버{\displaystyle }$ x ${\$$displaystyle$ $x$$}$의 하향 마감은 x ${\displaystyle x$을(를) 포함하고 각 $y{\displaystyle }$containing$$ ${\displaystyle D}$ ${\displaystyle y\in D}$에 대해 각 z R {\$displaystystyle zRy}$을(즉, 각 요소의 사전 이미지 포함) 포함하는)를 포함하는 최소 세트 D$${\d)이다.h 하위 집합으로$$ $R{\displaystyle }$ ${\displaystyle R}$에 대한 존중).

$R{\displaystyle }$ ${\displaystyle R}$과(와$)$ $S{\displaystyle }$ {\$displaystyle$ $R$$}$의 상대 제품 ${\displaystyle R}S{\displaystyle }$ {\$displaystyle$ R}은$($는)${\displaystyle }${ (${\displaystyle x}$ ,${\displaystyle z}$) :${\displaystyle \mathrm{}y}$y ( ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle \wedge }$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle z)\}\}}${\$displaysty \{\put(x,z\rig$):$\exists y\,\왼쪽(xRy\wedge ySz\오른쪽)\오른쪽$

이항 관계에 대한 우리의 공식적 정의로, 관계의 범위와 코도메인은 구별되지 않는다는 점에 유의하십시오.$이$는 (${\displaystyle R}$, ${\displaystyle B}$) ${\displaystyle B}$과(와) 관계 $R{\displaystyle }$ ${\displaystyle$ B$}$을$($를) $({\displaystyle }$R , B ) ${\$로 표현함으로써 이루어질 수 있지만, 우리의 개발은 이것을 요구하지 않을 것이다.

In ZFC, any relation whose domain is a subset of a set ${\displaystyle A}$ and whose range is a subset of a set ${\displaystyle B}$ will be a set, since the Cartesian product ${\displaystyle A\times B=\left\{\left(a,b\right):a\in A\wedge b\in B\right\}}$ is a set (being a subclass$P{\displaystyle \mathcal{}}$(${\displaystyle A}$ ${\displaystyle \cup }$ ${\displaystyle B}$)의 ${\$$\left(A\cup B\right)}$), and Separation provides for the existence of ${\displaystyle \left\{\left(x,y\right)\in A\times B:xRy\right\}}$. In NFU, some relations with global scope (such as equality and subset) can be implemented as sets.NFU에서 $x{\displaystyle }$ ${\displaystyle x}$ $및{\displaystyle }$ y$$ ${\displaystyle y}$은(는) ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle xRy}$의 R ${\displaystyle R}$보다 세 가지 유형(유형 수준 순서 쌍을 사용하는 경우 한 유형 낮음)임을$$ 명심하십시오.$$

관계의 속성 및 종류

이진 관계 $R{\displaystyle }$ ${\displaystyle R}$은(는) 다음과 같다.

• $R{\displaystyle }$ ${\displaystyle R}$필드의 모든$$ $x{\displaystyle }$ ${\displaystyle x}$에 대해 $x{\displaystyle }$ R ${\displaystyle x}$ ${\displaystyle xRx}$의 반사적 경우.
• 대칭:${\displaystyle \mathrm{}}$symmet ${\displaystyle x}$, ${\displaystyle y}$( ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle y}$→ y ${\displaystyle R}$ ${\displaystyle x}$) ${\displaystyle \forall x,y\,$ ($xRy\to yRx$
• transitive ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle z}$ ${\displaystyle (x}$ ${\displaystyle R}$ ${\displaystyle y}$ ${\displaystyle \wedge }$ ${\displaystyle y}$ ${\displaystyle R}$ ${\displaystyle z}$→ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle z}$) ${\displaystyle \forall x,y,z\,$ ($xRy\wedge yRz\rightarrow xRz$
• 대칭성이 ${\displaystyle \mathrm{if}}{\displaystyle \mathrm{}}$x${\displaystyle }$, y${\displaystyle }$(${\displaystyle x}$ R ${\displaystyle y}$ ${\displaystyle \wedge }$ ${\displaystyle R}$ x${\displaystyle }$→ x${\displaystyle }$= ${\displaystyle y}$) ${\displaystyle \forall x,y\,$ ($xRy\wedge yRx\오른쪽$ 화살표 $x=y)}$인 경우 $.$
• $R{\displaystyle }$ ${\displaystyle R$$},$${\displaystyle \exists \mathrm{}}$ ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle s}$ ${\displaystyle \exists$ x$\in S}$의 필드를 충족하는$$ 모든 $세트{\displaystyle }$ S ${\displaystyle S$에 대해 근거가 충분한 경우$$.
• $R{\displaystyle }$ ${\$$displaystyle R$ $x{\displaystyle }$= ${\displaystyle y}$ ${\displaystyle$ $x$$},$ $x$ {\displaystyle x$}$ 및 y ${\displaystyle$y} 필드의$$ $모든$$x,$ {\$displaystyle r}$에 동일한 사전 이미지가 $있는$ 경우에만$$ $확장$$.$

위의 속성의 특정한 조합을 가지는 관계에는 표준 이름이 있다.이진 관계 $R{\displaystyle }$ ${\displaystyle R}$은(는) 다음과 같다.

• $R{\displaystyle }$ ${\displaystyle R}$이(가) 반사성, 대칭성 및 전이성인$$ 경우 동등성 관계.
• $R{\displaystyle }$ ${\displaystyle R}$이(가) 반사성, 대칭성 및 전이성인$$ 경우 부분 순서.
• $R{\displaystyle }$ ${\displaystyle R}$이(가) 부분 순서이고$$ R ${\displaystyle R}$ 필드의 ${\displaystyle \mathrm{모든}}$ x${\displaystyle }$, y ${\displaystyle$ x$,y}$에 대해$$${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle xRy}$ 또는$$ Y ${\displaystyle x}$ ${\displaysty yRx}$ 중 하나일 경우 선형 순서$.$
• $R{\displaystyle }$ ${\displaystyle R}$이(가) 선형 순서이고 근거가 충분한 경우 정렬.
• $R{\displaystyle }$ ${\displaystyle R}$이(가) 근거가 충분하고 확장적인 경우$$ 세트 그림이며, $R{\displaystyle }$ ${\displaystyle R}$의 필드는 멤버 중 한 명의 하향 마감(상단 요소라고 함)과 같거나$$ 비어 있는 경우.

기능들

함수관계는${\displaystyle \mathrm{}\mathrm{binary}}$ x ,${\displaystyle y}$, z ${\displaystyle (x}$F y $style$ x F z →${\displaystyle y}$= ${\displaystyle z}$)와 같은$$ 이진 $술어{\displaystyle }$ F ${\$displaystyle $F}$이다${\displaystyle .}$ ${\displaystyle \forall$ x$,y,z\,\좌(xFy\wedge xFz\to y=z\rig).$$}}$ 그러한$$ 관계(predicate)는 앞의 절에서 설명한 것과 정확히 같은 관계(set)로 구현된다.따라서 술어 $F{\displaystyle }${\$displaystyle F}$은$($는) {${\displaystyle }$( x${\displaystyle }$, ${\displaystyle y}$)${\displaystyle }$: ${\displaystyle x}$ ${\displaystyle F}$ ${\displaystyle y}$ ${\displaystyle \}}$ ${\$):$xFy\right\}}$. A relation ${\displaystyle F}$ is a function if and only if ${\displaystyle \forall x,y,z\,\left(\left(x,y\right)\in F\wedge \left(x,z\right)\in F\to y=z\right).$$}$ ${\displaystyle \mathrm{따라서}}$ 값$$ 함수 $F{\displaystyle }$( x${\displaystyle }$) ${\$ F$\!$$\left(x\오른쪽)$를 고유한 개체 $y{\displaystyle }$ ${\displaystyle y}($$예$: Fy})로$$ 지정하여 x ${\displaystyle \mathrm{Fy}}$ ${\displaystyle xFy}$ –:$$${\displaystyle x}$ ${\displaystyle$ $x}$은(는) $y{\displaystyle }$ ${\displaystyle$ $x$$}$과($와{\displaystyle }$) y ${\displaystyle$ $y}$ 사이에 $관계{\displaystyle }$ f ${\displaystyle$ $f$$}$이$($가) ${\displaystyle \mathrm{있거나<img\; alt="f"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61"\; style="vertical-align:\; -0.671ex;\; width:1.279ex;\; height:2.509ex;">}}$ (${\displaystyle x}$, ${\displaystyle y}$ ) $\displaystyle \left(x,y\right)\ftin$ F$}$과(으)인) $같은$ 고유한$$ 개체 y ${\displaysty$}과(으) 관련된다.$$. 설정되지 않은 기능 술어의 두 이론 모두 존재는 표기법 ${\displaystyle F}$( x${\displaystyle }$) ${\$$\$$left{\displaystyle }$$(x\오른쪽)$ 세트 F ${\displaystyle F}$와 중요한 기능 술어의 경우 모두 왼쪽$$(x\오른쪽)을 선택하십시오.후자의 의미에서의 기능에 대해 수량화하지 않는 한, 그러한 모든 사용은 원칙적으로 제거할 수 있다.

형식 집합 이론의 외부에서는 "Let $f{\displaystyle }$: ${\displaystyle A}$→ B ${\displaystyle$ f$::$$A\to B}$은(는) 함수가 된다$$."함수의 영역은 단지 관계로서의 그것의 영역일 뿐, 함수의 코도메인을 아직 정의하지 않았다.이를 위해 도메인이 $A{\displaystyle }$ ${\displaystyle A}$이고 $범위$가 B ${\displaystyle B}$에 포함된 경우$$ 함수가 $A{\displaystyle }$ ${\displaystyle A}$에서 $B{\displaystyle }$ ${\displaystyle B}$ 사이라는 용어를 도입했다$.$ 이렇게 하면 모든 함수는 도메인에서 범위까지의 함수이며, $f{\displaystyle }${\$displaysty f}$ f$$.$m{\displaystyle }$ $A{\displaystyle }$ ${\displaystyle A}$ ~ B ${\displaystyle B}$은(는) $B{\displaystyle }$ ${\displaystyle B}$을(를) 포함하는$$ 모든 $세트{\displaystyle }$ C ${\displaystyle$ C$}$에 대해 $A{\displaystyle }$ ${\$$displaystystyle A$$}$에서 $}$까지의 함수이기도 하다$$$.$

실제로, 우리가 함수의 코도메인으로 간주하는 세트는 정의상 순서가 정해진 한 쌍의 집합일 뿐이기 때문에 함수는 집합으로 변하지 않는다.즉, 함수는 우리의 정의에 의해 그것의 코도메인을 결정하지 않는다.만약 누군가가 이것이 매력적이지 않다고 발견한다면$,{\displaystyle }$ 대신 f ${\displaystyle \{\backslash }$$displaystyle f}$ ${\displaystyle (f,B)}$로 함수를 정의할 수 있다$.$ 여기서 $f{\displaystyle }$ ${\$displaystyle f}은$$ 기능적 $관계$이고 B ${\displaystyle$B}은 코드메인이지만$$, 우리는 이 글에서 이 접근법을 채택하지 않는다(만약 한 사람이 먼저 순서 3배 - ex에 대해 더 우아하게).(${\displaystyle x}$, ${\displaystyle y}$, z${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle x}$,${\displaystyle }$( ${\displaystyle y}$, z${\displaystyle }$)${\displaystyle (x,y,z)=(x,$ ($y,z))}$- 그러면 도메인을 포함하기 위해$$ 순서가 지정된 트리플$({\displaystyle f}$ ,${\displaystyle A}$,${\displaystyle B}$ )$${\$displaystyle (f,A,B)}$로 함수를 정의할 수 있다.Note that the same issue exists for relations: outside of formal set theory we usually say "Let ${\displaystyle R\subseteq A\times B}$ be a binary relation", but formally ${\displaystyle R}$ is a set of ordered pairs such that ${\displaystyle {\text{dom}}\,R\subseteq A}$ and ${\displayst$$yle {\text{ran}\,R\subseteq B}$.

NFU에서 $x{\displaystyle }$ ${\displaystyle x}$은(는${\displaystyle )}$ $($ ) {\displaystyle $F\!$와 동일한 유형을 가짐$$$\left(x\right)}$및$F{\displaystyle }$ {\$displaystyle F}$은$($는) {\$displaystyle$ F$\!$보다 세 가지 유형이 높다$$.$\left(x\right)}($유형 수준 순서 쌍을 사용하는 경우 한 유형 더 높음).이 문제를 해결하기 위해 $F{\displaystyle }$[ ${\displaystyle A}$ ${\displaystyle ]}$ $[\$를 정의할 수 있다.$A\right]}$을$({\displaystyle }$를) { ${\displaystyle y}$ :${\displaystyle \mathrm{\exists }}$ x${\displaystyle }$( ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle A}$ ${\displaystyle \wedge }$ ${\displaystyle y}$= ${\displaystyle F}$(${\$exists $x\,\좌(x\in$A\$wedge$ y$=F\)$로 표시!$\left(x\\오른쪽$)\right$\}$ 집합 $A{\displaystyle }$ ${\displaystyle A$에 대해$$\$reft$(오른쪽$)\$right\}\}\}}이(가)지만$,{\displaystyle }$ {${\displaystyle F(x}$)${\displaystyle }$: ${\displaystyle x}$as ${\displaystyle A\}}$ ${\$로 보다 편리하게 기록된다.$F\\\좌(x\우측):x\in$ A$\우측$ $그러면{\displaystyle }$ A ${\displaystyle A}$이(가) 세트이고 F ${\displaystyle F}$이(가) 기능적$$ 관계라면 교체의 악시오는 $F{\displaystyle }$[ ${\displaystyle A}$ ${\displaystyle ]}$ ${\$을 보장한다.$A\right]}$은(는) ZFC의 세트다.NFU에서는 $F{\displaystyle }$[ ${\displaystyle A}$ ${\displaystyle ]}$ ${\$$A\right]}$과($)$ {\$displaystyle$ A$}$은(는) 현재$$ 유형이 같고, $F{\displaystyle }$ ${\displaystyle$ F$}$은(는) $F{\displaystyle }$ [${\displaystyle A}$ ${\displaystyle ]}$ ${\$보다 두 가지 유형이 높다$$.$A\right]}($유형 수준의 순서 쌍을 사용하는 경우 동일한 유형).

${\displaystyle \mathrm{함수}}$ I${\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= x ${\displaystyle$ I$\!$$\left(x\right)=x}$은(는) "너무 크므로 ZFC의 집합이 아니다$$.${\$그러나 $\left(x\right)$는 NFU의 집합이다.함수(predicate) $S{\displaystyle (x}$)${\displaystyle }$=${\displaystyle }${ ${\displaystyle x}$ ${\displaystyle \}}$ ${\$ S$\!\좌측(x\우측)=\좌측$(x\우측)=\좌측$\{x\우측\}}}$은 어느 이론에서도 함수나 집합이 아니며$$, ZFC에서는 그러한 집합이 너무 크므로 이것은 사실이며, NFU에서는 그 정의가 층화되지 않기 때문에 사실이다.${\displaystyle \mathrm{더욱이}}$ $S{\displaystyle }$( x${\displaystyle }$) ${\$ S$\!\좌(x\우)}$은(는) NFU에 존재하지 않는다는 것을 증명할 수 있다$$(New Foundation에서 칸토어의 역설의 해결 참조).

기능에 대한 작업

$f{\displaystyle }$ ${\displaystyle f}$ 및$$ $g{\displaystyle }$ ${\displaystyle g}$을(를) 임의 함수로 한다$$.${\displaystyle f}$ ${\displaystyle f$${\displaystyle \}}$ $및$ g ${\displaystyle$ $g$ $g{\displaystyle }$ ${\displaystyle \circ }$ f ${\$$displaystyle$ $g\, \$$displaystyle$ $g{\displaystyle }$\, $\,$$g}$의 $구성$은 $상대$ 제품 f g {\displaystytle $\circ f},$ ${\displaystyle \backslash }$x$$ = (${\displaystyle f)}$와 같은${\displaystyle 함수}$인 경우에만 ${\displaystyle 정의}$된다.${\$$\왼쪽(x\오른쪽)=g\!$$\왼쪽(f\!)$$\left(x\오른쪽$ f ${\displaystyle f}$의 범위가 $g{\displaystyle }$ ${\displaystyle g}$ 도메인의 하위 집합인$$ 경우$.$$f{\displaystyle {}^{}}$ ${\displaystyle$ f$\},$ f${\displaystyle {}^{}}$(${\displaystyle {}^{}}$- 1${\displaystyle {}^{}}$) ${\$의 역행은 함수인$$ $경우{\displaystyle }$ f$${\$displaystyle f}$의 역행으로 정의된다.설정된 $A{\displaystyle }$ ${\displaystyle A}$이$($가) 있을 경우 $ID{\displaystyle {}_{}}$ ${\displaystyle {함수}_{}}$ I ${\$$A$${\displaystyle \}}$은(${\displaystyle }$x${\displaystyle }$, ${\displaystyle x}$ )${\displaystyle }$∣${\displaystyle }$x ∈${\displaystyle x}$ x ${\displaystyle x}$ \ \ $}$ {\$displaystyle \left\{\put(x,x\right)\mid x\in$A\$right$ 이 세트는 ZFC와 NFU에서 각각 다른 이유로 구성된 세트다.

특수기능종류

함수는 역함수를 갖는 경우 주입(일대일이라고도 함)이다.

$A{\displaystyle }$ ${\displaystyle A}$에서 $B{\displaystyle }$ ${\displaystyle B}$까지의 함수 $f{\displaystyle }$ ${\displaystyle f}$은(는) 다음과 같다.

• $A{\displaystyle }$ ${\displaystyle A}$의 고유 멤버인$$ $f{\displaystyle }$ ${\displaystyle f}$ 아래의 이미지가 $B{\displaystyle }$ ${\displaystyle B$의 고유 멤버인$$ 경우$$ $A{\displaystyle }$ ${\displaystyle A}$에서 B ${\displaystytle$ B$}$로 주입.
• $f{\displaystyle }$ ${\displaystyle f}$의 $범위$가 B ${\displaystyle B}$인 경우$$ $A{\displaystyle }$ ${\displaystyle A}$에서 B ${\displaystyle B}$까지의 추측$.$
• $f{\displaystyle }$ ${\displaystyle f}$이(가) 주입 및 추리인 경우$$ A ${\displaystyle$ $A$$}$에서 B ${\displaystyle$ B$}($으)로 바이어싱.

Defining functions as ordered pairs ${\displaystyle (f,B)}$ or ordered triples ${\displaystyle (f,A,B)}$ has the advantages that we do not have to introduce the terminology of being a function "from ${\displaystyle A}$ to ${\displaystyle B}$", and that we can speak of "being surjective" outright as는 "$B{\displaystyle }$ ${\displaystyle B}$에 대해 굴욕적으로만 말할 수 있는 것에 반대한다.$$

세트 크기

ZFC와 NFU에서 두 세트 A와 B는 A에서 B로 바이어싱 f가 있는 경우에만 같은 크기(또는 등분형)이다.이것은 ${\displaystyle A}$= B $displaystyle$ A$$= B$}$로 쓸 수 있지만$,$ (현재로서는) 이것은 아직 정의되지 않은 개체 ${\displaystyle A}$ $displaystyle$A}과$$ ${\displaystyle B}$ $displaystyle B}$ 사이의 관계보다는 $A$와 B의 관계를 나타낸다는 점에 유의하십시오$.$ 이 관계를 A ~ ${\displaystyty A\Sim B}$에 표시하십시오.추상적인 추기경들을 상정하는 모습조차 피해야 하는 추기경들의 실제적 정의와 같은 맥락들

마찬가지로 A에서 B로 주사하는 경우에만 A${\displaystyle a}$ B $displaystyle$A$\leq$B$}$을(를) 홀딩으로$$ 정의하십시오.

등분율의 관계가 등가관계임을 보여주는 것은 간단하다: A와 A의 등분율은 ${\displaystyle i_{}}$ ${\$에 의해 목격된다.$A}}$; if f witnesses ${\displaystyle A = B }$, then ${\displaystyle f^{-1}}$ witnesses ${\displaystyle B = A }$; and if f witnesses ${\displaystyle A = B }$ and g witnesses ${\displaystyle B = C }$, then ${$$\displaystyle g\circulef}$증인$$ ${\displaystyle A}$= ${\displaystyle C}$ $displaystyle A$ = C$\}.$

${\displaystyle A}$ ${\displaystyle \le }$ ${\displaystyle B}$ $displaystyle$A$\leq$B$}$은(는) 추상 추기경들의 선형 순서지만 세트에서는 그렇지 않다는 것을 알 수 있다.반사성은 명백하고 등가성만 증명된다.전적으로 표준적인 방법으로 ZFC와 NFU에서 증명할 수 있는 슈뢰더-베른슈타인 정리는 다음을 확립한다.

• $\displaystyle A \leq B \leq B \leq A \rightarrow A = B }$

(이것은 추기경들에 대칭성을 확립한다)

• $\displaystyle A \leq B \vee B \leq A }$

선택이라는 공리에서 어느 이론이든 표준적인 방법으로 따르다.

유한 집합 및 자연수

자연수는 유한 서수 또는 유한 추기경으로 간주할 수 있다.여기서 그들을 유한한 기수로 간주한다.ZFC와 NFU의 구현에 큰 차이가 나는 첫 번째 장소다.

The Axiom of Infinity of ZFC tells us that there is a set A which contains ${\displaystyle \emptyset }$ and contains ${\displaystyle y\cup \{y\}}$ for each ${\displaystyle y\in A}$. This set A is not uniquely determined (it can be made larger while preserving this closure property): the set N of natural numbers is

• ${\displaystyle \{x\in a\mid \forall B\, (\empt \in B\wedge \forall y\), (y\in B\wardge \forall y\, (y\in B\in)\rightarrow x\cup\}}}}\}}}}}}}}}}}}}\}}}}}}}}}}}}}}$

이는 빈 세트를 포함하고 "표시" 작업 y ${\displaystyle y\cup }$ { ${\displaystyle \{}$ { ${\displaystyle y}$ ${\displaystyle \}}$ ${\displaystyle y\mapsto y\cup \{y\}}}$에 따라 닫히는 모든 세트의 교차점이다$.$

ZFC에서 집합 $A{\displaystyle }$ ${\displaystyle$ $A$$}$은(는) ${\displaystyle n}$${\displaystyle \in }$ N $displaystyle n$= A $\}$과(와) 같은 n이 있는 경우에만 유한하다$$(더 나아가, 유한 A에 ${\displaystyle 대해}$ A {\$displaystyle A}$을 이 n과$$ 같이 정의한다${\displaystyle ).}$ (두 개의 고유한 자연수가 동일한 크기가 아님을 증명할 수 있다).

산술의 일반적인 연산은 반복적으로 정의할 수 있으며 자연수 그 자체가 정의되는 방식과 매우 유사한 형식으로 정의할 수 있다.For example, + (the addition operation on natural numbers) can be defined as the smallest set which contains ${\displaystyle ((x,\emptyset ),x)}$ for each natural number ${\displaystyle x}$ and contains ${\displaystyle ((x,y\cup \{y\}),z\cup \{z\})}$ whenever it contains ${\displaystyle (}$${\displaystyle (}$ ${\displaystyle x}$, ${\displaystyle y}$)${\displaystyle }$, z${\displaystyle }$) ${\displaystyle ((x,y),z$

In NFU, it is not obvious that this approach can be used, since the successor operation ${\displaystyle y\cup \{y\}}$ is unstratified and so the set N as defined above cannot be shown to exist in NFU (it is consistent for the set of finite von Neumann ordinals to exist in NFU, but this strengthens the theory, as the existence of this 집합은 카운팅의 공리(아래 또는 새로운 기초 기사 참조)를 의미한다.

실제로 자연수의 가장 오래된 설정-이론적 정의인 자연수의 표준 정의는 등분성 하의 유한 집합의 동등성 등급이다.본질적으로 동일한 정의가 NFU에 적합하다(이 정의는 통상적인 정의는 아니지만 결과는 동일하다): 유한 집합의 집합인 Fin을 정의한다.

${\displaystyle \{A\mid \f\,(\empt \in F\wedge \f\f\forall x,y\),(x\in F\rightarrow x\cup \{y\}\in F)\}}}}$

For any set ${\displaystyle A\in Fin}$, define ${\displaystyle A }$ as ${\displaystyle \{B\mid A\sim B\}}$. Define N as the set ${\displaystyle \{ A \mid A\in Fin\}}$.

The Axiom of Infinity of NFU can be expressed as ${\displaystyle V\not \in Fin}$: this is enough to establish that each natural number has a nonempty successor (the successor of ${\displaystyle A }$ being ${\displaystyle A\cup \{x\} }$ for any ${\displaystyle x\not \in A}$) which산술의 피아노 공리가 만족한다는 것을 보여주는 어려운 부분이다.

산술 연산은 위에서 주어진 방식과 유사한 방식으로 정의할 수 있다(지금 주어진 후계자 정의를 사용).그것들은 또한 자연적으로 설정된 이론적인 방법으로 정의될 수 있다: A와 B가 분리된 유한 집합인 경우, A + B를 ${\displaystyle A}$ ${\displaystyle \cup }$ ${\displaystyle B}$로 정의하라$.$ $displaystyle A\cup$B$}.$ 보다 공식적으로, N에서 m과 n에 대해 m+n을 정의하라.

${\displaystyle \{A\mid \exists B,C\,(B\in m\wedge C\inn\wedge C\cap=\emptset \wedge A=B\cup C)\}}}$

(그러나 이러한 정의 스타일은 ZFC 숫자도 가능하지만, 좀 더 회로적이다: NFU 정의의 형태는 정해진 조작을 촉진하는 반면, ZFC 정의의 형태는 재귀적 정의를 촉진하지만, 어느 하나의 이론도 두 정의 스타일을 지지한다.)

그 두 구현은 상당히 다르다.ZFC에서는 각 유한 카디널리티(등가 등급 자체가 너무 커서 세트가 되지 않음)의 대표자를 선택한다. NFU에서는 등가 등급 자체가 집합이므로, 물체가 추기경을 위해 서야 하는 명백한 선택이다.그러나 두 이론의 산술은 같다: 동일한 추상화가 이 피상적으로 다른 두 가지 접근법에 의해 구현된다.

Equivalence relations and partitions

A general technique for implementing abstractions in set theory is the use of equivalence classes. If an equivalence relation R tells us that elements of its field A are alike in some particular respect, then for any set x, regard the set ${\displaystyle [x]_{R}=\{y\in A\mid xRy\}}$ as representing an abstraction from the set x respecting just those features (identify elements of A up to R).

For any set A, a set ${\displaystyle P}$ is a partition of A if all elements of P are nonempty, any two distinct elements of P are disjoint, and ${\displaystyle A=\bigcup P}$.

For every equivalence relation R with field A, ${\displaystyle \{[x]_{R}\mid x\in A\}}$ is a partition of A. Moreover, each partition P of A determines an equivalence relation ${\displaystyle \{(x,y)\mid \exists A\in P\,(x\in A\wedge y\in A)\}}$.

This technique has limitations in both ZFC and NFU. In ZFC, since the universe is not a set, it seems possible to abstract features only from elements of small domains. This can be circumvented using a trick due to Dana Scott: if R is an equivalence relation on the universe, define ${\displaystyle [x]_{R}}$ as the set of all y such that ${\displaystyle yRx}$ and the rank of y is less than or equal to the rank of any ${\displaystyle zRx}$. This works because the ranks are sets. Of course, there still may be a proper class of ${\displaystyle [x]_{R}}$'s. In NFU, the main difficulty is that ${\displaystyle [x]_{R}}$ is one type higher than x, so for example the "map" ${\displaystyle x\mapsto [x]_{R}}$ is not in general a (set) function (though ${\displaystyle \{x\}\mapsto [x]_{R}}$ is a set). This can be circumvented by the use of the Axiom of Choice to select a representative from each equivalence class to replace ${\displaystyle [x]_{R}}$, which will be at the same type as x, or by choosing a canonical representative if there is a way to do this without invoking Choice (the use of representatives is hardly unknown in ZFC, either). In NFU, the use of equivalence class constructions to abstract properties of general sets is more common, as for example in the definitions of cardinal and ordinal number below.

Ordinal numbers

Two well-orderings ${\displaystyle W_{1}}$ and ${\displaystyle W_{2}}$ are similar and write ${\displaystyle W_{1}\sim W_{2}}$ just in case there is a bijection f from the field of ${\displaystyle W_{1}}$ to the field of ${\displaystyle W_{2}}$ such that ${\displaystyle xW_{1}y\leftrightarrow f(x)W_{2}f(y)}$ for all x and y.

Similarity is shown to be an equivalence relation in much the same way that equinumerousness was shown to be an equivalence relation above.

In New Foundations (NFU), the order type of a well-ordering W is the set of all well-orderings which are similar to W. The set of ordinal numbers is the set of all order types of well-orderings.

This does not work in ZFC, because the equivalence classes are too large. It would be formally possible to use Scott's trick to define the ordinals in essentially the same way, but a device of von Neumann is more commonly used.

For any partial order ${\displaystyle \leq }$, the corresponding strict partial order < is defined as ${\displaystyle \{(x,y)\mid x\leq y\wedge x\neq y\}}$. Strict linear orders and strict well-orderings are defined similarly.

A set A is said to be transitive if ${\displaystyle \bigcup A\subseteq A}$: each element of an element of A is also an element of A. A (von Neumann) ordinal is a transitive set on which membership is a strict well-ordering.

In ZFC, the order type of a well-ordering W is then defined as the unique von Neumann ordinal which is equinumerous with the field of W and membership on which is isomorphic to the strict well-ordering associated with W. (the equinumerousness condition distinguishes between well-orderings with fields of size 0 and 1, whose associated strict well-orderings are indistinguishable).

In ZFC there cannot be a set of all ordinals. In fact, the von Neumann ordinals are an inconsistent totality in any set theory: it can be shown with modest set theoretical assumptions that every element of a von Neumann ordinal is a von Neumann ordinal and the von Neumann ordinals are strictly well-ordered by membership. It follows that the class of von Neumann ordinals would be a von Neumann ordinal if it were a set: but it would then be an element of itself, which contradicts the fact that membership is a strict well-ordering of the von Neumann ordinals.

The existence of order types for all well-orderings is not a theorem of Zermelo set theory: it requires the Axiom of replacement. Even Scott's trick cannot be used in Zermelo set theory without an additional assumption (such as the assumption that every set belongs to a rank which is a set, which does not essentially strengthen Zermelo set theory but is not a theorem of that theory).

In NFU, the collection of all ordinals is a set by stratified comprehension. The Burali-Forti paradox is evaded in an unexpected way. There is a natural order on the ordinals defined by ${\displaystyle \alpha \leq \beta }$ if and only if some (and so any) ${\displaystyle W_{1}\in \alpha }$ is similar to an initial segment of some (and so any) ${\displaystyle W_{2}\in \beta }$. Further, it can be shown that this natural order is a well-ordering of the ordinals and so must have an order type ${\displaystyle \Omega }$. It would seem that the order type of the ordinals less than ${\displaystyle \Omega }$ with the natural order would be ${\displaystyle \Omega }$, contradicting the fact that ${\displaystyle \Omega }$ is the order type of the entire natural order on the ordinals (and so not of any of its proper initial segments). But this relies on one's intuition (correct in ZFC) that the order type of the natural order on the ordinals less than ${\displaystyle \alpha }$ is ${\displaystyle \alpha }$ for any ordinal ${\displaystyle \alpha }$. This assertion is unstratified, because the type of the second ${\displaystyle \alpha }$ is four higher than the type of the first (two higher if a type level pair is used). The assertion which is true and provable in NFU is that the order type of the natural order on the ordinals less than ${\displaystyle \alpha }$ is ${\displaystyle T^{4}(\alpha )}$ for any ordinal ${\displaystyle \alpha }$, where ${\displaystyle T(\alpha )}$ is the order type of ${\displaystyle W^{\iota }=\{(\{x\},\{y\})\mid xWy\}}$ for any ${\displaystyle W\in \alpha }$ (it is easy to show that this does not depend on the choice of W; note that T raises type by one). Thus the order type of the ordinals less than ${\displaystyle \Omega }$ with the natural order is ${\displaystyle T^{4}(\Omega )}$, and ${\displaystyle T^{4}(\Omega )<\Omega }$. All uses of ${\displaystyle T^{4}}$ here can be replaced with ${\displaystyle T^{2}}$ if a type-level pair is used.

This shows that the T operation is nontrivial, which has a number of consequences. It follows immediately that the singleton map ${\displaystyle x\mapsto \{x\}}$ is not a set, as otherwise restrictions of this map would establish the similarity of W and ${\displaystyle W^{\iota }}$ for any well-ordering W. T is (externally) bijective and order-preserving. Because of this, the fact ${\displaystyle T^{4}(\Omega )<\Omega }$ establishes that ${\displaystyle \Omega >T(\Omega )>T^{2}(\Omega )\ldots }$ is a "descending sequence" in the ordinals which cannot be a set.

Ordinals fixed by T are called Cantorian ordinals, and ordinals which dominate only cantorian ordinals (which are easily shown to be cantorian themselves) are said to be strongly cantorian. There can be no set of cantorian ordinals or set of strongly cantorian ordinals.

Digression: von Neumann ordinals in NFU

It is possible to reason about von Neumann ordinals in NFU. Recall that a von Neumann ordinal is a transitive set A such that the restriction of membership to A is a strict well-ordering. This is quite a strong condition in the NFU context, since the membership relation involves a difference of type. A von Neumann ordinal A is not an ordinal in the sense of NFU, but ${\displaystyle \in \lceil A}$ belongs to an ordinal ${\displaystyle \alpha }$ which may be termed the order type of (membership on) A. It is easy to show that the order type of a von Neumann ordinal A is cantorian: for any well-ordering W of order type ${\displaystyle \alpha }$, the induced well-ordering of initial segments of W by inclusion has order type ${\displaystyle T(\alpha )}$ (it is one type higher, thus the application of T): but the order types of the well-ordering of a von Neumann ordinal A by membership and the well-ordering of its initial segments by inclusion are clearly the same because the two well-orderings are actually the same relation, so the order type of A is fixed under T. Moreover, the same argument applies to any smaller ordinal (which will be the order type of an initial segment of A, also a von Neumann ordinal) so the order type of any von Neumann ordinal is strongly cantorian.

The only von Neumann ordinals which can be shown to exist in NFU without additional assumptions are the concrete finite ones. However, the application of a permutation method can convert any model of NFU to a model in which every strongly cantorian ordinal is the order type of a von Neumann ordinal. This suggests that the concept "strongly cantorian ordinal of NFU" might be a better analogue to "ordinal of ZFC" than is the apparent analogue "ordinal of NFU".

Cardinal numbers

Cardinal numbers are defined in NFU in a way which generalizes the definition of natural number: for any set A, ${\displaystyle A \,{\overset {\mathrm {def} }{=}}\left\{B\mid B\sim A\right\}}$.

In ZFC, these equivalence classes are too large as usual. Scott's trick could be used (and indeed is used in ZF), ${\displaystyle A }$ is usually defined as the smallest order type (here a von Neumann ordinal) of a well-ordering of A (that every set can be well-ordered follows from the Axiom of Choice in the usual way in both theories).

The natural order on cardinal numbers is seen to be a well-ordering: that it is reflexive, antisymmetric (on abstract cardinals, which are now available) and transitive has been shown above. That it is a linear order follows from the Axiom of Choice: well-order two sets and an initial segment of one well-ordering will be isomorphic to the other, so one set will have cardinality smaller than that of the other. That it is a well-ordering follows from the Axiom of Choice in a similar way.

With each infinite cardinal, many order types are associated for the usual reasons (in either set theory).

Cantor's theorem shows (in both theories) that there are nontrivial distinctions between infinite cardinal numbers. In ZFC, one proves ${\displaystyle A < P(A) .}$ In NFU, the usual form of Cantor's theorem is false (consider the case A=V), but Cantor's theorem is an ill-typed statement. The correct form of the theorem in NFU is ${\displaystyle P_{1}(A) < P(A) }$, where ${\displaystyle P_{1}(A)}$ is the set of one-element subsets of A. ${\displaystyle P_{1}(V) < P(V) }$ shows that there are "fewer" singletons than sets (the obvious bijection ${\displaystyle x\mapsto \{x\}}$ from ${\displaystyle P_{1}(V)}$ to V has already been seen not to be a set). It is actually provable in NFU + Choice that ${\displaystyle P_{1}(V) < P(V) \ll V }$ (where ${\displaystyle \ll }$ signals the existence of many intervening cardinals; there are many, many urelements!). Define a type-raising T operation on cardinals analogous to the T operation on ordinals: ${\displaystyle T( A )= P_{1}(A) }$; this is an external endomorphism of the cardinals just as the T operation on ordinals is an external endomorphism of the ordinals.

A set A is said to be cantorian just in case ${\displaystyle A = P_{1}(A) =T( A )}$; the cardinal ${\displaystyle A }$ is also said to be a cantorian cardinal. A set A is said to be strongly cantorian (and its cardinal to be strongly cantorian as well) just in case the restriction of the singleton map to A (${\displaystyle (x\mapsto \{x\})\lceil A}$) is a set. Well-orderings of strongly cantorian sets are always strongly cantorian ordinals; this is not always true of well-orderings of cantorian sets (though the shortest well-ordering of a cantorian set will be cantorian). A cantorian set is a set which satisfies the usual form of Cantor's theorem.

The operations of cardinal arithmetic are defined in a set-theoretically motivated way in both theories. ${\displaystyle A + B =\{C\cup D\mid C\sim A\wedge D\sim B\wedge C\cap D=\emptyset \}}$. One would like to define ${\displaystyle A \cdot B }$ as ${\displaystyle A\times B }$, and one does this in ZFC, but there is an obstruction in NFU when using the Kuratowski pair: one defines ${\displaystyle A \cdot B }$ as ${\displaystyle T^{-2}( A\times B )}$ because of the type displacement of 2 between the pair and its projections, which implies a type displacement of two between a cartesian product and its factors. It is straightforward to prove that the product always exists (but requires attention because the inverse of T is not total).

Defining the exponential operation on cardinals requires T in an essential way: if ${\displaystyle B^{A}}$ was defined as the collection of functions from A to B, this is three types higher than A or B, so it is reasonable to define ${\displaystyle B ^{ A }}$ as ${\displaystyle T^{-3}( B^{A} )}$ so that it is the same type as A or B (${\displaystyle T^{-1}}$ replaces ${\displaystyle T^{-3}}$ with type-level pairs). An effect of this is that the exponential operation is partial: for example, ${\displaystyle 2^{ V }}$ is undefined. In ZFC one defines ${\displaystyle B ^{ A }}$ as ${\displaystyle B^{A} }$ without difficulty.

The exponential operation is total and behaves exactly as expected on cantorian cardinals, since T fixes such cardinals and it is easy to show that a function space between cantorian sets is cantorian (as are power sets, cartesian products, and other usual type constructors). This offers further encouragement to the view that the "standard" cardinalities in NFU are the cantorian (indeed, the strongly cantorian) cardinalities, just as the "standard" ordinals seem to be the strongly cantorian ordinals.

Now the usual theorems of cardinal arithmetic with the axiom of choice can be proved, including ${\displaystyle \kappa \cdot \kappa =\kappa }$. From the case ${\displaystyle V \cdot V = V }$ the existence of a type level ordered pair can be derived: ${\displaystyle V \cdot V =T^{-2}( V\times V )}$ is equal to ${\displaystyle V }$ just in case ${\displaystyle V\times V =T^{2}( V )= P_{1}^{2}(V) }$, which would be witnessed by a one-to-one correspondence between Kuratowski pairs ${\displaystyle (a,b)}$ and double singletons ${\displaystyle \{\{c\}\}}$: redefine ${\displaystyle (a,b)}$ as the c such that ${\displaystyle \{\{c\}\}}$ is associated with the Kuratowski ${\displaystyle (a,b)}$: this is a type-level notion of ordered pair.

The Axiom of Counting and subversion of stratification

So there are two different implementations of the natural numbers in NFU (though they are the same in ZFC): finite ordinals and finite cardinals. Each of these supports a T operation in NFU (basically the same operation). It is easy to prove that ${\displaystyle T(n)}$ is a natural number if n is a natural number in NFU + Infinity + Choice (and so ${\displaystyle N }$ and the first infinite ordinal ${\displaystyle \omega }$ are cantorian) but it is not possible to prove in this theory that ${\displaystyle T(n)=n}$. However, common sense indicates that this should be true, and so it can be adopted as an axiom:

• Rosser's Axiom of Counting: For each natural number n, ${\displaystyle T(n)=n}$.

One natural consequence of this axiom (and indeed its original formulation) is

• ${\displaystyle \{1,\ldots ,n\} =n}$ for each natural number n.

All that can be proved in NFU without Counting is ${\displaystyle \{1,\ldots ,n\} =T^{2}(n)}$.

A consequence of Counting is that N is a strongly cantorian set (again, this is an equivalent assertion).

Properties of strongly cantorian sets

The type of any variable restricted to a strongly cantorian set A can be raised or lowered as desired by replacing references to ${\displaystyle a\in A}$ with references to ${\displaystyle \bigcup f(a)}$ (type of a raised; this presupposes that it is known that a is a set; otherwise one must say "the element of ${\displaystyle f(a)}$" to get this effect) or ${\displaystyle f^{-1}(\{a\})}$ (type of a lowered) where ${\displaystyle f(a)=\{a\}}$ for all ${\displaystyle a\in A}$, so it is not necessary to assign types to such variables for purposes of stratification.

Any subset of a strongly cantorian set is strongly cantorian. The power set of a strongly cantorian set is strongly cantorian. The cartesian product of two strongly cantorian sets is strongly cantorian.

Introducing the Axiom of Counting means that types need not be assigned to variables restricted to N or to P(N), R (the set of reals) or indeed any set ever considered in classical mathematics outside of set theory.

There are no analogous phenomena in ZFC. See the main New Foundations article for stronger axioms that can be adjoined to NFU to enforce "standard" behavior of familiar mathematical objects.

Familiar number systems: positive rationals, magnitudes, and reals

Represent positive fractions as pairs of positive natural numbers (0 is excluded): ${\displaystyle {\frac {p}{q}}}$ is represented by the pair ${\displaystyle (p,q)}$. To make ${\displaystyle {\frac {p}{q}}={\frac {r}{s}}\leftrightarrow ps=qr}$, introduce the relation ${\displaystyle \sim }$ defined by ${\displaystyle (p,q)\sim (r,s)\leftrightarrow ps=qr}$. It is provable that this is an equivalence relation: define positive rational numbers as equivalence classes of pairs of positive natural numbers under this relation. Arithmetic operations on positive rational numbers and the order relation on positive rationals are defined just as in elementary school and proved (with some effort) to have the expected properties.

Represent magnitudes (positive reals) as nonempty proper initial segments of the positive rationals with no largest element. The operations of addition and multiplication on magnitudes are implemented by elementwise addition of the positive rational elements of the magnitudes. Order is implemented as set inclusion.

Represent real numbers as differences ${\displaystyle m-n}$ of magnitudes: formally speaking, a real number is an equivalence class of pairs ${\displaystyle (m,n)}$ of magnitudes under the equivalence relation ${\displaystyle \sim }$ defined by ${\displaystyle (m,n)\sim (r,s)\leftrightarrow m+s=n+r}$. The operations of addition and multiplication on real numbers are defined just as one would expect from the algebraic rules for adding and multiplying differences. The treatment of order is also as in elementary algebra.

This is the briefest sketch of the constructions. Note that the constructions are exactly the same in ZFC and in NFU, except for the difference in the constructions of the natural numbers: since all variables are restricted to strongly cantorian sets, there is no need to worry about stratification restrictions. Without the Axiom of Counting, it might be necessary to introduce some applications of T in a full discussion of these constructions.

Operations on indexed families of sets

In this class of constructions it appears that ZFC has an advantage over NFU: though the constructions are clearly feasible in NFU, they are more complicated than in ZFC for reasons having to do with stratification.

Throughout this section assume a type-level ordered pair. Define ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ as ${\displaystyle (x_{1},(x_{2},\ldots ,x_{n}))}$. The definition of the general n-tuple using the Kuratowski pair is trickier, as one needs to keep the types of all the projections the same, and the type displacement between the n-tuple and its projections increases as n increases. Here, the n-tuple has the same type as each of its projections.

General cartesian products are defined similarly: ${\displaystyle A_{1}\times A_{2}\times \ldots \times A_{n}=A_{1}\times (A_{2}\times \ldots \times A_{n})}$

The definitions are the same in ZFC but without any worries about stratification (the grouping given here is opposite to that more usually used, but this is easily corrected for).

Now consider the infinite cartesian product ${\displaystyle \Pi _{i\in I}A_{i}}$. In ZFC, this is defined as the set of all functions f with domain I such that ${\displaystyle f(i)\in A_{i}}$ (where A is implicitly understood as a function taking each i to ${\displaystyle A_{i}}$).

In NFU, this is requires attention to type. Given a set I and set valued function A whose value at ${\displaystyle \{i\}}$ in ${\displaystyle P_{1}(I)}$ is written ${\displaystyle A_{i}}$, Define ${\displaystyle \Pi _{i\in I}A_{i}}$ as the set of all functions f with domain I such that ${\displaystyle f(i)\in A_{i}}$: notice that ${\displaystyle f(i)\in A_{i}=A(\{i\})}$ is stratified because of our convention that A is a function with values at singletons of the indices. Note that the very largest families of sets (which cannot be indexed by sets of singletons) will not have cartesian products under this definition. Note further that the sets ${\displaystyle A_{i}}$ are at the same type as the index set I (since one type higher than its elements); the product, as a set of functions with domain I (so at the same type as I) is one type higher (assuming a type-level ordered pair).

Now consider the product ${\displaystyle \Pi _{i\in I} A_{i} }$ of the cardinals of these sets. The cardinality ${\displaystyle \Pi _{i\in I}A_{i}}$ is one type higher than the cardinals ${\displaystyle A_{i} }$, so the correct definition of the infinite product of cardinals is ${\displaystyle T^{-1}( \Pi _{i\in I}A_{i} )}$ (because the inverse of T is not total, it is possible that this may not exist).

Repeat this for disjoint unions of families of sets and sums of families of cardinals. Again, let A be a set-valued function with domain ${\displaystyle P_{1}(I)}$: write ${\displaystyle A_{i}}$ for ${\displaystyle A(\{i\})}$. The disjoint union ${\displaystyle \Sigma _{i\in I}A_{i}}$ is the set ${\displaystyle \{(i,a)\mid a\in A_{i}\}}$. This set is at the same type as the sets ${\displaystyle A_{i}}$.

The correct definition of the sum ${\displaystyle \Sigma _{i\in I} A_{i} }$ is thus ${\displaystyle \Sigma _{i\in I}A_{i} }$, since there is no type displacement.

It is possible to extend these definitions to handle index sets which are not sets of singletons, but this introduces an additional type level and is not needed for most purposes.

In ZFC, define the disjoint union ${\displaystyle \Sigma _{i\in I}A_{i}}$ as ${\displaystyle \{(i,a)\mid a\in A_{i}\}}$, where ${\displaystyle A_{i}}$ abbreviates ${\displaystyle A(i)}$.

Permutation methods can be used to show relative consistency with NFU of the assertion that for every strongly cantorian set A there is a set I of the same size whose elements are self-singletons: ${\displaystyle i=\{i\}}$ for each i in I.

The cumulative hierarchy

In ZFC, define the cumulative hierarchy as the ordinal-indexed sequence of sets satisfying the following conditions: ${\displaystyle V_{0}=\emptyset }$; ${\displaystyle V_{\alpha +1}=P(V_{\alpha })}$; ${\displaystyle V_{\lambda }=\bigcup \{V_{\beta }\mid \beta <\lambda \}}$ for limit ordinals ${\displaystyle \lambda }$. This is an example of a construction by transfinite recursion. The rank of a set A is said to be ${\displaystyle \alpha }$ if and only if ${\displaystyle A\in V_{\alpha +1}-V_{\alpha }}$. The existence of the ranks as sets depends on the axiom of replacement at each limit step (the hierarchy cannot be constructed in Zermelo set theory); by the axiom of foundation, every set belongs to some rank.

The cardinal ${\displaystyle P(V_{\omega +\alpha }) }$ is called ${\displaystyle \beth _{\alpha }}$.

This construction cannot be carried out in NFU because the power set operation is not a set function in NFU (${\displaystyle P(A)}$ is one type higher than A for purposes of stratification).

The sequence of cardinals ${\displaystyle \beth _{\alpha }}$ can be implemented in NFU. Recall that ${\displaystyle 2^{ A }}$ is defined as ${\displaystyle T^{-1}( \{0,1\}^{A} )}$, where ${\displaystyle \{0,1\}}$ is a convenient set of size 2, and ${\displaystyle \{0,1\}^{A} = P(A) }$. Let ${\displaystyle \beth }$ be the smallest set of cardinals which contains ${\displaystyle N }$ (the cardinality of the set of natural numbers), contains the cardinal ${\displaystyle 2^{ A }}$ whenever it contains ${\displaystyle A }$, and which is closed under suprema of sets of cardinals.

A convention for ordinal indexing of any well-ordering ${\displaystyle W_{\alpha }}$ is defined as the element x of the field of ${\displaystyle W}$ such that the order type of the restriction of ${\displaystyle W}$ to ${\displaystyle \{y\mid yWx\}}$ is ${\displaystyle \alpha }$; then define ${\displaystyle \beth _{\alpha }}$ as the element with index ${\displaystyle \alpha }$ in the natural order on the elements of ${\displaystyle \beth }$. The cardinal ${\displaystyle \aleph _{\alpha }}$ is the element with index ${\displaystyle \alpha }$ in the natural order on all infinite cardinals (which is a well-ordering, see above). Note that ${\displaystyle \aleph _{0}= N }$ follows immediately from this definition. In all these constructions, notice that the type of the index ${\displaystyle \alpha }$ is two higher (with type-level ordered pair) than the type of ${\displaystyle W_{\alpha }}$.

Each set A of ZFC has a transitive closure ${\displaystyle TC(A)}$ (the intersection of all transitive sets which contains A). By the axiom of foundation, the restriction of the membership relation to the transitive closure of A is a well-founded relation. The relation ${\displaystyle \in \lceil TC(A)}$ is either empty or has A as its top element, so this relation is a set picture. It can be proved in ZFC that every set picture is isomorphic to some ${\displaystyle \in \lceil TC(A)}$.

This suggests that (an initial segment of) the cumulative hierarchy can be studied by considering the isomorphism classes of set pictures. These isomorphism classes are sets and make up a set in NFU. There is a natural set relation analogous to membership on isomorphism classes of set pictures: if ${\displaystyle x}$ is a set picture, write ${\displaystyle [x]}$ for its isomorphism class and define ${\displaystyle [x]E[y]}$ as holding if ${\displaystyle [x]}$ is the isomorphism class of the restriction of y to the downward closure of one of the elements of the preimage under y of the top element of y. The relation E is a set relation, and it is straightforward to prove that it is well-founded and extensional. If the definition of E is confusing, it can be deduced from the observation that it is induced by precisely the relationship which holds between the set picture associated with A and the set picture associated with B when ${\displaystyle A\in B}$ in the usual set theory.

There is a T operation on isomorphism classes of set pictures analogous to the T operation on ordinals: if x is a set picture, so is ${\displaystyle x^{\iota }=\{(\{a\},\{b\})\mid (a,b)\in x\}}$. Define ${\displaystyle T([x])}$ as ${\displaystyle [x^{\iota }]}$. It is easy to see that ${\displaystyle [x]E[y]\leftrightarrow T([x])=T([y])}$.

An axiom of extensionality for this simulated set theory follows from E's extensionality. From its well-foundedness follows an axiom of foundation. There remains the question of what comprehension axiom E may have. Consider any collection of set pictures ${\displaystyle \{x^{\iota }\mid x\in S\}}$ (collection of set pictures whose fields are made up entirely of singletons). Since each ${\displaystyle x^{\iota }}$ is one type higher than x (using a type-level ordered pair), replacing each element ${\displaystyle \{a\}}$ of the field of each ${\displaystyle x^{\iota }}$ in the collection with ${\displaystyle (x,\{a\})}$ results in a collection of set pictures isomorphic to the original collection but with their fields disjoint. The union of these set pictures with a new top element yields a set picture whose isomorphism type will have as its preimages under E exactly the elements of the original collection. That is, for any collection of isomorphism types ${\displaystyle [x^{\iota }]=T([x])}$, there is an isomorphism type ${\displaystyle [y]}$ whose preimage under E is exactly this collection.

In particular, there will be an isomorphism type [v] whose preimage under E is the collection of all T[x]'s (including T[v]). Since T[v] E v and E is well-founded, ${\displaystyle T[v]\neq v}$. This resembles the resolution of the Burali–Forti paradox discussed above and in the New Foundations article, and is in fact the local resolution of Mirimanoff's paradox of the set of all well-founded sets.

There are ranks of isomorphism classes of set pictures just as there are ranks of sets in the usual set theory. For any collection of set pictures A, define S(A) as the set of all isomorphism classes of set pictures whose preimage under E is a subset of A; call A a "complete" set if every subset of A is a preimage under E. The collection of "ranks" is the smallest collection containing the empty set and closed under the S operation (which is a kind of power set construction) and under unions of its subcollections. It is straightforward to prove (much as in the usual set theory) that the ranks are well-ordered by inclusion, and so the ranks have an index in this well-order: refer to the rank with index ${\displaystyle \alpha }$ as ${\displaystyle R_{\alpha }}$. It is provable that ${\displaystyle R_{\alpha } =\beth _{\alpha }}$ for complete ranks ${\displaystyle R_{\alpha }}$. The union of the complete ranks (which will be the first incomplete rank) with the relation E looks like an initial segment of the universe of Zermelo-style set theory (not necessarily like the full universe of ZFC because it may not be large enough). It is provable that if ${\displaystyle R_{\alpha }}$ is the first incomplete rank, then ${\displaystyle R_{T(\alpha )}}$ is a complete rank and thus ${\displaystyle T(\alpha )<\alpha }$. So there is a "rank of the cumulative hierarchy" with an "external automorphism" T moving the rank downward, exactly the condition on a nonstandard model of a rank in the cumulative hierarchy under which a model of NFU is constructed in the New Foundations article. There are technical details to verify, but there is an interpretation not only of a fragment of ZFC but of NFU itself in this structure, with ${\displaystyle [x]\in _{NFU}[y]}$ defined as ${\displaystyle T([x])E[y]\wedge [y]\in R_{T(\alpha )+1}}$: this "relation" ${\displaystyle E_{NFU}}$ is not a set relation but has the same type displacement between its arguments as the usual membership relation ${\displaystyle \in }$.

So there is a natural construction inside NFU of the cumulative hierarchy of sets which internalizes the natural construction of a model of NFU in Zermelo-style set theory.

Under the Axiom of Cantorian Sets described in the New Foundations article, the strongly cantorian part of the set of isomorphism classes of set pictures with the E relation as membership becomes a (proper class) model of ZFC (in which there are n-Mahlo cardinals for each n; this extension of NFU is strictly stronger than ZFC). This is a proper class model because the strongly cantorian isomorphism classes do not make up a set.

Permutation methods can be used to create from any model of NFU a model in which every strongly cantorian isomorphism type of set pictures is actually realized as the restriction of the true membership relation to the transitive closure of a set.

See also

• Axiomatic set theory

References

• Keith Devlin, 1994. The Joy of Sets, 2nd ed. Springer-Verlag.
• Holmes, Randall, 1998. Elementary Set Theory with a Universal Set. Academia-Bruylant. The publisher has graciously consented to permit diffusion of this introduction to NFU via the web. Copyright is reserved.
• Potter, Michael, 2004. Set Theory and its Philosophy, 2nd ed. Oxford Univ. Press.
• Suppes, Patrick, 1972. Axiomatic Set Theory. Dover.
• Tourlakis, George, 2003. Lectures in Logic and Set Theory, Vol. 2. Cambridge Univ. Press.

External links

• Metamath: A web site devoted to an ongoing derivation of mathematics from the axioms of ZFC and first-order logic.
• Stanford Encyclopedia of Philosophy:
  • Quine's New Foundations—by Thomas Forster.
  • Alternative axiomatic set theories—by Randall Holmes.
• Randall Holmes: New Foundations Home Page