设数论谓词 Q(x,y,z,v)Q(x,y,z,v)Q(x,y,z,v) 定义为 Q(x,y,z,v)≡p(⟨x,y,z⟩) ∣ v, Q(x, y, z, v) \equiv p(\langle x,y,z\rangle) ~|~ v, Q(x,y,z,v)≡p(⟨x,y,z⟩) ∣ v, 其中，p(n)p(n)p(n) 表示第 nnn 个素数，⟨x,y,z⟩\langle x,y,z\rangle⟨x,y,z⟩ 是 x,y,zx,y,zx,y,z 的 Godel 编码。证明：Q(x,y,z,v)Q(x,y,z,v)Q(x,y,z,v) 是初等的。
∵⟨x,y,z⟩=2x⋅3y⋅5z∈EF\because \langle x,y,z\rangle= 2^x \cdot 3^y \cdot 5^z \in \mathcal{EF} ∵⟨x,y,z⟩=2x⋅3y⋅5z∈EF
又 Q(x,y,z,v)Q(x,y,z,v)Q(x,y,z,v) 的特征函数为 N2rs(v,p(⟨x,y,z⟩))N^2rs(v, p(\langle x,y,z\rangle))N2rs(v,p(⟨x,y,z⟩))
∴Q∈EF\therefore Q \in \mathcal{EF}∴Q∈EF