如何建立一個從N到{?,{?},{{?}},{{{?}}}...}的雙射？

01-04

顯然是存在雙射的，但能否用嚴格的數學語言將它表示出來？

首先，我們要定義{?,{?},{{?}},{{{?}}},...}是什麼。

設這個集合為M，用邏輯語言描述是 $exists M(emptyset in Mwedge forall x(xin M ightarrow {x}in M))$ 。

然而這一定是個集合嗎？不一定，有可能是真類(proper class)。

下面來證明M是一個集合：

遞歸定義類函數(class function)：

$F(0)=emptyset$

$F(n+1)={F(n)}$

則 $M=ran(F)$

根據替換公理模式，M=F[N]是一個集合。

這樣F就是一個函數了。下面證明它是雙射：

因為M是F的像，顯然滿射；根據基礎公理，沒有集合屬於自身，單射也是顯然的。

所以F就是所求的雙射。

幾點說明：

1. 這裡一開始定義F是類函數而不是函數，這是因為函數本質上是序對的集合。如果F是函數，那麼它的值域就是集合M，這就循環論證了。

2. F是否可以遞歸定義？一開始我是拒絕的，因為我起初想到的是自然數上的遞歸定理，這樣F必須是個函數，就又陷入了1里的死循環。但是根據超窮遞歸定理，F即使不是函數，也是可以遞歸定義的，只要F定義域是所有序數的類就行（真子類當然也行）。所以可以遞歸定義。

Method1:

let S={?,{?},{?,{?}},{?,{?},{{?}}}...}, N set of natural numbers

f: N--&>S

let f(0)=?，f(1)={?}, f(2)={?,{?}}

f(n)=f(n-1)∪{f(n-1)f(n-2)} for all n larger than or equals to 3

f(n) have n elements inside

It is obvious that it is injective and surjective, hence bijective.

Method2:

Let g: N--&>{?,{?},{{?}}...}

g(0)=?, g(n)={g(n-1)}, it is easy to see g(n)={{{{...?...}}}} (n left braces)

g is a bijection

h:N--&>S

h(0)=?

h(n)= g(1)∪g(2)...∪g(n)=f(n)

hence it is a bijection.

這個描述讓我想起自然數的另一個定義

（比較傳統的是Peano"s Axioms）

Definition:Natural Numbers

Let ω denote the minimal infinite successor set.
The natural numbers can be defined as the elements of ω.
Following Definition 2 of ω, this amounts to defining the natural numbers as the finite ordinals.
In terms of the empty set ? and successor sets, we thus define:
0:=?={}
1:=0+=0∪{0}={0}
2:=1+=1∪{1}={0,1}

3:=2+=2∪{2}={0,1,2}
?

Or in other words, define

0 :=?

1:= 0∪{0}=?∪{?}={?, {?}}

2:= 1∪{1}={?, {?}}∪{{?, {?}}}={?,{?},{?,{?}}}

Hence,

N+1 :=N∪{N}={?,{?},{?,{?}},{?,{?},{?,{?}}}...}(the last elements have N elements inside)∪{{?,{?},{?,{?}},{?,{?},{?,{?}}}...}={?,{?},{?,{?}},{?,{?},{?,{?}}}...}(the last elements have N+1 elements inside)

和題主說的很像吧&>&<

PS：看了看其他答主的答案，覺得自己too young too simple，實在是太不夠了。

以上

//多圖預警

//重要的事情不說三遍

//流量黨準備好，Wi-Fi隨意

我可能不會給出一個和題主相似的對自然數的雙射構造，但題主也許可以借鑒一下這個思路去構造。

由於我是個鶸，我還在自學latex中。於是我拍一下手寫的筆記給你，以供參考（英文預警）。

以上，希望有一些幫助....我想我是不是要匿了....畢竟悶聲發大財才是墜吼的！

分為兩步。

第一步用嚴格的數學語言描述{?,{?},{{?}},{{{?}}}...}。

第二步，建立雙射。

顯然第一步用遞歸的方式定義最自然，又自然數可以歸納，那遞歸定義的雙射就非常自然得到了。

本來覺得這是個trivial的問題，用自然數上的遞歸定理把這個集合構造出來就很簡單了，但是看了Ruoz的回答之後，發現這個問題並不是那麼的trivial，在ZF裡面把這個集合構造出來還是要稍微想一想的。

記號說明：

$omega$ : 自然數集（我們假設自然數從0開始）

設 $(A,<)$ 是一個良序結構，對任意a∈A, seg a={x∈A|x&設F是一個函數，A是一個集合，則F|A表示F在A上的限制

-----------------------------------------

首先自然數上的遞歸定理是不能用的在這裡：

設有一個集合A以及A上的一個函數f以及一個A中的元素a，那麼存在唯一的一個函數F： $omega ightarrow A$ 使得F(0)=a, F(n+1)=f(F(n))。

我們可能會傾向於這樣定義一個F：

F(0)=?

F(n+1)={F(n)}

然而這是不行的，加括弧這個操作本身是所有集合的類上的一個（類）函數，要讓它成為函數得把它限制到某個集合上，而這個集合在這裡恰恰是我們想構造的那個集合（或者一個更大的集合）！也就是說想用遞歸定理的構造這個集合的前提就是這個集合已經被構造好了！

-------------------------------------------

那麼，有別的辦法嗎？想到良序集上的超窮遞歸只需要f是一個類函數就可以了，那麼試試超窮遞歸：

設(A,&<)是一個良序結構， $gamma$ 是一個只有兩個自由變元xy的公式使得對任意x存在唯一的y使得 $gamma(x,y)$ ，那麼存在唯一的一個定義域為A的函數F使得對任意a∈A， $gamma(F|mathrm{seg}a, F(a))$ 。

現在的主要任務就是把這個 $gamma$ 寫出來。我們要的是F(0)=?和F(n)={F(n-1)}(n&>=1)，現在的問題是怎麼用F|segn表示出{F(n-1)}。我們知道，自然數的任何非空有上界子集有唯一的最大元，於是如果f是定義在自然數的某個非空有上界的子集的函數，那麼可以構造一個定義在所有集合上的類函數 $alpha$ （即給ZF的語言定義擴張進一個函數符號 $alpha$ ）使得對所有那樣的函數我們有 $alpha(f)=f(n)$ ，其中n是f定義域的最大元。注意到F|segn就是定義在自然數的某個非空有上界的子集的函數，並且segn的最大元正是n-1(n&>=1)，於是 $alpha(F|mathrm{seg}n)=F(n-1)$ ，於是我們可以寫出如下的 $gamma$ :

if x is a function defined on a bounded nonempty subset of omega then y={ $alpha(x)$ };

otherwise y=emptyset

這樣用超窮遞歸得到F之後取它的值域就好了。證明雙射應該就是比較簡單的事情了。

（我們實際上證明了一個自然數遞歸定理的加強版，其中f可以是一個類函數。於是題主的問題還是trivial的，本質上也還是遞歸定義一下就好了，無非就是遞歸定理的證明非常非常非常麻煩。）

戈德門特的《代數學教程》裡面有講，法蘭西數學譯叢那套書里的