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
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 ...
Beginner's user avatar
  • 175
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 ...
Claudia Correa's user avatar
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 ...
Min Wu's user avatar
  • 461
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 ...
Thomas's user avatar
  • 263
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 ...
Iian Smythe's user avatar
  • 3,001
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$ ...
Zoorado's user avatar
  • 1,215
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 ...
Mathlover's user avatar
  • 292
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 ...
zbh2047's user avatar
  • 601
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'$ ...
Dominic van der Zypen's user avatar
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 $\...
namsap's user avatar
  • 335
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: ...
dragoon's user avatar
  • 763
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$ ...
Rafał Gruszczyński's user avatar
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 ...
Evgeny Kuznetsov's user avatar
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 ...
Damian Sobota's user avatar
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 ...
András Salamon's user avatar
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$...
Don Monk's user avatar
  • 883
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 ...
matteo viale's user avatar
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 ...
user avatar
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?
dioxoid's user avatar
  • 21
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 ...
Victor's user avatar
  • 655
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 ...
goblin GONE's user avatar
  • 3,693
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 ...
Damian Sobota's user avatar
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 $\...
Ronnie's user avatar
  • 133
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.
Raskol's user avatar
  • 167
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 ...
Rahman. M's user avatar
  • 2,341
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) = - \...
Sebastien Palcoux's user avatar
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 ...
gradstudent's user avatar
  • 2,136
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 ...
Ashot's user avatar
  • 337
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 ...
Maxtimax's user avatar
  • 180
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 ...
Henry.L's user avatar
  • 7,951
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-...
Jonah's user avatar
  • 189
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 ...
King Kong's user avatar
  • 631
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 ...
user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Agustí Roig's user avatar
  • 1,935
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....
Horse's user avatar
  • 193
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}\...
Steve's user avatar
  • 1,117
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 ...
Kal's user avatar
  • 11
3 votes
3 answers
668 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 "...
dwymark's user avatar
  • 133
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\...
მამუკა ჯიბლაძე's user avatar
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 (...
Alexey Milovanov's user avatar
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. ...
Marcus Pivato's user avatar
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 |\...
Alexey Milovanov's user avatar
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}$$ ...
C. Dubussy's user avatar
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 (...
hhh's user avatar
  • 143
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 ...
Ani Kar's user avatar
  • 41
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)=...
Junekey Jeon's user avatar
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\...
Rafał Gruszczyński's user avatar
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 ...
user avatar
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}\...
Alex's user avatar
  • 21