Write $U=\forall x_i\neg \varphi$ and $H=\neg U\to \psi$. All derivations below use the printed replacement axiom, so they do not rely on the false equivalence from part (a).

The identity logical implication $\neg A\to \neg A$ follows by the deduction rule. Substituting $\alpha =\neg A$, $\beta =A$ into the replacement axiom and applying modus ponens rule therefore gives double-negation elimination:Universal instantiation gives $⊢U\to \neg \varphi$. Combine it with $⊢\neg \neg U\to U$ using modus ponens rule under a temporary assumption and then the deduction rule, obtaining $⊢\neg \neg U\to \neg \varphi$.

In the replacement axiom now substitute $\alpha =\neg \varphi$ and $\beta =\neg U$. Its antecedent is precisely the last theorem, and its consequent is $\neg \neg \varphi \to \neg U$. ThusUnder the fixed assumption $H$ and temporary assumption $\neg \neg \varphi$, modus ponens rule gives $\neg U$ and then $\psi$. Discharge the temporary assumption to obtain $H⊢\neg \neg \varphi \to \psi$.

Finally apply universal generalization. The variable $x_i$ is not free in $H$, because it is bound in $U$ and is not free in $\psi$ by hypothesis. Hence the side condition is satisfied andGeneralization is applied after the temporary assumption has been discharged; applying it while that assumption remained open would not be justified.

A collection of logical connectives is adequate, or has functional completeness, if every Boolean function of finitely many propositional variables can be expressed by a formula using those connectives and variables, with the usual convention for nullary truth constants stated if those are included.

An adequate example is $\boxed{\{\neg ,\to \}}$. An inadequate example is $\boxed{\{\to \}}$: formulas using logical implication alone preserve truth when every input is true, so cannot express negation. These examples concern truth functions, rather than mere syntactic formation of formulas.

If $X$ is finite and nonempty, let $n=|X|\ge 1$, choose a bijection with the cyclic group $\mathbb{Z}/n\mathbb{Z}$, and transport its addition to $X$. This includes the one-element case.

If $X$ is infinite, use the maximal partial group $(A,m)$ from the preceding part. Its carrier must be infinite: otherwise $|X\setminus A|<|A|$ would make the complement finite too, forcing $X$ finite. Since the complement injects into $A$,where the last equality is the permitted infinite-cardinal doubling identity. Cantor-Schröder-Bernstein supplies a bijection $j:X\to A$. DefineAssociativity follows by applying $j$ and using associativity of $m$; the identity is $j^{-1}(e_A)$ and the inverse of $x$ is $j^{-1}(j(x{)}^{-1})$. Hence $(X,\star )$ is a group.

This final transport need not extend the earlier partial operation on its original subset. That stronger claim is neither needed nor generally possible: for example a group of order three cannot occur as a subgroup of a group of order four. The proof establishes exactly the existence of some group structure on every nonempty set, using the allowed choice consequences in the infinite case.

Apply Zorn's lemma using the chain upper bounds just proved, obtaining a maximal partial group operation $m$ on a nonempty carrier $A\subseteq X$. Suppose $|X\setminus A|\ge |A|$. Then choose a subset $B\subseteq X\setminus A$ and a bijection $b:A\to B$. The set $A\cup B$ can be identified with $A\times C_2$ by sending $(a,0)$ to $a$ and $(a,1)$ to $b(a)$.

Use group extension by a duplicate carrier to transport the direct-product group operation along this bijection. Its restriction to $A\times A$ is exactly the original $m$, because $(a,0)(a^{\prime },0)=(m(a,a^{\prime }),0)$. It therefore gives a strictly larger member of $\mathcal{G}$, contradicting maximality. Thus $|A|\nleqq |X\setminus A|$. Cardinal comparability, allowed as a consequence of Zorn's lemma, leaves the strict opposite inequality:The argument uses choice through Zorn's lemma and cardinal comparability; the extension itself is an explicit transported direct-product operation once the bijection with $B$ is chosen.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Order the partial group operations by inclusion of their graphs. The collection is a set, since its members are subsets of $X\times X\times X$. It is nonempty: choose $x_0\in X$ and put the one-element group operation on $\{x_0\}$.

To construct a chain union of partial group operations, for the given nonempty chain, let $m={\bigcup }_{n\in \mathcal{C}}n$ and let $A$ be the union of the corresponding group carriers. Comparability guarantees agreement wherever two operations are both defined, so $m$ is a function. Its domain is $A\times A$: any two elements of $A$ lie together in one carrier, by taking the larger of the two chain members containing them. Their product then lies in that carrier and hence in $A$.

Any three elements similarly lie together in one chain member, where associativity holds; therefore associativity holds for $m$. The identities of nested nonempty groups agree: the smaller identity remains an idempotent under the larger group operation, whose only idempotent is its identity. Hence the whole chain has a common identity. Each element's inverse in a carrier remains its inverse in every larger carrier, so it is an inverse in the union as well. Thus $(A,m)$ satisfies all group axioms andIt is an upper bound for the chain. The empty chain also has an upper bound because $\mathcal{G}$ is nonempty, completing the hypothesis needed for Zorn's lemma.

For the cardinality of total orders on a countably infinite set, a total order on $\mathbb{N}$ is a subset of $\mathbb{N}\times \mathbb{N}$, so there are at most $2^{{\aleph }_0}=\mathfrak{c}$ such orders. To obtain the lower bound, associate to every binary sequence $(b_n)$ an order by placing the two-element blocks $\{2n,2n+1\}$ in increasing order of $n$. Inside block $n$, use $2n<2n+1$ when $b_n=0$ and reverse them when $b_n=1$.

This is a total order for every sequence. Distinct sequences differ on the comparison of some adjacent pair and therefore produce distinct relations. Thus binary sequences inject into the order set, provingThe construction counts distinct orders on the labelled set, even though the resulting order types are all isomorphic to the usual natural-number order.

The complex plane has a countable basis of disks with positive rational radii and centres with rational real and imaginary coordinates. Each open set is the union of the basic disks it contains, so it is determined by a subset of this countable basis. Therefore the number of open sets is at most $2^{{\aleph }_0}=\mathfrak{c}$.

For the reverse inequality, the distinct disks $\{z:|z|<r\}$ for $r>0$ give $\mathfrak{c}$ different open sets. ThusThe countable-basis restriction is decisive: there are $2^{\mathfrak{c}}$ arbitrary subsets of the plane, but only continuum many open ones.