BIT predicate¶

A binary relation that returns the zero-based j-th binary digit of a nonnegative integer i, enabling finite-set membership tests by bit position.

Version: v1 · 2026-10-07 · History
Domain-specific #: 13810
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Mathematical Logic, Arithmetic Coding → Mathematics
Aliases: BIT relation, Binary digit predicate

Core Idea¶

BIT(i,j) reads the binary digit at zero-based position j of a nonnegative integer i, counting from the least significant digit. Its value is floor(i/2^j) mod 2, equivalently (i >> j) & 1 for ordinary nonnegative-integer bit shifting. It is true when that digit is 1. The first argument is the number being read; the second is the position. Reversing them defines a different test.^[1]

Every nonnegative integer has finitely many 1 bits, so i can code the finite set S={j∈N:BIT(i,j)=1}; conversely i=Σ_{j∈S}2^j. This exact finite-support correspondence turns membership into a digit test. Recursive Ackermann coding reuses it at each set level, while an indexed software bitset exposes a related membership operation. Those uses share the test but differ in what the positions mean.^[1]^[2]

Structural Signature¶

Encoding number i: a nonnegative integer whose binary expansion carries finitely many nonzero positions. A negative signed-machine representation or arbitrary byte layout requires an extra convention.^[1]
Zero-based candidate position j: a nonnegative integer indexing from the least significant digit. In simple finite-subset coding j is the candidate element; in Ackermann coding j is the code of a candidate hereditarily finite member.^[1]
Binary decision rule: divide by 2^j, discard the fractional part, and take parity. The output is exactly 0 or 1; no comparison of decimal digits or similarity score is involved.^[1]
Interpretation boundary: a 1 digit can mean set membership, a software flag, or another assigned label. BIT itself fixes the arithmetic relation, not the semantics of a particular application.^[1]^[2]

The pair (i,j) and its order are constitutive. Replacing the arithmetic with a hash lookup, silently changing to one-based indexing, or asking whether i is a bit of j changes the object being described.

What It Is Not¶

BIT is not a unary predicate about a number in isolation: it needs both an encoding number and a position. It is not the whole finite set or the act of representing one, although its true positions can encode such a set. A bit pattern does not automatically define an undirected graph; adjacency would need a separate rule, including any needed symmetry convention.^[1]

Nor does finite-set coding make unrestricted complement a finite integer. The complement N\S of a finite S is generally infinite; a bitwise NOT or range flip represents complement only relative to a declared finite mask or interval. Claims about the expressive power of first-order logic with built-in BIT require a specified class of ordered structures and the exact theorem, not the digit formula alone.^[2]^[3]

Scope of Application¶

The arithmetic definition applies to i,j∈N with zero-based indexing and arbitrary-precision arithmetic in the mathematical model. A fixed-width word can implement it within that word's specified range. For finite-subset codes, i denotes exactly the set of its 1-bit positions. For pure hereditarily finite sets, apply the same finite-subset code recursively to member codes.^[1]

An API such as Java's BitSet uses a growable indexed bit vector rather than promising one fixed-size integer value. Its get(j) operation matches the membership test for the current set positions; OR and AND combine those positions as set union and intersection. A finite-range flip requires the caller to choose the range. No speed or storage bound follows from the abstract relation alone.^[2]

Clarity¶

For i=42, binary 101010, the 1 positions are 1, 3, and 5. Thus BIT(42,3)=1 and BIT(42,2)=0; the finite subset is {1,3,5}. The highest represented position is 5, but positions above it still return 0 in the unbounded natural-number definition. The formula is directional: BIT(3,42)=0, which is not a second way of asking whether 3 belongs to the set coded by 42.^[1]

The expression floor(i/2^j) mod 2 isolates the j-th bit because division shifts that bit to the units place and parity discards higher places. This is an arithmetic unpacking of binary expansion, not a separate empirical regularity.

Manages Complexity¶

A finite subset of N can be represented by one natural number without listing each element separately in the mathematical notation. Membership becomes a direct test of a declared position, and union/intersection correspond to OR/AND on the same position convention. This is an exact encoding of finite support, not a general claim that the integer is short: the singleton {N} requires the bit at N and therefore an N+1-digit binary representation.^[1]^[2]

The recursive hereditarily finite construction extends the same idea through nested sets. It replaces a tree of membership links with arithmetic codes, but the decoding rule and the distinction between a member and its code remain essential.^[1]

Abstract Reasoning¶

Choose nonnegative i and j, state that j is zero-based, and evaluate BIT(i,j)=floor(i/2^j) mod 2. If i is a simple finite-set code, conclude j∈S exactly when the result is 1. To combine two such sets, align their bit-position conventions and use OR for union or AND for intersection. To complement, first declare a finite universe U of positions and mask or flip only inside U.^[1]^[2]

For a pure hereditarily finite set x, Ackermann's recursive code is f(∅)=0 and f(x)=Σ_{a∈x}2^{f(a)}. Therefore BIT(f(x),f(a))=1 exactly when a∈x. Here the second argument is f(a), not an unencoded set a. That substitution is the step that makes the recursive membership relation arithmetic.^[1]

Knowledge Transfer¶

In Ackermann coding, the index is the numeric code of a potential member of a nested finite set. In a software BitSet, the index is an application-defined flag or integer key. Both use a zero-based position to answer a yes/no membership question. The interpretation of a position and the representation limits change, while the digit-test relation remains the common structure.^[1]^[2]

