Therefore, (P(a)≡T)∧(P(b)≡T)(P( a ) \equiv T) \wedge (P( b ) \equiv T), which means that aa and bb can both be expressed by the product of some primes.

For P(k+1)P( k+1 ), there are two cases.

Using the direct proof technique, we assume that (P(2)∧⋯∧P(k))≡T(P(2) \wedge \cdots \wedge P( k )) \equiv T.

Basis step: to prove that P(2)≡TP(2) \equiv T.

Since 2 is a prime, 2=22=2 shows that P(2)≡TP(2) \equiv T.

To use the UG rule, we consider an arbitrary positive integer kk with k≥2k \geq 2.

Case 2: k+1 is a not a prime. In this case k+1=a×bk+1 = a \times b , where aa and bb are positive integers greater than 1.

Define predicate P(n)P( n ) as the statement that nn equals to the product of some primes, where the domain of nn is {n∈Z|n>1}\{n \in Z | n > 1\} so the smallest element in this domain is 22.

proof

Inductive step: to prove that ∀k((P(2)∧⋯∧P(k))→P(k+1))≡T\forall k ( (P(2) \wedge \cdots \wedge P( k )) \to P( k+1 ) ) \equiv T, where k≥2k \geq 2.

Case 1: k+1 is a prime. In this case k+1=k+1k+1 = k+1 shows that P(k+1)≡TP( k+1 ) \equiv T

QED

So k+1=a×bk+1 = a\times b can be expressed by the product of some primes, i.e., P(k+1)≡TP( k+1 ) \equiv T