[math-fun] Constructing a set that isn't a congruence class
There are only countably many sets of natural numbers that form (the nonnegative part of) a congruence classes. Here's a natural way to list them as bit strings: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ... 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ... 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 ... 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 ... 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 ... 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 ... 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 ... 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 ... 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 ... 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ... 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 ... 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 ... 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 ... 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 ... 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ... ... We can use diagonalization to construct a set that isn't a congruence class: 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 ... Does this pattern continue? Jim Propp
=James Propp There are only countably many sets of natural numbers that form (the nonnegative part of) a congruence classes. Here's a natural way to list them as bit strings: [...] We can use diagonalization to construct a set that isn't a congruence class: 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 ... Does this pattern continue?
Not sure what you're asking. Your strings for congruence classes all have the form of isolated 1's separated by blocks on N 0's. Since the constructed string doesn't have that form it isn't a congruence class, regardless of how you generated it. It appears to have the alternating form 1 0, 2 1's, 3 0's, 4 1's, 5 0's and so on. Are you asking if the diagonal selection process from the array has this apparent structure in fact?
It turned out to be quite easy to prove once I looked at it the right way. It’s equivalent to the fact that n(n+1)/2 is 0 mod n iff n is odd. Jim Propp On Friday, June 22, 2018, James Propp <jamespropp@gmail.com> wrote:
On Friday, June 22, 2018, Marc LeBrun <mlb@well.com> wrote:
It appears to have the alternating form 1 0, 2 1's, 3 0's, 4 1's, 5 0's
and so on. Are you asking if the diagonal selection process from the array has this apparent structure in fact?
Yes.
Jim Propp
participants (2)
-
James Propp -
Marc LeBrun