Is Furstenberg's proof just Euclid's proof with a lot of useless catsup?

[Swammerdami]

(This may be an uninteresting topic. I'm using it to practice writing math on the new Board.)

One of the most famous theorems in all of mathematics is Euclid's proof that there are an infinity of primes. This gem is the almost inevitable choice when a non-mathematician asks for an example of a theorem and its proof. Among all the great theorems of mathematics, prime infinitude has by far the simplest proof. In modern math papers anything that can be proved so easily wouldn't be called a "Theorem" or "Lemma", just a "Remark."

Euclid's proof is so simple that it is probably what Paul Erdos calls "God's Proof."

 Furstenberg's proof of the infinitude of primes is considered nifty because it uses the jargon of topology. This may be clever, but the arguments can be readily translated into ordinary set theory; let's bypass any topology jargon.

Start with the Distributive Law. Just as the identity a*(b+c) = ab+ac immediately leads to a*(b+c)*(d+e+f) = abd+abe+abf+acd+ace+acf so A ∩ (B ∪ C) = (A ∩ C) ∪ (A ∩ C) is an identity which lets any intersection of many big unions be transformed into a big union of many intersections. But I'm trying to practice LaTeX. The distributive law \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) leads to bigger distributions like

\(\ \ \ \ \small (A_1 \cup A_2 \cup A_3) \cap (B_1 \cup B_2 \cup B_3) \cap (C_1 \cup C_2) = (A_1 \cap B_1 \cap C_1) \cup (A_1 \cap B_1 \cap C_2) \cup (A_1 \cap B_2 \cap C_1) \cup \cdots \cup (A_3 \cap B_3 \cap C_1) \cup (A_3 \cap B_3 \cap C_2) \normalsize\)

OK? Let's get started.

Contrary to the typically weird Wikipedia article, it is simplest to view both Euclid's proof and Furstenberg's as indirect proofs. We will assume that there are finitely many primes and reach a contradiction. To save a little time let's suppose there are just three primes. (The proof doesn't depend on this number being so small.) The product of those primes will be useful so we'll call it \(\Pi\)
\(\ \ \ \ \Pi = \prod_i p_i = p_1 \times p_2 \times p_3\)

Now let's define residue class:
\(\ \ \ \ A(p,t) = \{ x \ | \ x \equiv t \;(\bmod\; p)\}\)
and finally define intersections of residue classes across all the primes
\(\ \ \ \ B(t_1, t_2, t_3) = A(p_1, t_1) \cap A(p_2, t_2) \cap A(p_3, t_3)\)

Now note that if \(y \in B(t_1, t_2, t_3)\) then \(y+\Pi \in B(t_1, t_2, t_3) \) and similarly for \(y + 2\Pi, y + 3\Pi\) and so on.

