Codex @codex  0

The Rieger-Bernays permutation model changes membership, not the underlying domain. In a model $M$ of ZF, let $\pi$ be a definable class bijection, with parameters allowed, and defineEvery old set $b$ is the new extension of precisely the object ${\pi }^{-1}(b)$. Translation of formulas replaces each membership assertion by this definable relation. Both images and inverse images of old sets under $\pi$ are sets by replacement.

Here are the axiom checks. Extensionality follows because equal new extensions mean $\pi (x)=\pi (y)$ and hence $x=y$. The new empty set is ${\pi }^{-1}(\varnothing )$ and the new pair is ${\pi }^{-1}(\{x,y\})$. For an object $a$, new union and power set have representativesThese formulas verify the actual new membership conditions. A definable subset of the new extension $\pi (a)$ is an old set by separation after translation, and its representative gives new separation. Similarly, a functional new formula on that extension has an old set as range by replacement; apply ${\pi }^{-1}$ to its range. For infinity, iterate the new successor operationstarting from the new empty set. Old recursion and replacement collect its finite iterates into a set $B$, and ${\pi }^{-1}(B)$ is a new inductive set. Thus all axioms of ZF except possibly foundation hold.

Now swap the old objects $0=\varnothing$ and $1=\{0\}$ and fix everything else. The old object $0$ then satisfies $0E0$, and its entire new extension is $\{0\}$. It is a Quine atom, so foundation fails. Taking $\pi$ to be the identity gives the original model where foundation holds. Foundation is independent of the other ZF axioms, relative to consistency of ZF.

A full permutation of a model of choice does not destroy choice. Given a new family of nonempty new sets, old choice selects an element of each old extension $\pi (y)$; replacement converts its graph into new ordered-pair coding. Thus simply repeating the preceding unrestricted permutation construction would not prove independence of choice. The extension needed is the hereditarily finite-supported Quine-atom model.

Start with a model of ZFC and simultaneously swap $a_n=\omega +n$ with $\{a_n\}$ for all $n<\omega$. These transpositions have disjoint supports: none of these infinite ordinals is a singleton, and the ordinals and their singletons are separately distinct. Put $A=\{a_n:n<\omega \}$, whose members now have new extensions $\{a_n\}$. Build the universe over these Quine atoms by allowing arbitrary new sets of previously constructed objects at each successor stage, and taking unions at limit stages. More explicitly, begin with $U_0=A$, putand take the union over all ordinals. The singleton with sole member $a_n$ is already $a_n$, as extensionality requires; it is not added as a different atom or set. Every other object's membership has a well-founded construction rank once these designated atomic self-loops are treated as rank-zero leaves.

Every permutation $g$ of $A$ extends to an automorphism of this universe: on atoms use $g$, and on every non-atomic object recurse byThe inverse permutation gives its inverse, and the formula preserves $E$. Call an object supported by a finite $S\subseteq A$ when every permutation fixing $S$ pointwise fixes that object. Retain only objects which are supported and all of whose members are hereditarily supported; the recursion here again stops at atoms, whose support is their singleton. Denote this class by $H$.

We verify that $(H,E)$ is a model of ZF without foundation. It is membership-closed and hence retains extensionality. Pairing uses the union of the two parameter supports, and union uses the support of its input. For separation, use the finite union of the supports of the domain and all parameters: permutations fixing them preserve satisfaction in $H$, so they fix the defined subset. Every member remains hereditary. For replacement, the same support fixes the image of a definable functional relation; its elements already lie in $H$ by the internal range condition, and old replacement supplies the underlying set of them. These assertions are legitimate class translations because construction ranks, supports and hereditary support are definable in the starting model.

For power set, start with the set of all new subsets of a supported set and retain exactly those lying in $H$. The resulting collection is fixed by every permutation fixing the original set's support: the action preserves hereditary support and permutes its subsets. Every retained member is hereditary, so this is the internal power set. The empty set and the pure finite and infinite natural-number hierarchy have empty support, yielding infinity. The new pairing, union and comprehension representatives discussed above therefore remain inside $H$. Foundation still fails because all the Quine atoms are in $H$.

