(Looking to get back to basics so I can try to create a first principles proof for this, using the k-index filtering logic. The issue is in trying to prove that the complement set is infinite. Here, we take two steps back to the n=k+1 and composite k=xy+x+y framework (eg. fundamental definition of primality) in order to reframe Euclid’s classic theorem on the infinitude of primes.)
The Fundamental Partition
We begin with formal definitions. Let K be the set of positive integers. We define two disjoint subsets of K whose union is K.
- Definition 1: Let C be the set of all integers k in K that can be expressed in the form k = xy + x + y for some positive integers x and y.
- Definition 2: Let P be the complement of C in K, such that P = K \ C.
Theorem 1:
- (i) An integer k is in C if and only if k+1 is a composite number.
- (ii) An integer k is in P if and only if k+1 is a prime number.
- (iii) Both sets, C and P, are infinite.
Goal:
To prove that the set P is infinite without assuming the infinitude of primes. The set P contains all positive integers k that cannot be expressed in the form k = xy + x + y for any positive integers x and y.
We know that an integer k is in P if and only if k+1 is a prime number. The proof will show that for any finite collection of elements from P, we can always find a new element of P that is not in the collection. This implies P must be infinite.
Proof:
- Let P_sub = {k_1, k_2, …, k_n} be any finite, non-empty subset of P.
- By the definition of the set P, each number p_i = k_i + 1 is a prime number. This gives us a finite list of primes: {p_1, p_2, …, p_n}.
- Construct a new integer, M, by taking the product of all these primes:
M = p_1 * p_2 * … * p_n - Now, consider the integer K = M + 1. Since M is the product of primes, M is at least 2, so K is an integer greater than 1.
- Every integer greater than 1 must have at least one prime divisor. Let q be a prime divisor of K.
- We ask: is this prime q one of the primes in our original list {p_1, p_2, …, p_n}?
Let’s assume it is. If q were equal to some p_i from our list, then q would have to divide M, since M is the product of all the p_i.
We also know, by construction, that q divides K = M + 1.
If q divides both M and M + 1, then it must also divide their difference, which is (M + 1) – M = 1.
However, no prime number can divide 1. This is a contradiction. - Therefore, our assumption in step 6 must be false. The prime factor q cannot be any of the primes {p_1, p_2, …, p_n}. It must be a new prime, one that was not in our original list.
- Since q is a prime number, the integer k_new = q – 1 satisfies the condition for being an element of P (because k_new + 1 = q, which is prime). Because q is not in our original list of primes, k_new cannot be in our original list of elements from P.
Conclusion:
We have demonstrated that for any finite subset of P, we can always construct another element of P that is not in that subset. This procedure can be repeated indefinitely. Therefore, the set P cannot be finite and must be infinite.