Use the intended first-order structure of real arithmetic, with Int selecting the integers; $z$ is the parameter in ${\varphi }_z$. A suitable first-order formula isThe first condition requires a real square root of $2z$. The second excludes every representation as a rational number $p/q$ with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular, $2$ is written $1+1$ and there is no extra division symbol. A square root exists exactly when $z\ge 0$, and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on $r$ does not affect the claim about the principal square root. At $z=0$ the formula is false; for $z<0$ there is no real witness. The meanings of $+$ and $\ast$ as real arithmetic, not just the meaning of Int, are part of this interpretation.

Combine a minimum with an adjacent pair in a linear order:In $[0,1]\cup [2,3]$, choose $m=0,u=1,v=2$. The minimum and the adjacent pair in a linear order both exist. In $[0,1]$, the dense order property rules out such an adjacent pair. In $\mathbb{Z}$, adjacent pairs exist, but no minimum exists: for any $m$, the integer $m-1$ is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.

Express that the order is a dense order:In either real interval, $(x+y)/2$ lies strictly between any two distinct ordered elements and remains in the domain. In the integers, $x=0,y=1$ have no intervening integer, so this first-order sentence is false. The endpoints of a closed interval do not prevent a dense order.

Express existence of a minimum using only the given strict-order relation:In the closed interval $[0,1]$, the witness is $m=0$. In the open interval $(0,1)$, every possible witness $m$ has the smaller member $m/2$, so the first-order sentence is false. These witnesses are explanations in the ambient real numbers, not additional symbols in the first-order signature.

Only $\psi$ requires a natural deduction proof. Assume $h:(A\vee B)\to C$. Within that assumption, temporarily assume $a:A$. By disjunction introduction, obtain $A\vee B$; applying $h$ by the implication elimination rule gives $C$. Discharge $a$ by the implication introduction rule to derive $A\to C$. Disjunction introduction now gives $(A\to C)\vee (B\to C)$. Finally discharge $h$ by the implication introduction rule:All temporary assumptions are discharged. No classical rule is needed; the same proof works in Intuitionistic propositional logic. The false propositional formula $\phi$ has no proof in this sound natural deduction system.

Let $F=(A\to C)\vee (B\to C)$ and $H=(A\vee B)\to C$, so the two displayed propositional formulas are $\phi =F\to H$ and $\psi =H\to F$. Their complete truth tables areTherefore $\psi$ is a tautology; $\phi$ is not. For example $(A,B,C)=(0,1,0)$ makes the antecedent $F$ true via $A\to C$, while $H$ is false because $B$ is true and $C$ is false. This explains why having just one of the two logical implications is insufficient for the forward direction.

Use structural induction on the propositional formula. The induction claim is that its truth value under the all-one Boolean valuation is one. A variable has this truth value by definition. For the induction step, suppose the immediate subformulas $\alpha ,\beta$ each have truth value one. ThenThese are all permitted construction cases. Thus every such propositional formula evaluates to one. Equivalently, the three logical connectives define one-preserving Boolean functions, and composition preserves this property. The variable-only base grammar matters: admitting a constant false formula would invalidate the claim.

The given logical implication is false exactly when $A=B$ and $C\ne D$. For every literal on $A,B,C,D$, there is such a false Boolean valuation making that literal true. For a prescribed value of $A$ or $B$, give the other the same value and choose $C\ne D$. For a prescribed value of $C$ or $D$, give the other the opposite value and choose $A=B$.

Consequently no literal implies the whole propositional formula: there is no one-literal implicant. If an equivalent disjunctive normal form contained a one-literal conjunction term $\ell$, then every Boolean valuation satisfying $\ell$ would satisfy that disjunctive normal form, contradicting its equivalence to the given propositional formula. This proves the claim. Even if auxiliary Boolean variables are allowed in the equivalent expression, a one-literal term on one of them fails too: fix any false Boolean valuation of the original four and set the auxiliary literal true. The word “conjunct” here refers to a conjunction term in the disjunctive normal form, not a factor in a conjunctive normal form.

Eliminating logical implications givesAn absorption step simplifies this to the disjunctive normal formEach one-literal term is a permitted logical conjunction in a disjunctive normal form.

The kernel of a linear map $g$ is precisely $U$, sincePart (c) gives $\mathrm{im}g=W_1+W_2$. Apply the rank-nullity theorem to the finite-dimensional vector space $W_1\times W_2$, and then parts (a) and (b):This proves the dimension formula for a sum of subspaces. The kernel of a linear map records exactly the freedom to transfer a shared vector from one summand to the other without changing their sum.

Every output $u_1+u_2$ lies in the sum of subspaces $W_1+W_2$, since it is a linear combination of members of the two vector subspaces. For $u=(u_1,u_2)$, $v=(v_1,v_2)$ and scalars $a,b$,Therefore $g$ is a linear map. Every vector in $W_1+W_2$ is such an output: group the terms of any linear combination from $W_1\cup W_2$ according to their originating vector subspace. Thus the addition map of subspaces is also surjective.

Writing the given bases as $(u_1,\dots ,u_p)$ and $(v_1,\dots ,v_q)$, a basis of the Cartesian product with its componentwise vector space operations isThis is the direct sum basis. Therefore $\dim (W_1\times W_2)=p+q=\dim W_1+\dim W_2$. The construction includes zero-dimensional factors, whose corresponding portion of the basis is empty.

Use banded Gaussian elimination followed by back substitution. To distinguish the right-hand side from the upper-diagonal coefficients $b_i$, write it as $r_i$. If the modified pivot elements are nonzero, the tridiagonal elimination recurrences areThey eliminate just the one entry below each pivot element. Solve the resulting upper bidiagonal matrix system byThere is a bounded number of arithmetic operations per row in each sweep, giving $O(n)$ arithmetic operations and $O(n)$ storage. The unpivoted recurrences cost $8n-7$ arithmetic operations under the usual scalar-operation count.

For a general tridiagonal matrix, nonsingularity alone does not guarantee these pivot elements. If a zero or unsafe pivot element occurs, use partial pivoting between the current row and the next row. These are the only possible nonzero candidates in the current column; adjacent row swaps introduce at most a second upper diagonal. Tracking that fill-in keeps both Gaussian elimination and back substitution at $O(n)$ arithmetic operations. For example, $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is invertible but requires a row swap. If the input is singular, report a zero final pivot element; a unique solution cannot be promised, and compatibility or free-variable analysis is a separate issue. No nonsingularity or safe-pivot assumption is silently inferred from the word tridiagonal.