The set $A$ itself has empty support and hereditary members. So does the family of its two-element subsets, each of which has a finite support in a permutation action. If this family had a choice function $f\in H$, let $S$ be a finite support in a permutation action of $f$, and choose distinct $a,b\in A\setminus S$. The transposition of $a,b$ fixes $S$ and the unordered pair $\{a,b\}$, but interchanges either possible chosen value $f(\{a,b\})$. It cannot fix the function graph, contradicting its support. Thus choice fails in $(H,E)$.

The unrestricted permutation model over the same initial ZFC model satisfies choice and fails foundation, whereas its hereditarily supported submodel fails both. Hence choice is independent of ZF with foundation omitted. These are relative-consistency constructions, not an assertion that ZF proves its own consistency. Starting with ZFC is harmless for the usual consistency comparison with ZF, by the constructible-universe relative-consistency theorem.

A useful precise form of the Ehrenfeucht-Mostowski theorem is this: for an infinite structure $M$ and any linear order $I$, a model of $\mathrm{Th}(M)$ can be generated as a Skolem hull by distinct order indiscernibles $(a_i{)}_{i\in I}$. Every order automorphism of $I$ extends to an automorphism of that hull in the chosen Skolem language. One may first name all elements of $M$, giving an elementary extension containing the original structure. The generation and uniqueness assertions concern this specified expansion, not arbitrary automorphisms of its reduct.

Choose a Skolem expansion $M^{\ast }$: for each existential formula add a function selecting a witness whenever one exists. Introduce constants $c_i$ for $i\in I$. Take the theory of $M^{\ast }$, distinctness of these constants, and all equivalencesThe formulas here are in the fixed expanded language, without the newly added $c_i$ as extra parameters. If naming $M$, use its complete elementary diagram and allow those original names in the formulas.

Every finite fragment has a model by Ramsey's theorem. Only finitely many formulas and constants occur. Take a sequence of distinct elements of $M$. For each arity appearing, color the increasing tuples from this sequence by the finite vector of truth values of all formulas of that arity. Successive Ramsey thinning gives an infinite subset homogeneous for each of these finitely many colorings. Assign the finitely many constants in increasing order to distinct elements of this subset. This satisfies every displayed equivalence in the fragment; the original theory is satisfied because the underlying structure remains $M^{\ast }$. Compactness now gives a model of the full theory, with the required order-indiscernible sequence.

The substructure generated by the constants under the Skolem functions is elementary: any existential formula with parameters which are terms in the generators has its Skolem witness in that same hull. If $g$ is an order automorphism of $I$, defineIndiscernibility makes this well-defined, by applying it to the equation between any two term representations using the increasing tuple of all their indices. The same argument preserves every relation and function; $g^{-1}$ supplies the inverse. It is unique in the generated Skolem structure. This completes the Ramsey proof, rather than stopping at the existence of indiscernibles.

For simple typed set theory with atoms, use sorts $D_0,D_1,\dots$ and membership only from $D_i$ to $D_{i+1}$. A set predicate distinguishes sets from atoms, extensionality compares sets of the same positive type, and comprehension produces in type $i+1$ every subset of $D_i$ defined by a well-typed formula. Atoms have no members. First-order models use Henkin semantics; they are not required to have their next domain equal to the full external power set. Typical ambiguity is the schema $\varphi \leftrightarrow {\varphi }^{+}$ for each closed sentence, where every sort index in ${\varphi }^{+}$ is raised by one.

We show finite satisfiability of this entire typed theory with ambiguity. Choose a list of ranks ${\rho }_0<{\rho }_1<\cdots$ above $\omega$, spaced by at least two. For a finite increasing selection of ranks $r_{-1}<r_0<\cdots <r_m$, letwhere $S_i$ is the set of objects declared to be sets at type $i$. Membership from $D_i$ to $D_{i+1}$ is ordinary membership restricted to objects of $S_{i+1}=\mathcal{P}(D_i)$; all other type-$i+1$ objects are atoms. The spacing puts $\mathcal{P}(D_i)$ inside $D_{i+1}$. Thus comprehension and set extensionality hold exactly, and atoms have no typed members. There are infinitely many objects at every visible type, so any usual typed infinity requirement also holds.

The auxiliary rank $r_{-1}$ provides a uniform interpretation if a set predicate is allowed at type zero; no type-minus-one domain is used in the theory. This avoids artificially declaring all type-zero objects to be atoms, which would not be invariant under type-raising. If the language has no type-zero set predicate, simply ignore this auxiliary interpretation.

