Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of $g$ gives $f(a)=f(a^{\prime })$, and injectivity of $f$ then gives $a=a^{\prime }$. Thus the function composition is injective.

Take the nonempty intersections of the length-three and length-four blocks. Within the first twelve nonnegative integers the common cut points are $0,3,4,6,8,9,12$, givingThe complete partition of a set consists of these six blocks translated by $12j$ for every $j\in \mathbb{N}$. Indeed, adding $12$ increases the two floor quotients by $4$ and $3$ respectively, preserving equality of both quotients within each translated block. No adjacent displayed blocks can merge because at least one quotient changes at their boundary. This is the periodic common refinement of floor-quotient partitions, with period $\mathrm{lcm}(3,4)=12$.

The floor function is constant at $j$ on the four consecutive integers $4j,4j+1,4j+2,4j+3$. Consequently the partition of a set is $\{\{4j,4j+1,4j+2,4j+3\}:j\in \mathbb{N}\}$. Different blocks are disjoint and every nonnegative integer has exactly one quotient and remainder upon division by $4$.

For every $x\in A$, membership in the relevant equivalence class satisfiesEquality follows by axiom of extensionality. Thus $[a{]}_{R\cap S}=[a{]}_R\cap [a{]}_S$.

For every $a$, both $aRa$ and $aSa$ hold, so the intersection of equivalence relations is reflexive. If $a(R\cap S)b$, symmetry of both component binary relations gives $bRa$ and $bSa$, hence $b(R\cap S)a$. Finally, if $a(R\cap S)b$ and $b(R\cap S)c$, transitivity in each component gives $aRc$ and $aSc$, hence $a(R\cap S)c$. These are precisely the three conditions for an equivalence relation.

Write each member as $3-2/(n+1)$. Every member is strictly below $3$, so $3$ is an upper bound. If $u<3$, the Archimedean property supplies $n\in \mathbb{N}$ with $n+1>2/(3-u)$; then $3-2/(n+1)>u$. Thus no smaller number is an upper bound, proving $\sup S=3$. Since $3\notin S$, there is no greatest element. Equivalently, each member is followed by a larger member because $2/(n+2)<2/(n+1)$.

For the pointwise order on real polynomials, $p(x)\le p(x)$ proves reflexivity. Two opposite inequalities imply $p(x)=q(x)$ for every real $x$; the polynomials are therefore equal, proving the antisymmetric relation axiom. Chaining the inequalities at every $x$ proves transitivity.

To disprove total order, take $p(x)=x$ and $q(x)=0$. The inequality $p⪯q$ fails at $x=1$, whereas $q⪯p$ fails at $x=-1$. The order is partial but non-total.

For the product order, reflexivity follows from $a_i\le a_i$ in every coordinate. If $\mathbf{a}⪯\mathbf{b}$ and $\mathbf{b}⪯\mathbf{a}$, the antisymmetric relation axiom for the usual real order gives $a_i=b_i$ for every $i$, hence $\mathbf{a}=\mathbf{b}$. If $\mathbf{a}⪯\mathbf{b}⪯\mathbf{c}$, transitivity in each coordinate gives $a_i\le c_i$, hence $\mathbf{a}⪯\mathbf{c}$. Thus this is a partial order.

For $n\ge 2$, the vectors $(1,0,0,\dots )$ and $(0,1,0,\dots )$ are incomparable: each has a coordinate larger than the corresponding coordinate of the other. It is not a total order for $n\ge 2$. The dimension qualification matters: for $n=1$ this is the usual total order on $\mathbb{R}$, so the printed non-totality claim needs the implicit assumption $n\ge 2$.

A total order is a partial order in which every pair is comparable: for every $a,b\in A$, at least one of $a⪯b$ and $b⪯a$ holds. Both hold exactly when $a=b$.

A partial order is a preorder satisfying the antisymmetric relation axiom. In addition to reflexivity and transitivity, it satisfies $a⪯b$ and $b⪯a$ only when $a=b$.

A preorder is a binary relation that is both reflexive and transitive: $a⪯a$ for every $a\in A$, and $a⪯b⪯c$ implies $a⪯c$.

Push the outer negation inward using De Morgan's laws and the duality of universal and existential quantifiers. Negating the outer universal quantifier first gives an existential $x$. Negating its conjunction produces either $\forall y\neg P(x,y)$ or a witness $z$ for failure of the other conjunct. The implication fails precisely when $\neg Q(z)$ holds but its consequent fails. Therefore a negation normal form isAll negations now apply directly to atomic formulas. In particular, the $\neg Q(z)$ remains negative: failure of an implication requires its antecedent to be true.

Read the initial universal quantifiers as governing the conjunction of irreflexivity and transitivity. Explicitly, the intended first-order sentence assertsThus $Q$ is an irreflexive relation, a transitive relation, and a serial relation.

Suppose a first-order model had a finite nonempty domain of cardinality $N$. Choose $a_0$. Seriality supplies successive elements $a_1,\dots ,a_N$ with $Q(a_i,a_{i+1})$. By the pigeonhole principle, $a_i=a_j$ for some $i<j$. Repeated transitivity along that part of the chain gives $Q(a_i,a_j)=Q(a_i,a_i)$, contradicting irreflexivity. Hence there is no finite nonempty model. This is the infinite-model property of a serial strict partial order.

An infinite model exists: take domain $\mathbb{N}$ and $Q(x,y)$ to mean $x<y$. It is irreflexive and transitive, and $y=x+1$ witnesses seriality for every $x$.

The quantifier-scope convention matters: giving each printed universal quantifier only the immediately following atomic scope would leave the transitivity implication with free variables and would not express the claimed theorem. The explicit parenthesisation above records the reading under which the source's requested assertion is valid.

The source's explicit parenthetical condition is domination: every unselected vertex has a neighbour in the selected set. Together with independence this defines an independent dominating set. A first-order sentence expressing that definition with size at most three isThe finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a first-order formula. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected vertices. The last clause says that every vertex is selected or adjacent to a selected vertex. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.

For the standard meaning of independent vertex cover, replace the domination clause byThis instead demands that every edge has a selected endpoint. These interpretations differ: in a triangle in a graph, any singleton is an independent dominating set, but no independent vertex cover exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses $x,y$ select the cover. The clause $\neg E(x,y)$ makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing $x=y$. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

Keep the premise $P\to Q$ open. Assume $Q\to \neg P$, then temporarily assume $P$. Two applications of the implication elimination rule produce $Q$ and then $\neg P$, contradicting the temporary $P$. Discharge $P$ using the negation introduction rule, then discharge $Q\to \neg P$ using the implication introduction rule.This natural deduction proof uses only the supplied introduction and elimination rules. Line 6 is an application of the negation elimination rule; no classical contradiction principle is needed.