Questions tagged [boolean-algebras]

A Boolean algebra is a commutative ring satisfying x²=x for every x, and sometimes required to have a unit; they have characteristic 2. For coding theory (notably dealing with subsets linear subspaces of spaces of Boolean functions), rather use the [coding-theory] or [linear-algebra] tag.

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

What's the shorest $k$-cnf formula in $n$ variables with exactly one satisfying assignment?

What's the shortest $k$-cnf formula in $n$ variables, measured by number of clauses, with exactly one satisfying assignment? The following construction achieves $n+2^k-k-1$ clauses. Let $$C_{b_1\cdots ...
1 vote
0 answers
42 views

Is a Boolean algebra with an order continuous topology a measure algebra?

Assume that $B$ is a complete boolean algebra endowed with a Hausdorff topology, with respect to which all operations on $B$ are continuous, $0$ has a base of full sets (recall that $A\subset B$ is ...
  • 5,057
1 vote
0 answers
50 views

Consequences of having unbounded points in a bornology

For a set $X$ a bornology $\mathcal{B}$ is essentially an ideal in the power set $\mathcal{P}(X)$. Many sources including Wikipedia state additional property that $X = \bigcup \mathcal{B}$. Call it a ...
1 vote
1 answer
100 views

Continuous surjection between spectra of commutative von Neumann algebras

Suppose that $V_1,V_2$ are two commutative von Neumann algebras and $V_1 \subset V_2$. Being in particular commutative $C^*$-algebras we have that $V_1 \cong C(X_1), V_2 \cong C(X_2)$ for some ...
  • 8,794
2 votes
2 answers
148 views

Maximal uncountable chains in ${\cal P}(\omega)$

Let ${\cal P}(\omega)$ denote the power-set of $\omega$. We order it by set inclusion $\subseteq$ and say that ${\cal C}\subseteq {\cal P}(\omega)$ is a chain if for all $A, B\in {\cal C}$ we have $A\...
2 votes
0 answers
66 views

Should we check for equivalence in Quine's method of simplifying Boolean functions?

I already asked this on MathStackExchange, but had no response. Now I've figured out it is more appropriate to ask such question on this site, since it is rather about further elaboration on a ...
  • 121
5 votes
1 answer
226 views

Boolean algebra of ambiguous Borel class

Suppose $X$, $Y$ are uncountable compact metric spaces and $\Delta^0_\xi(X)$, $\Delta^0_\xi(Y)$ ($2\le\xi\le\omega_1$) are the Boolean algebras of Borel sets of ambiguous class $\xi$. So for $\xi=2$ ...
1 vote
1 answer
180 views

Star-autonomous categories are categorifications of Boolean algebras?

I asked this question fourteen days ago on MathStackexchange (see here). I have not received any answers or comments until now. It seems to me that on MathStackexchange not many people are familiar ...
  • 445
2 votes
2 answers
134 views

Why is a Boolean algebra being $\kappa$-saturated upward closed in $\kappa$?

A Boolean algebra $B$ is defined (e.g. in Jech) to be $\kappa$-saturated if there is no partition $W$ of $B$ where $|W|=\kappa$. He seems to assume that this implies $|W|<\kappa$ for any partition ...
  • 1,189
1 vote
0 answers
65 views

Proof of the Local Deduction Theorem, for one of many logics

I'm looking for a proof of the Local Deduction Theorem for any one of many logics. That is, a proof of the statement: $\Sigma \cup \{\phi\} \models \psi$ iff for some positive $n,$ $\Sigma \models \...
  • 361
1 vote
1 answer
53 views

An exercise in fuzzy logics built from a t-norm [closed]

Consider the following t-norm: $$ a * b = \begin{cases} 2ab, &\quad\text{if }a, b\le1/2\\ \min\{a, b\} &\quad\text{otherwise} \end{cases} $$ We build from it the $\...
  • 361
1 vote
2 answers
95 views

The Boolean algebra of all almost invariant subsets of an uncountable locally finite group is contained in every Sub-Boolean that separates points

Let $G$ be a group. A subset $A\subset G$ is said to be almost right invariant if $A\Delta A\cdot g$ is finite for all $G$. The family of all almost right invariant subsets $\mathcal{B}_G$ of $G$ is a ...
4 votes
1 answer
231 views

Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

This question is a follow-up of this question. Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd. Question: Can we compute the exact minimum $$A:= \min_{u:\mathbb{...
  • 6,387
9 votes
1 answer
332 views

Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd. Is it possible that $$ \sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
  • 6,387
4 votes
1 answer
166 views

Generalized limits in Boolean algebras

Let $\mathbb{B}$ be an infinite $\sigma$-complete Boolean algebra. By $\mathbb{B}^\omega$ we denote the countable product of $\mathbb{B}$ with the coordinate-wise operations. Let us call a ...
1 vote
1 answer
91 views

Probability of two Boolean functions being equal expressed in terms of the maximum Fourier coefficient

This paper by Maslov et al. uses that the probability of two $n$-bit Boolean functions $l(x)$ and $g(x)$ being equal is bound in terms of $\hat{g}_\text{max}$, the largest Fourier coefficient of $g(x)$...
3 votes
0 answers
127 views

Boolean Algebra of size $2^{<\kappa}$ without an $\aleph_1$-complete ultrafilter

For this post we work only with cardinals that live below the first measurable. Assume that $\kappa$ is singular and $\kappa<2^{<\kappa}<2^\kappa$. Question: Is it possible to have a Boolean ...
0 votes
0 answers
39 views

Selectively countable Boolean algebras of sets (terminology)

I am interested in the name for the following property of a Boolean algebra $\mathcal A$ of subsets of a set $X$: $(\star)$ for any sequence $(A_n)_{n\in\omega}$ of pairwise disjoint nonempty sets in $...
  • 34.8k
2 votes
1 answer
100 views

Dedekind-MacNeille completion of ${\cal P}(\omega)/({\rm fin})$

Let ${\cal P}(\omega)/({\rm fin})$ be the quotient of the Boolean algebra ${\cal P}(\omega)$ where two sets are considered to be equivalent if they differ by a finite number of elements. It turns out ...
2 votes
2 answers
198 views

What to call a continuous function with preimage preserving nowhere-density?

Currently I am reading some basic literature on descriptive set theory and boolean algebras. And this comes out a lot, for example in results like: Let $X$ and $Y$ be topological spaces, and $f:X \to ...
1 vote
1 answer
221 views

Understanding Kelley's intersection number (Boolean algebras)

It is known that: Theorem (Kelley, 1959). There exists a finite, strictly positive, finitely additive measure on a Boolean algebra $A$ if and only if $A^+$ is the union of a countable number of ...
  • 11
3 votes
1 answer
118 views

Existence of a quasi-open (a.k.a semi-open) map into a Cantor cube

Recall that a topological space is extremally disconnected if the closure of any open set is open. A continuous map is quasi-open if it maps nonempty open sets onto sets with nonempty interior. For ...
  • 5,057
0 votes
1 answer
130 views

$\mathbb R$ and $\mathbb F_2$ rank in boolean matrix product

By rank I imply rank over reals ($\mathbb R$). I consider two $n\times n$ matrices $A,B$ having entries in $0/1$. The product below follows usual matrix product rules except $xy$ is $AND(x,y)$ and $x+...
1 vote
1 answer
113 views

Density and compactness of Boolean embeddings

Let A and B be Boolean algebras and $h:A\rightarrow B$ a Boolean embedding. If every element of $B$ can be expressed both as a join of meets and as a meet of joins of elements in $h(A)$, then the ...
  • 151
-1 votes
1 answer
104 views

A complete Boolean algebra on a function space

If $(B_1, \cdot_1, +_1, -_1)$ is a complete atomic Boolean algebra (where the induced partial order is $\leq_A$), and $(B_2, \cdot_2, +_2, -_2)$ is a complete atomic algebra (where the induced partial ...
  • 617
15 votes
1 answer
352 views

What are internal complete atomic boolean algebras, intuitively?

The category of complete atomic boolean algebras $\mathbf{CABA}$ is equivalent to $\mathbf{Set}^{\mathrm{op}}$ via $$\mathbf{Set}^{\mathrm{op}} \to \mathbf{CABA}, ~ X \mapsto (P(X),\bigcup,\bigcap).$$ ...
5 votes
2 answers
254 views

Self-homeomorphism of Stone-Čech boundary with an isolated fixed point

$\DeclareMathOperator\bso{\beta^*\!\omega}\DeclareMathOperator\Homeo{Homeo}$Let $\bso$ be the complement of the countable discrete space $\omega$ in its Stone-Čech compactification $\beta\omega$ (some ...
  • 52.7k
12 votes
2 answers
783 views

Analytical origins of the Stone duality

I've asked this question in the HSM community, but by the nature of my question, some user told me to ask this question here. This is the original post https://hsm.stackexchange.com/q/13087/14296 ...
  • 151
12 votes
0 answers
347 views

An internal notion of freeness for complete Boolean algebras

Background and Definition Gaifman and Hales showed that there are no infinite free complete Boolean algebras. But let a complete Boolean algebra $B$ be internally free if there is a set $X\subseteq B$ ...
8 votes
0 answers
127 views

On the number of Reed–Muller codewords with no consecutive ones

$\DeclareMathOperator\RM{RM}\DeclareMathOperator\Eval{Eval}$Consider the polynomial ring $\mathbb{F}_2[x_1,x_2,\dotsc,x_m]$ and let $f\in \mathbb{F}_2[x_1,x_2,\dotsc,x_m]$. Let us now fix a Gray ...
1 vote
0 answers
111 views

Minimizing all aspects of the definition of Boolean algebra

There are many equivalent ways to describe Boolean algebras. There are a number of different ways to "minimize" the description. We can: Minimize the number of function symbols. Minimize ...
  • 15.4k
6 votes
0 answers
127 views

Rigid boolean inclusions?

A boolean algebra $B$ is rigid if it has no nontrivial automorphisms and atomless if it has no minimal nonzero elements. $A \subseteq B$ is a complete boolean inclusion if $B$ is complete and $A$ is a ...
6 votes
0 answers
93 views

Computing the zeta transform of a Boolean function: Space-time tradeoff

Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by $$\zeta_f(y) :...
  • 71
5 votes
1 answer
223 views

Boolean valued models in a general setting

It is well known that Boolean valued models play significant roles for set-theoretic purposes. But how well-studied are Boolean valued models in a more general setting, as models for random first-...
7 votes
1 answer
360 views

A set theoretic question arising from trying to understand a sheaf cohomology question

I'm trying to understand the footnote to Example 5.3 in Wiegand - Sheaf cohomology of locally compact totally disconnected spaces which is about constructing a locally compact Hausdorff and totally ...
8 votes
1 answer
332 views

Intuition behind Boolean-valued models of set theory

$\DeclareMathOperator\Card{Card}$The book Forcing Eine Einführung in die Mathematik der Unabhängigkeitsbeweise by Hoffmann provides an intuition behind boolean valued models of set theory which I will ...
  • 123
5 votes
1 answer
310 views

Is the Pierce spectrum useful elsewhere in Mathematics?

In Borceaux and Janelidze's Galois Theories, a construction of the Pierce spectrum is given. It is the poset of ideals in a Boolean ring. It's construction is reminiscent of the Zariski spectrum in ...
5 votes
1 answer
266 views

Complete Boolean algebras of subsets of $\mathbb N$

Let $\mathfrak A$ be a subset of $\mathrm{Pow}(\mathbb N)$, the powerset of $\mathbb N$. Assume that $\mathfrak A$ is a complete Boolean algebra in the induced order, i.e., the inclusion order. Does ...
7 votes
1 answer
196 views

Functions on Stone spaces as "enveloping algebra" of Boolean algebra

I'm looking for references for the following closely related facts: Given a Boolean algebra $B$, I denote by $\mathbb{Z}[B]$ the free ring generated by symbols $e_b$ such that $e_b e_{b'} = e_{b \cap ...
  • 33.5k
3 votes
1 answer
118 views

What is the name for Boolean algebra's version of $\models$ between sets of identities and identities?

On p62 in Schaum's Outline of Theory and Problems of Boolean Algebra and Switching Circuits by Elliott Mendelson (1970), Part (b) of the corollary says that if an identity is satisfied by some ...
  • 337
3 votes
1 answer
175 views

Boolean ring of unitary divisors / Structure of unitary divisors?

I hope this question is appropriate for MO: Let $n$ be a natural number, $U_n := \{ d | d \text{ divides } n, \gcd(d,n/d)=1\}$ be the set of unitary divisors. We can make $U_n$ to a boolean ring: $$a \...
's user avatar
6 votes
1 answer
274 views

Can this ultrafilter convergence condition be expressed as a compactness condition?

Suppose that $X$ is a topological space. Let us say that an ultrafilter $\mathcal U$ on the Boolean algebra $C_X$ of clopen subsets of $X$ is partition-prime if whenever $X = \amalg_{i \in I} X_i$ is ...
2 votes
0 answers
90 views

Projective objects for compact po-spaces

Let us consider the following definition: a compact po-space is a pair $(X,\leq)$ where $X$ is a compact space and $\leq$ is an order, closed on $X^2$. Then, we can consider the category $KPoSp$ whose ...
  • 21
40 votes
1 answer
2k views

In the category of sigma algebras, are all epimorphisms surjective?

Consider the category of abstract $\sigma$-algebras ${\mathcal B} = (0, 1, \vee, \wedge, \bigvee_{n=1}^\infty, \bigwedge_{n=1}^\infty, \overline{\cdot})$ (Boolean algebras in which all countable joins ...
  • 92.7k
2 votes
2 answers
238 views

Existence of measurable "inclusion" into Euclidean space

Let $(\Omega,\mathfrak{F})$ be a measurable space. When does there exist an injective measurable function $f:(\Omega,\mathfrak{F})\to (\mathbb{R}^n,B(\mathbb{R}^n))$ to some Euclidean space, here $B(\...
  • 5,064
2 votes
1 answer
89 views

Decreasing sequences in a finitely generated closure algebra

I am interested in finitely generated closure algebras (as a special case of Heyting algebras), and in decreasing sequences of elements within such an algebra that have no lower bound. Call two ...
15 votes
1 answer
876 views

What is a module over a Boolean ring?

Recall that a (unital) Boolean ring is a (unital) commutative ring $A$ where every element is idempotent; it follows that $A$ is of characteristic 2. There is an equivalence of categories between ...
  • 51k
6 votes
1 answer
249 views

Reduced products of complete Boolean algebras

I expect that complete Boolean algebras are not closed under reduced products modulo $\kappa$-complete filters, for any regular cardinal $\kappa$. Is it true? And, is a reference for this?
8 votes
0 answers
258 views

Elementary equivalence between $n\mapsto n+1$ and its inverse on the Stone-Čech remainder?

Consider structures $(A,f)$ encoding a Boolean algebra $A$ endowed with an automorphism $f$. There is an obvious notion of isomorphism between such structures. Consider the endomorphism $\hat{\Phi}$ ...
  • 52.7k
12 votes
1 answer
363 views

Near permutation $n\mapsto n+1$ not conjugate to its inverse on the Stone-Čech remainder?

Let $\beta\omega$ be the Stone-Čech compactification of the discrete infinite countable space $\omega$, and $\beta^*\omega=\beta\omega\smallsetminus \omega$ is the Stone-Čech remainder. The map $j:n\...
  • 52.7k

1
2 3 4 5