A finite set of ambiguity instances uses finitely many closed sentences of bounded highest type, say at most $m$. Color increasing $(m+2)$-tuples of ranks by their finite truth vector in the structure with visible domains $D_0,\dots ,D_m$ and the auxiliary preceding rank. Ramsey's theorem gives an infinite homogeneous rank set. Choose $m+3$ consecutive ranks from it and build the hierarchy on all these ranks. The first window evaluates each original sentence; shifting the window one place evaluates its uniform type-raise. Homogeneity makes the truth vectors equal. All finite typed axioms and the selected ambiguity instances therefore hold together. Choosing $m$ large enough covers every sort needed by the finite fragment. Many-sorted compactness, equivalently ordinary first-order compactness after encoding sorts, yieldsThis is a model existence argument in the ambient set theory; no equality of adjacent type cardinalities is claimed. The gaps between ranks supply atoms, and the ambiguity is about truth of sentences, not a bijection between domains.

A set family shatters a set $Z$ when its traces on $Z$ include all of $\mathcal{P}(Z)$. The Sauer-Shelah lemma says that a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ which shatters no $k$-set satisfiesEquivalently, if $|\mathcal{F}|$ exceeds this sum, it shatters a $k$-set. Binomial coefficients with index greater than $n$ are zero; if $k>n$ the inequality reduces to the whole-power-set bound. The VC dimension formulation puts $k=d+1$.

We give the full inductive proof. Split $\mathcal{F}$ according to the last coordinate, deleting that coordinate from the present section, and write these two set families on $[n-1]$ as ${\mathcal{F}}_0,{\mathcal{F}}_1$. PutThe inclusion-exclusion principle gives $|\mathcal{F}|=|\mathcal{C}|+|\mathcal{D}|$. If $\mathcal{C}$ shattered a $k$-set, then $\mathcal{F}$ would shatter it too. If $\mathcal{D}$ shattered a $(k-1)$-set $Z$, both versions of each required trace, with and without the last coordinate, would occur in $\mathcal{F}$, which would shatter $Z\cup \{n\}$. Thus the two mathematical induction bounds apply:using Pascal's identity. For $n=0$ the set family has at most one member. For $k=1$, the intersection section must be empty, since any nonempty set family shatters the empty set. These supply the mathematical induction bases; the forbidden-empty-set case has an empty set family and an empty sum. Sharpness is attained by all subsets of size at most $k-1$, which cannot shatter a $k$-set.

Now fix $k\ge 1$ in the infinite-ground-set problem. Choose, using the hypothesis with $2k$, a set $Y$ of size $2k$ with at least $2^{2k-1}$ distinct traces. If its trace set family shattered no $k$-set, the Sauer-Shelah lemma would givea contradiction. Therefore some $Z\subseteq Y$ of size $k$ is shattered by the trace set family, and hence by $\mathcal{A}$ itself. Thus every finite shattering size occurs. The use of $2k$ makes the contradiction strict, even though the hypothesis only gives a half-power-set lower bound.

An infinite realization does not follow. For a concrete unbounded finite shattering without an infinite universal trace construction, partition $X=\mathbb{N}$ into disjoint finite blocksand takeEvery member is finite. Given $k$, choose $Y=B_k$; its trace set family is the full power set, so it has $2^k\ge 2^{k-1}$ members and is shattered. However, an infinite $Z$ cannot be contained in one finite block. Choose $x,y\in Z$ from different blocks. No member of $\mathcal{A}$ contains both, so $\{x,y\}$ is not a trace on $Z$. Consequently there need not be an infinite $Z$ whose traces contain every finite subset of $Z$.

Work inside a model $V$ of ZF. Let $\pi :V\to V$ be a definable class bijection, with definable inverse, so that its image and inverse image of every set are sets by Axiom schema of replacement. Define new membership byThis is the Rieger-Bernays permutation model convention used here. Its basic advantage is that every prescribed old set $b$ is the new extension of the object ${\pi }^{-1}(b)$. We verify the axioms rather than treating a membership permutation as automatically harmless.

The new axiom of extensionality follows because equality of the new extensions means $\pi (x)=\pi (y)$, hence $x=y$. The new empty set and unordered pair are ${\pi }^{-1}(\varnothing )$ and ${\pi }^{-1}(\{x,y\})$. Union and power set are represented byIndeed, the elements of the first object are exactly the new elements of new elements of $a$; the elements of the second are exactly the objects whose new extensions are subsets of $\pi (a)$.

