Talk:BIT predicate

Ackermann coding

@Russ Woodroofe: Where else do you propose putting the definition of Ackermann coding, which was already described (albeit incorrectly) and discussed in the history section, where I put it? 2601:547:501:8F90:75EF:C82F:5D9:1C9 (talk) 23:23, 29 January 2023 (UTC)

I think that per WP:AUDIENCE, to the extent possible, this article should be readable by beginning-university-level computer science students, because using numbers to encode sets of small integers or other systems of discrete values and using the BIT predicate as a membership test is an important and insufficiently well-known programming technique. So I would definitely like to see an accessible explanation of how this predicate can be used as a set membership test for subsets of a sequence $x_{0},x_{1},\dots$ encoded as $\{\dots ,x_{i},x_{j},\dots \}\mapsto \cdots +2^{i}+2^{j}+\cdots$. The recursive encoding of hereditary finite sets is a specific example of this encoding, for a specific recursively-defined sequence of values (the hereditary finite sets), but the recursive nature of the sets and the notation-heavy treatment of the recent attempts to explain it make it likely extremely heavy going for such students. So I would prefer to see only a brief mention of that part, with a link to where to find more, rather than an in-depth treatment of this subject here. Beyond its historical value, this encoding is interesting for the fact that it provides an isomorphism between the binary relations of integers under the bit predicate and hereditarily finite sets under set membership, and that should also probably be mentioned somewhere (if written briefly and accessibly, rather than in notation-heavy detail, this could also be in the history). —David Eppstein (talk) 23:40, 29 January 2023 (UTC)

PS I have made an attempt at more of an explanation of this technique, in the coding section. —David Eppstein (talk) 00:12, 30 January 2023 (UTC)

I agree that a sentence starting "Formally" does not belong in the history section, although a more informal and approachable description could go there. Other math articles often have a "Precise definition" section (not at the top of the article), where they go into some more formal and notation-heavy details. Perhaps in an article tending more towards computer science, a better section heading would be "Formal viewpoint". IP editor, what is it that you're really trying to do here? Russ Woodroofe (talk) 09:42, 30 January 2023 (UTC)

I definitely agree that the attempted addition from that editor was overly technical and had no place in the history section. What has currently been added to the article seems to cover most it, doesn't it? One think that may have been lost in the shuffle is the statement that "The Ackermann coding is a primitive recursive function" (with the reference), what actually did not belong in the history section either. Someone may want to add it back to the Set theory section probably. PatrickR2 (talk) 19:51, 30 January 2023 (UTC)

Actually, after looking at it in more detail, the explanation of the Ackermann coding in the Hereditarily finite set article seems a little easier to follow, especially as they have a good illustrative example. Should all the Ackermann encoding info be removed from BIT predicate and instead refer to the other article? PatrickR2 (talk) 19:59, 30 January 2023 (UTC)

The version of this info I just added to the applications section, you mean? —David Eppstein (talk) 20:31, 30 January 2023 (UTC)

@Russ Woodroofe: @David Eppstein: @PatrickR2: How about creating a separate article titled Ackermann coding that is specifically about the set-theoretic concept, linking BIT predicate and hereditarily finite set to it and viceversa? (Also, the Implementation section contains an error due to not accounting for multiplicity, e.g. $\{0\}=\{0,0\}$.) 2601:547:501:8F90:212A:34FB:FECC:443F (talk) 00:39, 31 January 2023 (UTC)

The simple recursive definition is already in this article now, in a more readable form that does not bring in technical and unnecessary concepts like the Von Neumann hierarchy. "Account for multiplicity"??? Sets have no multiplicity. Are you thinking of multisets? —David Eppstein (talk) 01:53, 31 January 2023 (UTC)

@David Eppstein: The simple recursive definition is already in this article The recursive definition of the inverse function (the other direction of the coding) is missing. "Account for multiplicity"??? Sets have no multiplicity. Are you thinking of multisets? I explicitly said $\{0\}=\{0,0\}$, not the opposite. Note the equals sign. That sets have no multiplicity is precisely my point. The article currently says

When such a bit array is interpreted as a binary number, the set $\{i,j,k,\dots \}$ is represented as the binary number $2^{i}+2^{j}+2^{k}+\cdots$.

$\{0,0\}=\{0\}$ but $2^{0}+2^{0}\neq 2^{0}$. It must be specified that the $i,j,k,\ldots$ are all distinct. One more thing: You incorrectly flipped the relation in the statement about modelling ZF-Inf. It is the converse relation of BIT that models $\in$, not BIT itself. (Note that the arguments are also flipped for the Rado graph relation <.) This could be avoided by defining BIT in the opposite way throughout the article. ("BIT(i, j) iff the ith bit of j is 1.") 2601:547:501:8F90:212A:34FB:FECC:443F (talk) 05:41, 31 January 2023 (UTC)