This transfer does not justify moving every theorem across settings. The hereditarily finite coding is a mathematical bijection under its recursive convention; a mutable software container has capacity and API semantics. A first-order structure with BIT has a specified universe and built-in relation; its logical consequences require those conditions.^[1]^[2]^[3]

Examples¶

Ackermann-coded membership. Tarau's finite-subset example sends {1,3,5} to 42. In the recursive pure hereditarily finite interpretation, 42 denotes a set whose member codes are 1, 3, and 5. For any candidate set a with f(a)=3, BIT(42,3)=1 proves a belongs to the set coded 42. It does not claim that the natural number 3, without the coding interpretation, is literally that member.^[1]

Indexed software flags. A Java BitSet with positions 1, 3, and 5 set returns true from get(3) and false from get(2). OR with a second BitSet adds its set positions; AND retains shared positions. Flipping positions within a chosen interval changes those flags only in that finite interval. The API example instantiates position, membership test, and bounded complement without requiring a single machine word.^[2]

Structural Tensions¶

Exact finite-support code versus unbounded complement. A finite integer can exactly answer membership for its finitely many 1 positions, including zeros at every higher position. But complement relative to all N turns almost all those zeros into ones, giving an infinite set that no finite binary integer encodes. The diagnostic question is: Which finite universe or index interval does “complement” mean here? With that range stated, a mask or finite-range flip is valid; without it, the transfer from set complement to bitwise NOT is incomplete.^[1]^[2]

Structural–Framed Character¶

Formal structure: BIT is a specified two-place truth relation with a binary arithmetic rule. Evaluative weight: a 1 digit means membership under a convention, not that the member is better. Human-practice dependence: users choose which object i encodes and what j names, while the mathematical bit test remains fixed. Institutional origin: Ackermann coding and a software bitset provide different operational settings rather than authorities defining a new digit value.^[1]^[2]

Vocabulary travel: “bit” in a machine word and in a natural-number expansion can refer to the same indexed binary position, subject to width and sign conventions. Import versus recognition: recognize BIT only when the first argument is the encoded number, the second is a zero-based bit position, and the result is the specified digit. Its character: structural-dominant. The arithmetic relation is portable across the two settings, while set membership and software flags require their own domain interpretation and representation conventions.^[1]^[2]

Structural Core vs. Domain Accent¶

The portable skeleton is a two-place relation that decides whether an indexed position is marked in a finite-support representation. The specific domain identity is stronger: the mark must be the j-th binary digit of nonnegative i under the stated orientation. A general Prime about relations covers the wider association pattern but does not itself supply base-two expansion, zero-based indexing, or Ackermann's recursive set code.^[1]

The two unlike cases, pure hereditarily finite sets and software bitsets, show useful transfer of the digit test. They do not by themselves promote BIT to a new substrate-independent Prime, because both inherit the same binary-position machinery. The live Relation Prime is the approved strict parent; the live Predicate Prime's current one-place frontmatter is a less exact genus for this two-place relation.^[1]^[2]

This entry is a kind of Relation.

The approved DAG edge is strict subsumption to Relation: BIT relates i and j by a determinate rule and adds a particular arithmetic membership condition. Predicate is a nearby term but its live identity emphasizes a property of one object, so it was declined as a second parent pending any future Prime clarification. Representation concerns the use of a code; representing sets is an application of BIT, not a necessary genus of the bare digit relation.^[1]

Relationships to Other Abstractions¶

Current abstraction BIT predicate Domain-specific

Parents (1) — more general patterns this builds on

BIT predicate is a kind of Relation Prime

BIT is a particular binary relation on nonnegative integers with a specified digit-membership rule.

Hierarchy path (1) — routes to 1 parentless root

BIT predicate → Relation

Neighborhood in Abstraction Space¶

BIT predicate sits in a sparse region of the domain-specific corpus (98^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Numeral Systems & Digit Algorithms (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Do not swap i and j, start counting bits from 1 without translating the formula, treat a coded member as its uncoded object, or infer unrestricted complement from a finite bit pattern. Do not identify a Java BitSet's current flags with a fixed-width signed integer without a declared conversion. BIT is the oriented binary-digit relation; its applications require extra conventions.^[1]^[2]

References¶

[1] Paul Tarau, A Functional Hitchhiker's Guide to Hereditarily Finite Sets, Ackermann Encodings and Pairing Functions (2008), arXiv:0808.0754, §3.1 PDF pp. 2–3 for set2nat, nat2set, the pure Ackermann recurrence, and the example 42↔{1,3,5}; §2 PDF p. 2 for least-significant-first bit notation. https://arxiv.org/pdf/0808.0754 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w

[2] Oracle, BitSet (Java Platform SE 8) (Java SE 8 API), class description and methods get(int), or(BitSet), and(BitSet), flip(int,int), and valueOf(long[]) for indexed membership, set operations, finite-range flip, and representation. https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] Albert Atserias and Phokion G. Kolaitis, First-Order Logic vs. Fixed-Point Logic in Finite Set Theory (LICS 1999), abstract on built-in BIT and ordered finite structures; cited only for the scope boundary, not for an unverified complexity-class equivalence. https://lics.siglog.org/archive/1999/AtseriasKolaitis-FirstOrderLogicvsFi.html registry ↩a ↩b