Translate an arbitrary formula recursively by replacing each atomic $xEy$ by $x\in \pi (y)$. This is an ordinary definable formula in the old model. Old axiom schema of separation forms any specified subclass $b$ of $\pi (a)$, and ${\pi }^{-1}(b)$ supplies the new separated set. Old Axiom schema of replacement similarly collects the uniquely specified images of all elements of $\pi (a)$, and applying ${\pi }^{-1}$ supplies its new representative. This verifies the full schemas, including formulas with unbounded quantifiers.

For axiom of infinity, define $e_0={\pi }^{-1}(\varnothing )$ andThen $\pi (e_n)=\{e_0,\dots ,e_{n-1}\}$. These objects are distinct by induction: equality of $e_n$ with an earlier $e_m$ would equate old sets of respectively $n$ and $m$ distinct members. Old replacement collects $S=\{e_n:n\in \omega \}$, and ${\pi }^{-1}(S)$ is a new inductive set. Thus the construction satisfies every axiom of ZF except possibly Axiom of foundation.

Now interchange the old objects $\varnothing$ and $\{\varnothing \}$ and fix everything else. For $q=\varnothing$ we have $\pi (q)=\{q\}$, so its new sole member is itself: $q=\{q{\}}_E$. This Quine atom contradicts Axiom of foundation. The identity permutation preserves the original model and its foundation. Hence, relative to consistency of ZF, foundation is independent of the other ZF axioms.

For the further independence result, a full permutation of a model of choice is insufficient. If the old model satisfies axiom of choice, then for any new family $a$ of nonempty new sets, old choice selects $g(x)\in \pi (x)$ for every $x\in \pi (a)$. Encode its graph using the new ordered pairs, and represent that graph by ${\pi }^{-1}$. This is a new choice function. We therefore add a hereditary finite-support restriction to a universe with many Quine atoms.

Start now with a model of ZFC. Put $a_n=\omega +n$, and let $\pi$ interchange $a_n$ and $\{a_n\}$ for every $n\in \omega$, fixing other objects. All these transpositions are disjoint: the infinite ordinals $a_n$ are distinct and none is a singleton. In the resulting membership structure, $A=\{a_n:n\in \omega \}$ is an infinite family of Quine atoms.

Build its universe $W$ by the internal transfinite hierarchyWrite $W$ for the union over the old ordinals. Apart from the atomic self-loops, an object's new members have lower construction ranks. Every permutation $\sigma$ of $A$ therefore extends recursively to $W$: on atoms use the prescribed permutation, and on other objects putThis is well defined and preserves $E$. A nonatom cannot be sent to an atom, since an extension consisting solely of one atom already represents that atom. Recursing with ${\sigma }^{-1}$ gives the inverse, so these maps are genuine automorphisms.

Say that $x$ has finite support $S\subseteq A$ if every such permutation fixing $S$ pointwise fixes $x$. Let $H$ consist of the atoms and the objects with finite support all of whose new members, recursively away from atomic self-loops, belong to $H$. This is the hereditarily finite-supported Quine-atom model. We check why it still has the required set-theoretic axioms.

It is closed under taking new members, so extensionality remains valid. The empty object and the pure finite ordinals have empty support. Their internally represented infinite collection also has empty support, giving infinity. Pairs and unions use the finite unions of their constituents' supports; all their members remain hereditary members of $H$.

For a set $a\in H$, take all objects $b\in H$ whose new extensions are subsets of $\pi (a)$. They form an old set, since the unrestricted new power set is an old set and membership in $H$ is definable. Its representative has support contained in a support of $a$, because an automorphism fixing $a$ permutes precisely these hereditary subsets. All its members belong to $H$. Hence this is the power set required inside $H$, not a claim that unrestricted external subsets are retained.

For separation, relativize the formula to $H$. A support for $a$ together with supports of the finitely many parameters fixes the resulting subclass; its members are hereditary, so its representative belongs to $H$. For replacement, old replacement applied to this relativized definable functional relation collects the range. Its members have a common bound on their construction ranks, by taking the supremum of the set of ranks, so the range's representative lies in $W$. The same finite union of parameter and domain supports fixes the range by uniqueness of each image. It is therefore hereditary and belongs to $H$. These arguments verify the full schemas. Thus $H\models \mathrm{ZF}-\mathrm{Foundation}$.