If a set is written as {i,j,k} I think it is implicit that these values are distinct. We could make it explicit: "the set $\{i,j,k,\dots \}$ (for distinct $i,j,k,\dots$)". —David Eppstein (talk) 07:53, 31 January 2023 (UTC)

@David Eppstein: (and IP guy): The article is starting to look better now, especially with the broad Applications section. But the lead is misleading: the BIT predicate or Ackermann coding, ..., is a predicate that tests ... This puts the BIT predicate itself and the Ackermann coding at the same level and even equates them to the same thing. But they are different things. The BIT predicate is a simple predicate with two variables that can itself be used in many applications in computer science and math, as explained in the Applications section. The Ackermann coding really means the Ackermann coding of the hereditarily finite sets. It can be expressed by means of the BIT predicate, in the same way that the Rado graph or private information retrieval make use of it. But they are not the same thing at all. The Ackermann coding is tied up with hereditarily finite sets and I think that's where more information about it should reside. It's ok to make mention of it in the BIT predicate article, in the same way that the Rado graph is mentioned here. But for example the last paragraph added by IP guy about ZF set theory without thee axiom of infinity is all interesting, but should not be in this article; it should be added to the HF article instead. In summary, we should deemphasize Ackermann coding in this article, remove mention of it in the lead, edit the Ackermann coding redirect to point to the HF article (and expand the HF article as needed). (let me know if you agree and want me to take a stab at some cleanup) PatrickR2 (talk) 15:27, 31 January 2023 (UTC)

@PatrickR2: This is why I suggested creating a separate article called Ackermann coding (linking both BIT predicate and hereditarily finite sets to it and viceversa). It'll help keep things more organized. 2601:547:501:8F90:78E0:1437:F355:228B (talk) 17:37, 31 January 2023 (UTC)

It doesn't look to me like there is quite enough to justify a separate article (although I don't feel very strongly). Perhaps, however, instead of having Ackermann coding redirect to the top of this article here, it could redirect to the Set theory subheading or similar (with Ackermann coding in bold, as per WP:R#ASTONISH)? I'll make the side comment that the Ackermann coding might also be mentioned at Heyting arithmetic, although I'm not positive if this is talking about the same thing or not. Russ Woodroofe (talk) 19:29, 31 January 2023 (UTC)

I feel strongly that (at least the topic discussed here so far) Ackermann coding is really about a way to encode hereditarily finite sets as integers, and as such is inextricably tied up with HF sets and therefore should not be a separate article. Its purpose is really in inferring properties of HF sets. The HF article now has a section "Ackermann coding" and that should be expanded. PatrickR2 (talk) 20:03, 31 January 2023 (UTC)

Side note: The HF sets are a topic of little interest to first year computer science undergrads (and even later, only more theoretically minded CS students would take an interest in it). So we won't have the need to dumb it down for them. PatrickR2 (talk) 20:07, 31 January 2023 (UTC)

Actually, what do you guys mean by "Ackermann coding"? Do you mean "Ackermann coding of HF sets" as we have been discussing, or do you mean something else? PatrickR2 (talk) 20:21, 31 January 2023 (UTC)

@Russ Woodroofe: @PatrickR2: I moved the content about Ackermann coding to Hereditarily_finite_set#Ackermann_coding. Can we redirect Ackermann coding to the latter? 2601:547:501:8F90:588C:22CB:8445:66EC (talk) 05:49, 2 February 2023 (UTC)

This looks good to me. Please do. PatrickR2 (talk) 20:57, 2 February 2023 (UTC)

IP editor, is there a textbook type source (or other secondary source) for the Ackermann material over at hereditarily finite set? The material looks more-or-less fine to me, but the only source I see is the original article of Ackermann, a primary source. Russ Woodroofe (talk) 00:25, 3 February 2023 (UTC)

I'm obviously not the IP editor, but I think this looks like an adequate textbook source:

Omodeo, Eugenio G.; Policriti, Alberto; Tomescu, Alexandru I. (2017), "3.3: The Ackermann encoding of hereditarily finite sets", On Sets and Graphs: Perspectives on Logic and Combinatorics, Springer, pp. 70–71, doi:10.1007/978-3-319-54981-1, ISBN 978-3-319-54980-4, MR 3558535

It calls it the "Ackermann encoding" rather than "Ackermann coding"; that might be more common. —David Eppstein (talk) 02:19, 3 February 2023 (UTC)

GA Review

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

This review is transcluded from Talk:BIT predicate/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Frzzl (talk · contribs) 22:23, 3 August 2023 (UTC)

GA review (see here for what the criteria are, and here for what they are not)

1. It is reasonably well written.

   a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists):

   see below

