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.
273 questions
15 votes
3 answers
797 views
Does ZF alone prove that every complete, atomless Boolean algebra has an infinite antichain?
Here by "antichain" I mean a set of elements that have pairwise-trivial meets, not merely ones that are pairwise-incomparable. Clearly, every atomless Boolean algebra has antichains in this ...
- 153
8 votes
1 answer
459 views
Boolean ultrapower - set-theoretic vs algebraic/model-theoretic
I've been looking through the Hamkins/Seabold paper "Well-founded Boolean ultrapowers as large cardinal embeddings". The Boolean ultrapowers are defined there in two different ways: in ...
- 481
7 votes
1 answer
248 views
Ascending chains in $\mathcal{P}(\kappa)/I_{\mathrm{NS}}$
$\newcommand{\NS}{\mathrm{NS}}\mathcal{P}(\kappa)/I_{\NS}$ is the Boolean algebra of subsets of $\kappa$ under nonstationary symmetric difference, with $\mathbf{0} = [\emptyset] = I_{\NS}$, $\mathbf{1}...
- 2,033
3 votes
1 answer
257 views
Algebraic structure, defined by its own automorphism group
The same post's presented on mathstackexchange, but I think this one is a research level question. I was preparing for my postgraduate exams and one of the questions concerned constructing non-...
- 113
2 votes
0 answers
130 views
Uncountably broad sets in Boolean algebras
Let $A$ be a complete Boolean algebra, and let $\kappa$ be a cardinal. We will say that $B\subset A$ is $\kappa$-broad, if $|B|\ge\kappa$ and for any $B'\subset B$ with $|B'|\ge\kappa$ we have $\...
- 5,643
0 votes
0 answers
104 views
Is there a way to visualize the Stone space of a Boolean algebra - i.e., via its corresponding lattice?
It is a little frustrating to me that I'm not able to 'see' clearly what the Stone space of a Boolean algebra is supposed to be - specially because we have a very visual object representing the ...
- 447
3 votes
1 answer
161 views
Surjective order-preserving map $f: {\cal P}(\omega)/{\text{(fin)}} \to {\cal P}(\omega)$
$\def\Pfin{{\cal P}(\omega)/{\text{(fin)}}}$The projection $\pi:{\cal P}(\omega)\to \Pfin$ is clearly surjective and order-preserving. (The quotient $\Pfin$ is defined here.) Is there a surjective ...
- 53.3k
7 votes
1 answer
397 views
Extracting partitions from dense open subsets of complete Boolean algebras without choice
Let $B$ be a complete Boolean algebra with bottom and top elements $0$ and $1$. A set $D \subseteq B$ is open if for all $a \in D$ and $b \leq a$, $b \in D$, it is dense if for all $a \in B$ there is $...
- 2,512
0 votes
0 answers
185 views
How to construct a matrix ($n\times m$, $m>n$) over $\mathbb{F}_2 $ with full rank, with the row width $m$ and entries' weight per row minimized?
How to construct a full-rank $n \times m$ matrix over $\mathbb{F}_2$ with $m > n$, minimizing width and row sparsity? Goal: Construct a matrix $X \in \mathbb{F}_2^{n \times m}$, with $m > n$, ...
- 19
1 vote
1 answer
115 views
How to find the minimum sum-of-products expression for this boolean function [closed]
I'm working my way through a digital logic textbook, and there is a question whose back-of-book answer is different from my own. I cannot seem to derive it using boolean algebra alone, so I'd like to ...
- 121
8 votes
2 answers
544 views
A lattice/topos-theoretic construction of the Boolean algebra of measurable subsets modulo nullsets
Suppose we take the viewpoint that the right category for measure theory is the category of measurable locales or equivalently, the opposite category of the category of commutative Von Neumann ...
- 2,682
1 vote
1 answer
145 views
Extension of ring homomorphisms in Boolean rings
I am trying to understand problems related to Sikorski’s extension theorem. The following problem occurs when dealing with closed subsets of the Cantor sets. My knowledge of group and ring theory is ...
- 1,201
0 votes
0 answers
68 views
$\sigma$-internal sum of two Boolean $\sigma$-algebras satisfying the countable chain condition
In Chapter 44 "Introduction to Boolean algebras" by Halmos and Givant, is described the notion of internal sum of Boolean algebras. In Chapter 30 is introduced the countable chain condition (...
- 216
0 votes
1 answer
186 views
$\sigma$-homomorphism preserving $\sigma$-distributivity
I am basing some of my thesis on Introduction to Boolean Algebras by Givant and Halmos. My current goal is to leverage the countable chain condition to define conditional probability measures. In ...
- 216
1 vote
0 answers
48 views
Chains with full range on a Boolean algebra with convex measure
Preliminaries. Let $X$ be a set and let $\mathcal A$ be a Boolean algebra of subsets of $X$ (i.e., $\mathcal A\subset 2^X$ such that $\mathcal A$ contains the empty set and is closed under finite ...
- 121
4 votes
0 answers
94 views
Does there exist a multi-valued "monotone" and "compact" map from a Boolean algebra to the "free" part of $\mathcal{P}(\kappa)$?
This is a follow-up to my previous question, which has a negative answer. Here is the most general version that I'm interested: Does there exist a Boolean algebra $A$, an infinite cardinal $\kappa$, ...
- 5,020
8 votes
1 answer
250 views
Does there exist a section of $\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ that is "nearly Boolean"?
The following might be a somewhat esoteric question: Does there exist an infinite cardinal $\kappa$ and a section $f$ of the quotient map $\pi:\mathcal{P}(\kappa)\to\mathcal{P}(\kappa)/(\text{fin})$ (...
- 5,020
3 votes
1 answer
209 views
Stone-Čech compactification of a Boolean subalgebra of $\{0,1\}^S$
Setup: Let $S$ be a set. Let $B$ be a Boolean subalgebra of $\{0,1\}^S$; i.e., just to be clear $B$ contains the constant $0$ and $1$ functions, and is stable under binary pointwise $\land$, $\lor$ ...
- 38k
5 votes
1 answer
231 views
Countably compact Boolean algebras versus distributivity
Let us say that a complete Boolean algebra $B$ is: countably distributive when for any sequence $(I_n)_{n\in\mathbb{N}}$ of sets and any elements $(u_{n,i})_{n\in\mathbb{N},i\in I_n}$ of $B$ we have $...
- 38k
13 votes
4 answers
961 views
What is a "general" relation algebra?
I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "...
- 19.4k
9 votes
1 answer
490 views
Copy of $P(\omega)/\mathrm{fin}$ on $\omega_1$
$\newcommand{\fin}{\mathrm{fin}}$Under what hypotheses does there exist a uniform ideal $I$ on $\omega_1$ such that $P(\omega_1)/I \cong P(\omega)/\fin$? What is the consistency strength? It follows ...
- 20.8k
15 votes
3 answers
2k views
Exponentials of truth values
I noticed that the exponentiation identity $$\exp(r + s) = \exp(r) \cdot \exp(s)~,$$ which is of course completely standard for real or complex numbers also holds in a Boolean setting. That is, when I ...
- 341
3 votes
1 answer
210 views
1-1 map on the $\{0,1\}^k$
Let integer $k>0$ and let $\{0,1\}^k$ denote the set of all $1\times k$-dim vectors whose every coordinate is eithor 0 or 1, for example, $(0,1,1,0,\dots,1,0,0,1)$. For any such vector $\alpha$, ...
- 623
4 votes
0 answers
163 views
Commutativity of a diagram between complete embeddings
Suppose $\mathbb{P}_0$, $\mathbb{P}_1$ and $\mathbb{P}_2$ are separative posets such that $\mathbb{P}_2$ projects into $\mathbb{P}_1$ and $\mathbb{P}_1$ projects into $\mathbb{P}_0$, i.e. there are ...
- 665
2 votes
1 answer
293 views
Complete CCC Boolean algebras (or Stonean spaces)
I am interested in what is known about complete Boolean algebras $B$ with the countable chain condition (ccc), i.e., every disjoint set is countable. Let $K$ be the Stone space of $B$; the ...
- 388
1 vote
2 answers
228 views
Description of atomless complete Boolean algebras with a countable $\pi$-base
Recall that a subset $A$ of a Boolean algebra $B$ is a $\pi$-base if for every $b>0$ there is $a\in A$ with $0<a\le b$. For example, the definition of atomicity says that atoms constitute a $\pi$...
- 5,643
6 votes
1 answer
148 views
Projections between complete boolean algebras
Let $P$ and $Q$ be complete boolean algebras. Suppose that $\dot H$ is a $P$-name such that $1_P\Vdash\dot H$ is $Q$-generic. For each $p\in P$, let $A_p$ be the set of $q\in Q$ such that $p\Vdash q\...
- 665
2 votes
2 answers
271 views
Boolean algebra object structure on coproduct of terminal object
I am asking for some clarification on this old question. The context for my question is a cartesian closed category $ C $ with a binary coproduct and a terminal object $ I $. One of the answers claims ...
- 230
2 votes
0 answers
101 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 ...
- 521
3 votes
0 answers
109 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 ...
- 19.1k
6 votes
1 answer
259 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 ...
- 33.5k
3 votes
0 answers
193 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
279 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$ ...
- 25.7k
4 votes
0 answers
187 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 ...
- 135
5 votes
0 answers
316 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 ...
- 4,077
9 votes
1 answer
475 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 ...
- 53.3k
1 vote
1 answer
154 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\...
- 5,263
13 votes
1 answer
406 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 ...
- 53.3k
1 vote
0 answers
142 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 ...
- 1,297
11 votes
3 answers
944 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,109
7 votes
1 answer
276 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, ...
- 907
-1 votes
1 answer
95 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 ...
- 5,020
6 votes
1 answer
392 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}$...
- 53.3k
4 votes
1 answer
298 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 $[...
- 53.3k
4 votes
1 answer
622 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, ...
- 1,203
12 votes
1 answer
634 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\}...
- 1,206
3 votes
1 answer
251 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 ...
- 31
7 votes
1 answer
485 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$ ...
- 2,183
-3 votes
1 answer
107 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-...
- 11
1 vote
0 answers
80 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 ...
- 491