Binary combinatory logic

Template:Expert-subject Closure with a twist is a property of subsets of an algebraic structure. A subset $Y$ of an algebraic structure $X$ is said to exhibit closure with a twist if for every two elements

y_{1},y_{2}\in Y

there exists an automorphism $\phi$ of $X$ and an element $y_{3}\in Y$ such that

y_{1}\cdot y_{2}=\phi (y_{3})

where " $\cdot$ " is notation for an operation on $X$ preserved by $\phi$ .

Two examples of algebraic structures with the property of closure with a twist are the cwatset and the GC-set.

Cwatset

In mathematics, a cwatset is a set of bitstrings, all of the same length, which is closed with a twist.

If each string in a cwatset, C, say, is of length n, then C will be a subset of Z₂ⁿ. Thus, two strings in C are added by adding the bits in the strings modulo 2 (that is, addition without carry, or exclusive disjunction). The symmetric group on n letters, Sym(n), acts on Z₂ⁿ by bit permutation:

p((c₁,...,c_n))=(c_p(1),...,c_p(n)),

where c=(c₁,...,c_n) is an element of Z₂ⁿ and p is an element of Sym(n). Closure with a twist now means that for each element c in C, there exists some permutation p_c such that, when you add c to an arbitrary element e in the cwatset and then apply the permutation, the result will also be an element of C. That is, denoting addition without carry by +, C will be a cwatset if and only if

\ \forall c\in C:\exists p_{c}\in {\text{Sym}}(n):\forall e\in C:p_{c}(e+c)\in C.

This condition can also be written as

\ \forall c\in C:\exists p_{c}\in {\text{Sym}}(n):p_{c}(C+c)=C.

Examples

All subgroups of Z₂ⁿ — that is, nonempty subsets of Z₂ⁿ which are closed under addition-without-carry — are trivially cwatsets, since we can choose each permutation p_c to be the identity permutation.

An example of a cwatset which is not a group is

F = {000,110,101}.

To demonstrate that F is a cwatset, observe that

F + 000 = F.

F + 110 = {110,000,011}, which is F with the first two bits of each string transposed.

F + 101 = {101,011,000}, which is the same as F after exchanging the first and third bits in each string.

A matrix representation of a cwatset is formed by writing its words as the rows of a 0-1 matrix. For instance a matrix representation of F is given by

F={\begin{bmatrix}0&0&0\\1&1&0\\1&0&1\end{bmatrix}}.

To see that F is a cwatset using this notation, note that

F+000={\begin{bmatrix}0&0&0\\1&1&0\\1&0&1\end{bmatrix}}=F^{id}=F^{(2,3)_{R}(2,3)_{C}}.

F+110={\begin{bmatrix}1&1&0\\0&0&0\\0&1&1\end{bmatrix}}=F^{(1,2)_{R}(1,2)_{C}}=F^{(1,2,3)_{R}(1,2,3)_{C}}.

F+101={\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}}=F^{(1,3)_{R}(1,3)_{C}}=F^{(1,3,2)_{R}(1,3,2)_{C}}.

where $\pi _{R}$ and $\sigma _{C}$ denote permutations of the rows and columns of the matrix, respectively, expressed in cycle notation.

For any $n\geq 3$ another example of a cwatset is $K_{n}$ , which has $n$ -by- $n$ matrix representation

K_{n}={\begin{bmatrix}0&0&0&\cdots &0&0\\1&1&0&\cdots &0&0\\1&0&1&\cdots &0&0\\&&&\vdots &&\\1&0&0&\cdots &1&0\\1&0&0&\cdots &0&1\end{bmatrix}}.

Note that for $n=3$ , $K_{3}=F$ .

An example of a nongroup cwatset with a rectangular matrix representation is

W={\begin{bmatrix}0&0&0\\1&0&0\\1&1&0\\1&1&1\\0&1&1\\0&0&1\end{bmatrix}}.

Properties

Let C $\subset$ Z₂ⁿ be a cwatset.

The degree of C is equal to the exponent n.

The order of C, denoted by |C|, is the set cardinality of C.

There is a necessary condition on the order of a cwatset in terms of its degree, which is

analogous to Lagrange's Theorem in group theory. To wit,

Theorem. If C is a cwatset of degree n and order m, then m divides 2ⁿn!

The divisibility condition is necessary but not sufficient. For example there does not exist a cwatset of degree 5 and order 15.

Generalized cwatset

In mathematics, a generalized cwatset (GC-set) is an algebraic structure generalizing the notion of closure with a twist, the defining characteristic of the cwatset.

Definitions

A subset H of a group G is a GC-set if for each h ∈ H, there exists a $\phi _{h}$ ∈ Aut(G) such that $\phi _{h}$ (h) $\cdot$ H = $\phi _{h}$ (H).

Furthermore, a GC-set H ⊆ G is a cyclic GC-set if there exists an h ∈ H and a $\phi$ ∈ Aut(G) such that H = { $h_{1},h_{2},...$ } where $h_{1}$ = h and $h_{n}$ = $h_{1}$ $\cdot$ $\phi$ ( $h_{n-1}$ ) for all n > 1.