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.
248
questions
1
vote
1
answer
336
views
To what logic does the free Boolean sigma-algebra of countably many generators correspond to?
The free Boolean algebra on countably many generators is closely related to the classical (two-valued) propositional calculus (after identification of logically equivalent formulas).
By the Stone ...
9
votes
1
answer
374
views
Embeddings of Boolean algebras in $\wp(\omega)/Fin$
If we assume MA+¬CH, then every boolean algebra with cardinality smaller than the continuum embeds in ℘(ω)/Fin. A proof of this result can be found in Theorem 1.1, Chapter 8 of the book "Hausdorff ...
1
vote
0
answers
84
views
Algorithm of constructing the graph for a partial order set [closed]
Given a finite partial order set $(P,\leq)$. Is there an algorithm for constructing its graph, where, from bottom to top, the ordering goes up? Namely, I want to construct the directed graph ...
11
votes
1
answer
1k
views
Is every complete Boolean algebra isomorphic to the quotient of a powerset algebra?
Is every complete Boolean algebra isomorphic to a quotient, as a Boolean algebra, of some powerset algebra $\wp(X)$?
It is not true for arbitrary Boolean algebras, see the comments, or see my MathSE ...
5
votes
2
answers
260
views
Von Neumann's theorem on realizing automorphisms of the measure algebra
I'm looking for a proof, in English, of the following theorem due to von Neumann (which apparently originates in the paper Einige Sätze über Messbare Abbildungen, Ann. of Math, 1932):
Every ...
6
votes
1
answer
565
views
Boolean ultrapower of V[G] by G
In Joel David Hamkins's "Well-founded Boolean Ultrapowers as Large Cardinal Embeddings", it is mentioned that if $U \in \mathbf{V}$ is an ultrafilter of a complete Boolean algebra $\mathbb{B}$ and $U$ ...
2
votes
1
answer
268
views
How to recover $k$ lost items in binary data $x_1,x_2,x_3 \dots,x_n$ via only XOR operator?
I asked this question in math.stackexchange (link) and I have had an answer for general case by using Reed-Solomon Code. More information for Reed-Solomon Coding for Fault-Tolerance in RAID-like ...
7
votes
1
answer
348
views
A Bitwise Xor Problem
Consider a sequence $a_i$ defined by
$$
\begin{align*}
a_1&=p,\\
a_2&=q,\\
a_i&=a_{i-1} \oplus a_{i-2}+1,
\end{align*}$$
where $\oplus$ is the bitwise xor operation. How can we give an ...
2
votes
1
answer
296
views
Boolean completion of a partially ordered set
Given a poset $(P, \leq)$, is there a complete Boolean lattice $B$ and an order-preserving map $i_P: P\to B$ such that for any complete Boolean lattice $B'$ and order-preserving map $f: P\to B'$ ...
12
votes
3
answers
796
views
Is it possible to completely embed complete Heyting Algebras into upsets of a poset?
Let $H$ be a Heyting algebra. It is a well-known result that there is a partially ordered set (Kripke frame) X such that there is an embedding of Heyting algebras $f: H \to \mathsf{Up}(X)$, where $\...
9
votes
0
answers
347
views
Direct limits of $\sigma$-centered forcing notions
It is quite well known that
Any FS (finite support) iteration of length $<\mathfrak{c}^+$ of $\sigma$-centered posets is $\sigma$-centered (see e.g. here).
Now consider the following question: ...
8
votes
2
answers
286
views
Does $\aleph_0$-density of regular open algebra entail existence of countable basis?
Suppose that the family $\mathrm{RO}(X)$ of regular open subsets of $(X,\mathscr{O})$ is a basis of $X$. Let the density of $\mathrm{RO}(X)$ (considered as Boolean algebra) be $\aleph_0$.
Does $X$ ...
3
votes
1
answer
382
views
Stone topological Boolean algebras
I am looking for an initial reference for a theorem which is known, namely:
Theorem: A Boolean algebra $A$ admits a Stone space topology (i.e. is the underlying algebra of a Stone topological ...
1
vote
0
answers
100
views
Paper by Diestel, Faires and Huff
I have been looking for a (long) while for the following paper:
J. Diestel, B. Faires, and R. Huff, Convergence and boundedness of measures on non-sigma complete algebras, preprint, 1976.
This ...
2
votes
1
answer
139
views
Efficiently embedding finite Boolean algebras into lattices of set partitions?
Let $P_n$ be the lattice of set partitions of $[n] = \{1,2,\dots,n\}$, let $B_n$ be the Boolean algebra of subsets of $[n]$.
Is there some $n_0$ such that for all $n \ge n_0$ it is possible to ...
11
votes
1
answer
663
views
partitions of Boolean algebras
A partition of a Boolean algebra is a collection of pairwise disjoint nonzero elements with supremum 1. For any infinite Boolean algebra $A$ let $a(A)$ be the least size of an infinite partition of $A$...
13
votes
2
answers
592
views
A curiosity on complete homomorphisms of boolean algebras
The question may be trivial, but has eluded me, may be it is more appropriate for mathstack-exchange.
Let $B$, $C$ be boolean algebras and $i:B\to C$ be an homomorphism.
By Stone duality to each such ...
0
votes
1
answer
503
views
Representation of free Boolean sigma-algebras
By a theorem of Loomis and Sikorski, for every Boolean $\sigma$-algebra $\mathfrak{A}$ there exists a $\sigma$-field of sets $\mathcal{F}$ and a $\sigma$-ideal $\Delta$ such that $\mathfrak{A}$ is ...
2
votes
1
answer
133
views
Atomicity of blocks in a Hilbert lattice
Where can I find the proof that any block (maximal boolean subalgebra) $\mathbf{B}$ of the orthomodular lattice $\mathcal{L}$ of closed subspaces of a separable Hilbert space $\mathcal{H}$ is atomic?
2
votes
1
answer
365
views
Characterization of monotone boolean functions with minimum number of extremal points
Let $B = \{ 0, 1 \}$. For two points $\textbf{x}, \textbf{y} \in B^n$ we will write $\textbf{x} \preceq \textbf{y}$ iff $\textbf{x}_i \leq \textbf{y}_i$ for every $i \in \{ 1, \ldots, n \}$.
A ...
2
votes
2
answers
224
views
What's "serialization" really called, and is there any theory surrounding it?
Define an operator $\mathop{\vec{\bigcup}}$ as follows:
Definition. Whenever $A$ is an $I$-indexed family of sets, where $I$ is a totally-ordered set, we have $$\mathop{\vec{\bigcup}}_{i \in I} A_i ...
2
votes
0
answers
94
views
Weak* convergence of measures on Boolean algebras
The Dieudonné-Grothendieck theorem asserts that given a compact Hausdorff space $K$ and a uniformly bounded family $\mathcal{K}\subset C(K)^*$ (the dual to the Banach space of continuous real-valued ...
2
votes
0
answers
155
views
Does $\lambda$-completion of $\kappa$-Boolean algebras preserve monomorphisms?
Let $\kappa \le \lambda$ be infinite regular cardinals. Does the free $\lambda$-completion functor $F_\kappa^\lambda$ from the category of $\kappa$-complete Boolean algebras to the category of $\...
2
votes
1
answer
166
views
Logic Alphabet for more than Two Variables
Is it possible to generalise Zellweger’s logic alphabet for more than two Boolean variables?
Can it be done by only using the 16 binary connectives?
Thanks.
6
votes
1
answer
341
views
Weak equivalence over forcing notions
We know there are several definitions about forcing equivalence which imply that two forcings notions can be equivalent or not. In general we like to know the similarity between generic extensions by ...
3
votes
0
answers
165
views
A boolean representation of the Möbius function on a finite lattice
Let $(L,\wedge , \vee)$ be a finite lattice with minimum $\hat{0}$ and maximum $\hat{1}$.
Consider the Möbius function $\mu$ on $L$ defined inductively by $$\mu(\hat{1}) = 1 \text{ and } \mu(a) = - \...
4
votes
0
answers
80
views
Polynomial approximations on the Boolean hypercube
Given $\vec{a} \in \mathbb{R}^n$ and $b \in \mathbb{R}$ consider the function $f(x) = Th[\vec{a}.\vec{x}+b]$ on $x \in \{-1,1\}^n$ such that the ``threshold function (Th)" gives $1$ when the argument ...
2
votes
1
answer
215
views
Symmetric group acting on the set of boolean functions
Let $S_n$ act on the set of boolean functions of size $n$ in the following way:
If $f$ is a boolean function and $\alpha \in S_n$, then $g=\alpha f$ and $g(x)=f(\alpha(x))$ where $x$ is boolean ...
5
votes
2
answers
502
views
How "strong" is the existence of a non trivial ultrafilter on $\omega$?
Obviously the question in the title alone doesn't make sense so I'll develop on the context and then I'll ask my question :
Studying $AD$ (axiom of determinacy) I had to prove that $AD$ and $AC$ are ...
6
votes
0
answers
327
views
What is the algebraic equivalent of independent elements?
The definition/notion of independence is always a bit odd in measure theoretic probability theory.
Definition Given a probability space $(\Omega,\mathcal{F},P)$, two sets $A,B\in\mathcal{F}$ are ...
8
votes
2
answers
825
views
In what sense is GCD an extension of boolean OR?
The J Programming langauge has an operator which acts as both the GCD and boolean Or. The J Primer has this note about it:
The GCD is a useful extension of the domain of the or function to non-...
2
votes
0
answers
66
views
Distance measures between Boolean algebra homomorphisms
Is there a natural way to define the 'distance' between two Boolean algebra homomorphisms $f, g: B \rightarrow B'$? I'm thinking of something like the Kullback leibeler divergence for probability ...
2
votes
0
answers
60
views
A question related to Boolean functions? [closed]
Let $Z_2=\{0,1\}$, $Z_2^r=Z_2\times Z_2 \times...\times Z_2,$ $S_1\subset Z_2^{n_1}$ and $S_2\subset Z_2^{n_2}$, $S=(S_2,S_1)\subset Z_2^{n_1+n_2}$, I'd like to construct $S_1$ and $S_2$ s.t the ...
1
vote
1
answer
170
views
Interval topology on complete Boolean algebras
Let $(P,\leq)$ be a poset. The interval topology $\tau_i(P)$ on $P$ is generated by
$$\{P\setminus\downarrow x : x\in P\} \cup \{P\setminus\uparrow x : x\in P\},$$
where $\downarrow x = \{y\in P: y\...
1
vote
1
answer
109
views
Missing an elementary step about the frame of strings in Barr-Diaconescu theorem
I'm trying to understand the proof of the Barr-Diaconescu theorem about Boolean covers for Grothendieck sites. Precisely, the versions you can find in Jardine's book "Local Homotopy Theory" or in Mac ...
1
vote
3
answers
284
views
Is every c.c.c. non-atomic partial order of size $\omega_1$ a union of countable complete suborders?
We say that $\mathbb{P}$ is a complete suborder of $\mathbb{Q}$, if it is a suborder, and maximal antichains in $\mathbb{P}$ remain maximal antichains in $\mathbb{Q}$
As the title says, is every c.c....
4
votes
0
answers
137
views
Level sets of function of inner products of vectors on hypercube
Let $H = \{ 0, 1\}^d$ be the $d$-th Cartesian product of $\{0, 1\}$ in $\mathbb{R}^d$. Suppose $v_1, \ldots, v_k$ are $k$ vectors in $H$ in general position. We define function $F \colon H^{k}\...
1
vote
1
answer
142
views
Finding a set of disjoint affine subspaces such that their union is equal to a given subset of $\mathbb{F}_2^n$
Suppose I'm given a set of point $S = \{x_1, \dots, x_m \} \subseteq \mathbb{F}_2^n$, and the following task. Find a set of disjoint affine subspaces of $\mathbb{F}_2^n$, $A_1, \dots, A_k$ satisfying ...
3
votes
3
answers
667
views
Incomplete subsets of the free boolean algebra on countably many generators
I know that it is provable that the free boolean algebra on countably many generators is incomplete. For the sake of concreteness, let's call the generators $p_1, p_2, p_3,...$ and refer to them as "...
2
votes
1
answer
181
views
Lattices without nontrivial dense elements
This question arose from another one of mine, Homotopy type of some lattices with top and bottom removed.
An element $d$ of a bounded lattice $L$ is called $\mathit{dense}$ if
$$
\forall x\in L\ (d\...
7
votes
0
answers
287
views
The number of monotone Boolean functions
In the paper "The number of monotone Boolean functions" A. D. Korshunov calculates an asymptotic number of the number of monotone Boolean functions (wikipedia):
However I can not find this paper (...
3
votes
1
answer
838
views
Finitely additive measures on Boolean algebras of regular open subsets: Is there a relationship with Borel measures? A theory of integration?
Let $\mathcal{X}$ be a topological space. An open subset $\mathcal{R}\subseteq\mathcal{X}$ is regular if it is the interior of its own closure. The intersection of two regular open sets is regular. ...
4
votes
0
answers
153
views
Effective "almost enumeration" of monotone boolean functions
Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...
2
votes
0
answers
62
views
Dual equivalence for multioperators
This is a reference request question. But let's start with a few definitions.
Let $L$ and $M$ be two bounded lattices. A multioperator $p$ for $L$ and $M$ is an application $$p : L \to Ft(M)^{op}$$ ...
2
votes
0
answers
115
views
Influence of independent variables on boolean functions?
Suppose a simple connected graph $G$ where its vertices are assumed to be independent. An event with uncertainty corresponds to each vertex. My instructor guides me that even though the vertices (...
4
votes
0
answers
285
views
Find the number of boolean functions of n variable that satisfy the following condition
For how many boolean functions is this true? The length of the shortest disjunctive normal form of that functions is equal to 2^(n-1). And the the number of variable entries in the minimal dnf of that ...
0
votes
1
answer
176
views
About equalizer of Boolean algebras
Let $A,B$ be complete Boolean algebras and $\varphi,\psi:A\rightarrow B$ be
maps preserving $0,1$, and arbitrary joins and meets. Let $C$ be the equalizer of these two; so $C=\left\{a\in A:\varphi(a)=...
2
votes
1
answer
143
views
Regular open Boolean algebras and homomorphism which does not preserve nearness of sets
I am looking for an example of topological spaces $\langle X_1,\mathscr{O}_1\rangle$ and $\langle X_2,\mathscr{O}_2\rangle$ such that
there is a homomorphism $h\colon\mathrm{r}\mathscr{O}_1\...
8
votes
1
answer
285
views
Boolean-Valued Models: Why is $\| x=y \| \cdot \| \phi(x) \| \leq \| \phi(y) \|$?
Let $B$ be a complete Boolean algebra. Jech defines a Boolean-valued model $\mathfrak{A}$ of the language of set theory to consist of a Boolean universe $A$ and functions of two variables with values ...
2
votes
1
answer
513
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...