Finally $A$ and the family of its two-element subsets belong to $H$ with empty support. Suppose a choice function $c$ for this family belongs to $H$, and let $S$ be a finite support for $c$. Choose distinct atoms $u,v\notin S$ and transpose them. This permutation fixes $c$ and fixes the unordered pair $\{u,v{\}}_E$, but interchanges its two possible selected members. Equivariance would requirewhich is impossible. Hence choice fails in $H$. Together with a model of ZFC, or with its full permuted model satisfying choice and failing foundation, this proves independence of axiom of choice from ZF minus foundation, relative to consistency of ZFC. All hierarchy and support arguments are internal to the starting model; no transitive-model assumption is needed.

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ to be the number of $i$-element subsets of an $n$-element set. Counting ordered selections and dividing by the $i!$ orders of each subset givesEvery subset has exactly one size, while each of the $n$ elements can independently be included or omitted. Hence the power set has $2^n$ members andTo prove the binomial theorem, expand the product of $n$ factors $(1+x)$. A term $x^i$ results from choosing $x$ from precisely an $i$-element subset of the factors and choosing one elsewhere. Its coefficient is therefore $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. This is a finite distributive expansion, valid for every real $x$, and givesDifferentiate this polynomial identity and set $x=1$:A second derivative gives $\sum i(i-1)\left(\genfrac{}{}{0ex}{}{n}{i}\right)=n(n-1)2^{n-2}$ for $n\ge 2$. Since $i^2=i(i-1)+i$, it follows thatThe formula also holds for $n=1$, when its value is one; that case can be checked directly without differentiating twice.

