I realized that i have used argument below many times before and I'm not sure if it is true.
Let $A=\{n\in \omega|\Phi(n)\}$.
Then $A\preceq \aleph_0$.
(i)Suppose $A$ is dedekind-infinite and find a contradiction (Dedekind-infinite here refers to a set when there exists a injective function $f:\omega_0 \rightarrow A$)
(ii)Thus $A\prec \aleph_0$.
Here, after the step(ii), could $A$ possibly be an infinite-dedekind finite set? That is $A$ may not have a maximal element? (Not a von-neumann ordinal?)