2. It is factually accurate and verifiable.

   a (reference section): b (inline citations to reliable sources): c (OR): d (copyvio and plagiarism):

   Notes and Refs are formatted fine, couldn't find any issues with OR. Earwig comes up with 2.0%, so no issues there. Source checks below.

3. It is broad in its coverage.

   a (major aspects): b (focused):

   Article covers the history, meaning, and uses. I think that fits the scope well, and it doesn't digress.

4. It follows the neutral point of view policy.

   Fair representation without bias:

   couldn't find any problems here

5. It is stable.

   No edit wars, etc.:

   I think any sort of edit war on this article would be difficult to come about.

6. It is illustrated by images and other media, where possible and appropriate.

   a (images are tagged and non-free content have non-free use rationales): b (appropriate use with suitable captions):

   Only image is created by the nominator, no licensing problems.

7. Overall:

   Pass/Fail:

Review

Hello! I'm going to take on this review; I think I can just about wrap my head around the maths in this one! I should be able to start either tomorrow or overmorrow - the article looks to be in good shape so with luck this should be rather swift.  Frzzl  talk; contribs  22:23, 3 August 2023 (UTC)

Ok, thanks! I should have more time to respond beginning Sunday. —David Eppstein (talk) 23:23, 3 August 2023 (UTC)

Right, I should start off with an apology for taking such a horrendously long time to get around to this review - life got hectic over the last few days. That aside, here are some points on content; I'll do a source check after these to pass the article.

Content

• Here the bits of i are numbered from the low-order bits to high-order bits in the binary representation of i, with the ones bit being numbered as bit 0. The subexpression i>>j shifts these bits so that bit i is shifted to position 0, and the subexpression &1 masks off the remaining bits, leaving only the bit in position 0. - The first sentence is giving the impression that the usage of the expression numbers the bits of i - surely a binary number would be initialised with its bits already in this order? Can we also link Binary shift and Bitmask?
  • This comment caused me to realize that the "description" section was missing a brief gloss of binary notation and a definition from it of the bit predicate, which I added at the start of the section. This caused the quoted sentence to become redundant, and I removed it. Shift was already linked, in the previous sentence. I added the link to mask, since it is not the same as the link to bitwise and from the previous sentence. —David Eppstein (talk) 00:04, 11 August 2023 (UTC)
• Link Computer security in #Private information retrieval
  • Done. —David Eppstein (talk) 23:49, 10 August 2023 (UTC)
• Richard Rado in 1964 used the BIT predicate to construct the infinite Rado graph. - this sounds fairly unnatural to me, can we switch it for something more along the lines of In 1964, the German-British mathematician Richard Rado...?
  • Done. —David Eppstein (talk) 23:49, 10 August 2023 (UTC)
• Finally, link Isomorphism just to be on the safe side.
  • Done. —David Eppstein (talk) 23:49, 10 August 2023 (UTC)

These are tiny points because the article is very good. I'll go through the sources once these are addressed.  Frzzl  talk; contribs  19:43, 9 August 2023 (UTC)

• @Frzzl: Ok, I think I've handled these; please take another look. —David Eppstein (talk) 00:04, 11 August 2023 (UTC)

  OK, happy with the content.  Frzzl  talk; contribs  09:53, 12 August 2023 (UTC)

Source checks

Status:  Done

• Some of the refs need moving around, for example in the first paragraph of the History section; I don't think that source 2 can be used to cite the bit about membership testing - the first sentence should be cited by 2 and the second by 1.

Sources I've verified (from rev 1169738141) 1, 2, both uses of 6, 10, 11 13, 17 (it's not explicit, but I'm fine with it) - so, the article is verifiable.

The referencing for the Notes is on the whole formatted well, no problems there; once you've moved the refs for that paragraph around, I can pass the article :D  Frzzl  talk; contribs  10:25, 12 August 2023 (UTC)

Ok, I changed the first paragraph of history so that the membership testing is sourced only to Ackermann. I left both references on the sentence "The BIT predicate was first introduced in 1937 by Wilhelm Ackermann" since one of them is the original reference by Ackermann and the other one is used here as a secondary source for Ackermann being the one to introduce it. Were there any other similar issues? —David Eppstein (talk) 19:47, 13 August 2023 (UTC)

No others as far as I can tell, so I'll pass the article. Thanks for the article, it was a pleasure to work with you!  Frzzl  talk; contribs  10:36, 14 August 2023 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.