So \(B(1,1,1)\) is the set of integers 1 greater than a multiple of each prime. +1 is in that set, so \(1 + \Pi\) is as well. This contradicts the fact that every integer except +1 (and -1 if we were allowing negative integers, but we don't need that bother) must be a multiple of a prime. Euclid's proof is complete, although we seem to have taken a roundabout path to get there. We've added a lot of unnecessary catsup if you will!

But we've done all this because we're giving Furstenberg's proof. For that we needed all this. And have yet more catsup to add!

First Remark that any of the sets \(B(t_1, t_2, t_3)\) just defined is either empty or infinite. (if y is an element so are \(y + \Pi, y + 2\Pi, \cdots\))

Let's define \(C(p)\) as all the non-multiples of the prime p.
\(\ \ \ \ C(p) = A(p,1) \cup A(p,2) \cup ... \cup A(p, p-1)\)
And D as the set of all integers which are not multiples of any prime.
\(\ \ \ \ D = C(p_1) \cap C(p_2) \cap \cdots \cap C(p_3)\)
If our finite list of primes is complete then D is exactly the finite set \(D = \{ +1 \}\)
Now D is the intersection of unions, so by the Distributive Law we can rewrite it as the union of intersections
\(\ \ \ \ D = B(1,1,1) \cup B(1,1,2) \cup \cdots\)

As we Remarked, each of the B sets is either empty or infinite, so D is either empty or infinite.
But if our list of primes is complete, D is neither empty nor infinite; it would consist solely of +1. (Throw in -1 if you're a negative thinker.)
Q.E.D.

Am I missing something? Is Furstenberg's proof just Euclid's proof with a lot of catsup added?

 

[steve_bank]

Sounds like prime-al mathematics. Get it? Prime numbers and primal? I sholud do standup comedy only about math.

 

[lpetrich]

This proof is confusing to me, and I had to look up a lot of definitions. Understanding  Evenly spaced integer topology requires understanding  Topological space

A set S and its subsets B are a topological space, with B a topology on S. Members of B are called open sets.

1. Both S and {} are open sets.
2. The union of any set of open sets is an open set.
3. The intersection of any finite set of open sets is an open set.

Their complements with respect to S are closed sets. Some sets are both open and closed, like S and {}.

1. Both S and {} are closed sets.
2. The union of any finite set closed sets is a closed set.
3. The intersection of any set of closed sets is a closed set.

An arithmetic-series set S(a,b) = {a*n+b for n in Z} for nonzero a

The evenly-spaced integer topology is all arithmetic-series sets and unions of them.

The series sets S(a,b) are both open and closed: S(a,b) = Z - union of S(a,b+k) for k = 1 to a-1

A finite set cannot be open, since an open set contains at least one series set, and is thus infinite. Thus, the complement of a finite set cannot be closed.

Consider that Z - {1,-1} = union of S(p,0) over all primes p

{1,-1} is not an open set, thus Z - {1,-1} is not a closed set, thus, the union of S(p,0) over all primes p is not a closed set. Since each S(p,0) is a closed set, that means that the number of primes cannot be a finite number.


Even after restating the proof, I can't figure out how it might be connected to Euclid's proof.

 

[Swammerdami]

The evenly-spaced integer topology is all arithmetic-series sets and unions of them.
...
Even after restating the proof, I can't figure out how it might be connected to Euclid's proof.

But are you not assuming that which you need to prove? You can't use the properties of topologies until you've proven that that space is indeed a topology. How do we know the "topology" you just defined IS a topology?

From your first Wiki link, we see

Since the intersection of any finite collection of arithmetic progressions is again an arithmetic progression, the family of arithmetic progressions is in fact a base for the topology, meaning that every open set is a union of arithmetic progressions.

But IS the "the intersection of any finite collection of arithmetic progressions [] again an arithmetic progression"? This is a necessary part of Furstenberg's proof, as implied in my post. (Note that "residue class" and "elements of arithmetic progression" mean the same thing.)

...
\(\Pi = p_1 \times p_2 \times ... \times p_3\)

Now let's define residue class:
\(\ \ \ \ A(p,t) = \{ x \ | \ x \equiv t \;(\bmod\; p)\}\)
and finally define intersections of residue classes across all the primes
\(\ \ \ \ B(t_1, t_2, t_3) = A(p_1, t_1) \cap A(p_2, t_2) \cap A(p_3, t_3)\)

Now note that if \(y \in B(t_1, t_2, t_3)\) then \(y+\Pi \in B(t_1, t_2, t_3) \) and similarly for \(y + 2\Pi, y + 3\Pi\) and so on.

So \(B(1,1,1)\) is the set of integers 1 greater than a multiple of each prime. +1 is in that set, so \(1 + \Pi\) is as well. This contradicts the fact that every integer except +1 (and -1 if we were allowing negative integers, but we don't need that bother) must be a multiple of a prime. Euclid's proof is complete, although we seem to have taken a roundabout path to get there. We've added a lot of unnecessary catsup if you will! ...

"Even after restating the proof, I can't figure out how it might be connected to Euclid's proof."

The remark in the final paragraph of this excerpt establishes a topology prerequiste (the finite intersection of open sets is open) and does so using ... the very same argument Euclid uses to prove the primes cannot be finite in number!

 

[Swammerdami]

It's been 24 hours. lpetrich, will you bring closure to the thread by demonstrating any error I've made, or acquiescing?
I suppose that, as so often, my own explanations may seem confused. :-( Let me summarize.

TL;DR:

From your first Wiki link, we see

Since the intersection of any finite collection of arithmetic progressions is again an arithmetic progression, the family of arithmetic progressions is in fact a base for the topology, meaning that every open set is a union of arithmetic progressions.

The red clause is stated at the Wiki page without proof. Can we agree that it must be proved as part of the Furstenberg proof? I've shown how proof can follow from the exact argument that Euclid used to prove primes' infinitude. Do you or Furstenberg have a proof that bypasses that?

 

[lpetrich]

The arithmetic-sequence topology's members are easy to find if one sticks to a *finite* number of sets in a union or intersection.

With a finite number of unions and intersections, one finds that every possible set is a union of sequences that share the same step value. For instance,

• union of S(2,1), S(3,1) is union of S(6,1), S(6,3), S(6,4), S(6,5)
• union of S(2,0), S(3,0) is union of S(6,0), S(6,2), S(6,3), S(6,4)
• intersection of the two is S(6,3), S(6,4)

In general, union of S(a1,b1) and S(a2,b2) has a = lcm(a1,a2) and is
union of (union of S(a,b1+k*(a/a1)) for k from 0 to (a/a1)-1)
and (union of (S(a,b2+k*(a/a2)) for k from 0 to (a/a2)-1)

For an infinite number of input sets, however, I can't find anything, and the above kind of proof breaks down, because there must be an infinite number of a's in the sequences, and that means that there is no maximum a in them.

 

[Swammerdami]

(I'm not sure what you gained by writing S(a,b) to denote the exact same set as the one I call A(a,b) in the OP of a thread which I started. )

The arithmetic-sequence topology's members are easy to find if one sticks to a *finite* number of sets in a union or intersection.

With a finite number of unions and intersections, one finds that every possible set is a union of sequences that share the same step value. For instance,

• union of S(2,1), S(3,1) is union of S(6,1), S(6,3), S(6,4), S(6,5)
• union of S(2,0), S(3,0) is union of S(6,0), S(6,2), S(6,3), S(6,4)
• intersection of the two is S(6,3), S(6,4)

In general, union of S(a1,b1) and S(a2,b2) has a = lcm(a1,a2) and is
union of (union of S(a,b1+k*(a/a1)) for k from 0 to (a/a1)-1)
and (union of (S(a,b2+k*(a/a2)) for k from 0 to (a/a2)-1)

For an infinite number of input sets, however, I can't find anything, and the above kind of proof breaks down, because there must be an infinite number of a's in the sequences, and that means that there is no maximum a in them.

I'm afraid one of us has missed the point.

What is the intersection of S(2,1), S(3, 1), S(5, 1), S(7,1) ? Assume 2, 3, 5, 7 are the ONLY primes. Answer is {1}. This is NOT an element of the alleged topology. If you claim that that intersection has some other element — say 2*3*5*7+1 = 211 — then 211 is not divisible by any prime, so must itself be prime. That is a contradiction.

That argument works if there are only four primes. But the same argument, with the obvious modification, works if there five primes, or six. Or a thousand primes. Or a Googol of them.

Does the argument break down IF there are infinitely many primes? You betcha! THEN your topology IS a topology. But you cannot use the primes' infinitude: That's what you're trying to prove!

 

[Swammerdami]

So: Silence confirms agreement?

Resolved: that
This Board believes that Furstenberg's proof is just Euclid's proof with a lot of unnecessary "catsup."

 

[Jarhyn]

So, I very much appreciate your discussion of Euclid's proof, mostly on grounds that now I understand what that character in the Zeta function is supposed to mean.