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
2 votes
0 answers
69 views

Normal form of boolean expressions linear/affine w.r.t. conjunction and disjunction

$\DeclareMathOperator\Bool{Bool}$I am interested in boolean expressions that are linear/affine in the following sense. Let $\Bool(X)$ be the free boolean algebra over the set $X$. We can consider the ...
18 votes
3 answers
2k views

How do I apply the Boolean Prime Ideal Theorem?

I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be ...
1 vote
1 answer
161 views

Distributive sublattices of atomistic ortholattices

Let $L$ be an atomistic ortholattice (i.e. every element can be written as a join of atoms) with top and bottom elements 0 and 1, and let $M$ be a distributive atomic sub-ortholattice of $L$. Is $M$ ...
3 votes
0 answers
62 views

Fast checking that a system of polynomial equations is satisfiable over $\mathbb{F}_2$

I have a (fairly large) system of polynomial equations, of the form $$ c_1d_1=0,\ c_1d_2+c_2d_1=0,\ldots $$ (In case it is relevant, all the polynomials are homogeneous of degree 2, except for exactly ...
5 votes
1 answer
198 views

On the number of complete Boolean algebras

In their 1972 paper On the number of complete Boolean algebras Monk and Solovay showed that if $\lambda$ is an infinite cardinal, then there are $2^{2^\lambda}$ many isomorphism types of complete ...
2 votes
1 answer
375 views

Extending a complete lattice to get a "nice" Boolean lattice

Suppose we have a complete lattice. Which additional axioms (e.g. distributivity axioms) are needed to obtain a Boolean lattice in which $\text{complement}(a) = \text{lub}\{b \;|\; b \wedge a = \text{...
10 votes
1 answer
343 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}$ ...
14 votes
2 answers
481 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\...
3 votes
0 answers
95 views

Positive boolean satisfiability problem : finding minimal solutions

Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals. For every assignment of the variables which ...
1 vote
1 answer
206 views

Zero divisors in the boolean polynomial ring $\mathbb{F}_2[x_1,x_2,...,x_n]/(x_1^2-x_1,x_2^2-x_2,...x_n^2-x_n)$

Related to this question. Let $n$ be positive integer and let $K$ be the boolean polynomial ring $\mathbb{F}_2[x_1,x_2,...,x_n]/(x_1^2-x_1,x_2^2-x_2,...x_n^2-x_n)$. For all $a$ in $K$ we have $a= -a$ ...
3 votes
0 answers
109 views

Do coproducts injections of Heyting algebras have left and right adjoints?

Given two Heyting algebras $A$ and $B$, let $A+B$ be their coproduct in the category of Heyting algebras. Is it true that the inclusion $A → A+B$ always has a left and a right adjoint ? (Actually, I ...
5 votes
0 answers
198 views

Classical first-order model theory via hyperdoctrines

I have been reading this discussion by John Baez and Michael Weiss and I find this approach to model theory using boolean hyper-doctrines very interesting. One of their goal was to arrive at a proof ...
3 votes
1 answer
180 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 ...
1 vote
2 answers
168 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\mathbin\Delta A\cdot g$ is finite for all $G$. The family of all almost right invariant subsets $\mathcal{B}_G$ of $...
9 votes
1 answer
351 views

Are the Boolean algebras ${\cal P}(\omega)/(\text{fin})$ and ${\cal P}(\omega)/(\text{thin})$ isomorphic?

A set $A\subseteq \omega$ is said to be thin if $$\lim\sup_{n\to\infty}\frac{|A\cap \{0,\ldots, n\}|}{n+1} = 0.$$ We say for $A, B\subseteq \omega$ that $A\simeq_\text{fin} B$ if the symmetric ...
4 votes
1 answer
303 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 \...
2 votes
0 answers
176 views

Truncating the high degree part of a positive boolean function doesn't change the distance to positive functions too much

Given $\displaystyle n\in\mathbb{Z}^{+}$, suppose $\displaystyle f:\{-1,1\}^n\to[0,1], $ then $f$ has a Fourier expansion: $\displaystyle f(x)=\sum_{S\subseteq[n]} \tilde{f}(S)x^S,$ where $\...
0 votes
0 answers
35 views

Consider the probability of connecting the terminal vertices using Binary Decision Diagram with length constraint

Definitions Given an undirected graph $G=(V,E,p),p:E \to [0,1]$ where $V$ is the set of vertices, $E$ is the set of edges and $m=|E|$, and $p$ represents the probability that an edge functions. A set ...
3 votes
0 answers
126 views

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

I already asked this on Math Stack Exchange, 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 ...
13 votes
1 answer
262 views

Can any poset of cardinality $\leq 2^{\aleph_0}$ be embedded in ${\cal P}(\omega)/(\text{fin})$?

We endow ${\cal P}(\omega)$ with an equivalence relation by saying that $A\simeq_{\text{fin}} B$ iff the symmetric difference $A\Delta B$ is finite. The resulting set of equivalence classes is denoted ...
1 vote
1 answer
117 views

Extremally disconnected rigid infinite Hausdorff compacta(?)

Question: does there exist an extremally disconnected infinite Hausdorff compact space $\ X\ $ such that the only homeomorphism $\ h: X\to X\ $ is the identity homeomorphism $\ h=\mathbb I_X:\ X\to X\...
10 votes
3 answers
725 views

When are two forcing posets "the same"?

Let $B$ and $C$ be complete Boolean algebras. To avoid triviality I may also want them to be atomless. For $b\in B$ nonzero, denote $B\upharpoonright b=\{p\in B:p\leq b\}$, which can be viewed as a ...
1 vote
0 answers
105 views

An algebra with two multiplications, based on series-parallel diagrams?

Here is a commutative, unital, associative algebra $\mathcal{F}$ with two ways to multiply. The multiplications come from a construction with Boolean operations and series-parallel diagrams. I want ...
12 votes
5 answers
4k views

Examples for "nice" Boolean algebras that are not complete or not atomic

A Boolean algebra may, or may not, be complete (i.e, any set of elements has a sup and an inf) or atomic (i.e., every element is a sup of some set of atoms). Boolean Algebras that are complete as ...
7 votes
1 answer
225 views

Formulas that are valid simultaneously in a power set Boolean algebra $B$ and the 2-element Boolean algebra $\mathbf2$ [duplicate]

Note 1. Early I posted a related question Set-theoretic tautologies. But the answer did not contain any concrete references to the literature. So I posted this, more precisely formulated question, ...
-1 votes
1 answer
58 views

The existence of a maximal “cross-sectional” filter on the Boolean algebra of measurable subsets of [0, 1] modulo almost everywhere equivalence

Let $\mathcal{B}([0, 1])$ be the Boolean algebra of measurable subsets of $[0, 1]$ modulo almost everywhere equivalence, i.e., two measurable sets which differ only by a Lebesgue null set are ...
6 votes
1 answer
349 views

Is every homogeneous poset a lattice?

A poset $(P,\leq)$ is homogeneous if $P\cong [a,b]$ for all $a,b\in P$ with $a<b$ (where $[a,b] := \{x\in P: a\leq x\leq b\}$). Examples of homogeneous posets include $[0,1]$, $[0,1]\cap \mathbb{Q}$...
4 votes
1 answer
255 views

Is ${\cal P}(\omega)/\text{(fin)}$ a fractal poset?

If $(P,\leq)$ is a partially ordered set and $a,b\in P$ we set $[a,b]:=\{x\in P: a\leq x\leq b\}$. We say that $P$ is fractal if whenever $a,b\in P$ and $[a,b]$ contains more than one element, then $[...
4 votes
1 answer
383 views

Boolean algebra of the lattice of subspaces of a vector space?

Recall that a Boolean algebra is a complemented distributive lattice. The set of subspaces of a vector space comes very close to being a boolean algebra. It satisfies all the required properties, ...
3 votes
1 answer
179 views

Results on Boolean matrices

Matrices with entries in the finite field of two elements $\mathbb{F}_2$, and with the usual operations of matrix addition and multiplication, have been intensively studied, especially due to their ...
11 votes
1 answer
427 views

A strictly descending chain of subalgebras of $P(\omega)/_{\mathrm{fin}}$

Consider the algebra $B=P(\omega)/_{\mathrm{fin}}$ (the quotient of the power set of natural numbers modulo the ideal of finite sets). Is there an infinite strictly descending chain $\{A_i\mid i\in I\}...
6 votes
2 answers
1k views

Embedding a Brouwerian lattice into a Boolean lattice

I have already asked a similar question at https://math.stackexchange.com/questions/470704/can-a-brouwerian-lattice-be-extended-into-a-boolean-algebra but have received no answer. Sorry, I ask a ...
4 votes
1 answer
139 views

Existence of more distributive Boolean lattices

Is there a Boolean lattice $(X,\le)$ and a nonempty collection $(a_{ij})_{i\in I,j\in J}\subseteq X$ such that $$\bigvee_{i\in I}\bigwedge_{j\in J}{a_{ij}}\ne \bigwedge_{f:I\to J}\bigvee_{i\in I}a_{if(...
5 votes
1 answer
309 views

A problem of non-emptiness of intersections of certain chains of regular open sets

Let $X$ be a topological space and $\mathrm{RO}(X)$ its complete boolean algebra of regular opens. Define well inside relation: $$U\prec V\iff\overline{U}\subseteq V.$$ Let $\mathcal C\subseteq\mathrm{...
2 votes
1 answer
125 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 ...
7 votes
1 answer
444 views

Are no infinite subsets of the set of all propositional atoms definable in this structure, even with parameters?

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it. Consider a countably infinite set $P$ ...
-3 votes
1 answer
80 views

Can you do boolean and of 1 and a number less than 1? [closed]

I am reading imenez, J., Echevarria, J.I., Sousa, T. and Gutierrez, D. (2012), SMAA: Enhanced Subpixel Morphological Antialiasing Computer Graphics Forum, 31: 355-364. https://doi.org/10.1111/j.1467-...
1 vote
0 answers
39 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
1 answer
112 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 ...
1 vote
0 answers
61 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 ...
2 votes
2 answers
221 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\...
4 votes
1 answer
255 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{...
5 votes
1 answer
252 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
234 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 ...
2 votes
2 answers
161 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 ...
2 votes
1 answer
85 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 $\...
1 vote
0 answers
73 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 \...
9 votes
1 answer
406 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(...
4 votes
1 answer
191 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 ...
5 votes
3 answers
503 views

Maximal ideals in Boolean algebras; reference request

An old theorem of Pospisil asserts that for any infinite set $I$ the power-set algebra $\wp(I)$ has $\exp \exp |I|$ many maximal ideals containing the ideal of finite sets. This result is published in ...

1
2 3 4 5