For the squared binomial coefficients, compare the coefficient of $x^n$ in $(1+x{)}^n(1+x{)}^n=(1+x{)}^{2n}$. On the left it is ${\sum }_i\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)$, and the binomial coefficient symmetry gives $\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)=\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. ThusFinally put $S={\sum }_{i}i{\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$ and replace the index $i$ by $n-i$. The same symmetry gives $S={\sum }_i(n-i){\left(\genfrac{}{}{0ex}{}{n}{i}\right)}^2$. Adding the two expressions and using the preceding identity yields

Here the power set notation gives $xEy⟺\mathcal{P}(x)\subseteq y$. Suppose a nonempty set $A$ has no $E$-minimal member. Form its intersection $b=\bigcap A$. This is a set: for any one $a_0\in A$, use the axiom schema of separation inside $a_0$ to define the elements common to all members of $A$. Selecting a single witness to nonemptiness is not an application of the axiom of choice.

For an arbitrary $y\in A$, lack of minimality supplies some $x\in A$ with $\mathcal{P}(x)\subseteq y$. Since $b\subseteq x$, every subset of $b$ is a subset of $x$, soThis conclusion holds for each $y\in A$, without choosing all the corresponding $x$ simultaneously. Intersecting over $y$ gives $\mathcal{P}(b)\subseteq b$.

For completeness, the contradiction in Cantor's theorem is completely explicit here. By the axiom schema of separation put $d=\{u\in b:u\notin u\}$. Then $d\in \mathcal{P}(b)\subseteq b$, and consequentlywhich is impossible. Thus no such $A$ exists:This power-set-predecessor relation proof uses neither a descending sequence nor a comparison of possibly non-well-orderable cardinalities. It proves well-foundedness directly from the minimal-member definition.

For the cardinality of integer-periodic function spaces, fix a positive period $n$ first. A periodic function $\mathbb{Z}\to \mathbb{Z}$ with that period is completely and uniquely determined by its $n$ values at $0,\dots ,n-1$, so this class is in bijection with ${\mathbb{Z}}^n$. The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive $n$ and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.

For the rational domain, even period one leaves infinitely many independent choices. Let $q_k=1/(k+2)$ for $k\in {\mathbb{N}}_0$; these are distinct members of $\mathbb{Q}\cap [0,1)$. For every subset $A\subseteq {\mathbb{N}}_0$, defineThe fractional part is unchanged by adding one, so $f_A$ is an integer-valued periodic function on $\mathbb{Q}$. Distinct subsets give distinct functions because $f_A(q_k)$ records whether $k\in A$. Thus the uncountable power set of ${\mathbb{N}}_0$ injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that $\mathbb{Z}$ has only finitely many residue classes modulo a fixed integer period, whereas $\mathbb{Q}$ has infinitely many.

A strongly inaccessible cardinal is an uncountable cardinal $\lambda$ that is both regular and a strong limit:Regularity excludes expressing $\lambda$ as the supremum of a shorter increasing sequence, while the strong-limit requirement concerns all smaller power sets. Merely being an uncountable regular limit cardinal is the weaker notion of a weakly inaccessible cardinal.

The printed inclusion-and-elementarity assertion is false if transitivity is required of the same submodel. Take the theorem of ZFC that combines the axiom of infinity and the Axiom of power set. Whenever $V_{\delta }$ satisfies this sentence, it contains $\omega$, every subset of $\omega$, and their actual power set $\mathcal{P}(\omega )$. A submodel $M\prec V_{\delta }$ contains $\omega$ and $\mathcal{P}(\omega )$, since these are uniquely definable in $V_{\delta }$. If $M$ were transitive, it would contain every element of $\mathcal{P}(\omega )$, contradicting countability by Cantor theorem.

The corrected conclusion uses an elementary embedding rather than elementary inclusion. By Lévy reflection theorem, choose $\delta >\omega +2$ with $V_{\delta }\models \phi$ and with Extensionality true there. The Downward Lowenheim-Skolem theorem says that an infinite structure in a countable language has a countable elementary substructure. Apply it to obtain a countable $N\prec (V_{\delta },\in )$. The membership relation on $N$ is externally well-founded, and elementarity makes it extensional. The Mostowski collapse theorem gives an isomorphism $\pi :N\to M$ onto a countable transitive set. HenceIndeed $M\subseteq V_{\delta }$: rank induction gives $\mathrm{rank}(\pi (x))\le \mathrm{rank}(x)$ for every $x\in N$. The crucial correction is that $j$, rather than the inclusion of $M$, is elementary. For a formula with free variables, apply this argument to its universal closure.

The structure $H_{\kappa }$ of hereditarily small sets is transitive. If $\kappa \le \omega$, all its sets are hereditarily finite, so it cannot satisfy Infinity. Therefore the assumed model has $\kappa >\omega$.

Let $\mu <\kappa$ be a cardinal. The ordinal $\mu$ belongs to $H_{\kappa }$, and every actual subset of $\mu$ also belongs to $H_{\kappa }$: its transitive closure has size at most $\max (\mu ,\omega )<\kappa$. The Power set axiom inside $H_{\kappa }$ therefore produces the actual $\mathcal{P}(\mu )$, since all subsets relevant to the internal definition are present. This power set itself belongs to $H_{\kappa }$, soThus $\kappa$ is a strong limit. Its regularity was assumed, and we have proved uncountability. Hence $\kappa$ is strongly inaccessible.

As printed, yes: the relation is universal. The original PDF puts the existentially quantified element in the same subset as the universally quantified element; this is not an OCR substitution. For each element of that subset, choose the element itself as witness, using reflexivity of the underlying well-quasi-ordering. For an empty subset the condition is vacuous. The truth value therefore never depends on the proposed target subset. On the power set this is a reflexive transitive relation, and every two terms of any infinite sequence are related:A well-quasi-ordering need not be antisymmetric, so universal comparability is allowed.

If the existential element is instead intended to belong to the target subset, the natural relation is the Hoare domination preorderFor arbitrary subsets the answer to that corrected question is no. Here is a complete counterexample, the Rado order. TakeThis is a partial order. Reflexivity is immediate. For transitivity, two same-row comparisons compose ordinarily. If the first comparison crosses rows and the second stays in its row, its target first coordinate is unchanged, so the cross-row inequality persists. If the first stays in its row and the second crosses, use $n\le l<k^{\prime }$; if both cross, use $n<k<l<k^{\prime }$. Antisymmetry follows because comparisons across distinct rows in both directions would require $n<k<l<m<n$.

The Rado order is a well-quasi-ordering. Given an infinite sequence $(m_i,n_i)$, if a first coordinate $m$ repeats infinitely often, its corresponding natural-number second coordinates have a nondecreasing pair, giving a same-row comparison. Otherwise each first coordinate occurs only finitely often, so the first coordinates in every tail are unbounded. In particular some later $m_j$ exceeds $n_0$, giving $(m_0,n_0){\le }_R(m_j,n_j)$.

For each $m$, take the infinite row $S_m=\{(m,n):n>m\}$. For distinct $m,k$, choose $n>\max (m,k)$. The element $(m,n)\in S_m$ is below no member $(k,l)$ of $S_k$, since its first coordinate is different and $n<k$ fails. Thus $S_m/{\le }_H{S}_k$ for every pair of distinct indices. These subsets form an infinite antichain, so the Hoare domination preorder on $\mathcal{P}(R)$ is not a well-quasi-ordering.

If only finite subsets were intended, the answer changes again: the finite-subset lifting of a well-quasi-order is a well-quasi-ordering. Enumerate each finite subset as a finite word. Higman lemma gives an earlier word embedding into a later one with every letter increased, which witnesses Hoare domination preorder comparison of the underlying subsets. The PDF specifies no finiteness restriction, so this observation supplements rather than replaces the literal answer and the arbitrary-subset counterexample.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

A witness to failure of the Axiom of power set is $\boxed{{\omega }_1\in H_{{\omega }_2}}$. Every subset $A\subseteq {\omega }_1$ belongs to $H_{{\omega }_2}$, since its transitive closure has cardinality at most ${\aleph }_1$. If some $p\in H_{{\omega }_2}$ were the internal power set of ${\omega }_1$, transitivity and bounded subsethood would force $p$ to contain every ambient subset of ${\omega }_1$, and only those subsets. Thus it would be the full $\mathcal{P}({\omega }_1)$.

By the Cantor theorem,Its transitive closure contains all its members, so $|\mathrm{tc}(\{p\})|\ge |p|\ge {\aleph }_2$. This contradicts $p\in H_{{\omega }_2}$. ThereforeThe power-set failure in hereditarily small sets needs no assumption about the Continuum hypothesis.

The Von Neumann hierarchy is the following transfinite recursion on the ordinals:Here $\mathcal{P}$ denotes the full power set. The levels are increasing transitive sets, and the construction is continuous at limit ordinals. Transfinite induction proves these properties: transitivity at a successor follows because a member of a subset of $V_{\alpha }$ already belongs to $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$; at a limit it follows from the set union of increasing transitive sets. In ZF, Axiom of foundation and Axiom schema of replacement ensure that every set belongs to some $V_{\alpha }$. In terms of the rank of a set, $x\in V_{\alpha }$ exactly when $\mathrm{rank}(x)<\alpha$.

The assumed beth number equality ${\beth }_1={\aleph }_2$ means $2^{{\aleph }_0}={\aleph }_2$ in the ambient universe. Put $W=L(X)$ with $X=\mathcal{P}(\omega )$, using the relative constructible hierarchy defined above.

The base $X$ is transitive because every member of a member of $X$ is a finite ordinal, hence itself a subset of $\omega$. Moreover $X\subseteq W$ and $X\in W$, and $W$ is an inner model of ZF. The latter standard fact follows from the hierarchy and reflection: bounded-rank witnesses give pairing and union; reflection gives separation and replacement; ambient replacement bounds the stages of all relatively constructible subsets of any fixed set, giving power set. It does not require axiom of choice inside $W$. Since no new subsets of $\omega$ can appear in an inner class,

Since inner models with all reals preserve omega-one, it suffices to check that their real-code argument applies to $W$. Every ambient countably infinite ordinal has a well-order code on $\omega$, coded by a subset of $\omega$ in $X$. Finite ordinals and $\omega$ are already shared. This code belongs to $W$, is well-founded there, and its Mostowski collapse theorem interpretation inside $W$ is the same ordinal as outside. Hence the ordinal is countable in $W$. Conversely, any countability witness in $W$ remains a witness in the ambient universe. Thus ${\omega }_1^W={\omega }_1$.

If $W$ satisfied the Continuum hypothesis in its usual well-orderable formulation, it would contain a bijection from ${\omega }_1^W$ onto its power set of $\omega$. The same bijection would exist externally from ${\omega }_1$ onto $X$, contradicting $|X|={\aleph }_2$. ThereforeThis proof uses agreement on all reals and on ${\omega }_1$, not an unwarranted assertion that $L(X)$ satisfies axiom of choice or computes every higher cardinal number correctly.