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.
240
questions
2
votes
0
answers
170
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 $\...
- 49
0
votes
0
answers
27
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 ...
- 1
1
vote
1
answer
110
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\...
- 4,674
13
votes
1
answer
248
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 ...
- 44.4k
1
vote
0
answers
102
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,267
10
votes
3
answers
699
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 ...
- 493
7
votes
1
answer
204
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, ...
- 889
-1
votes
1
answer
54
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 ...
- 1,099
6
votes
1
answer
347
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}$...
- 44.4k
4
votes
1
answer
244
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 $[...
- 44.4k
4
votes
1
answer
324
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, ...
- 987
11
votes
1
answer
422
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,082
3
votes
1
answer
174
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
441
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,043
-3
votes
1
answer
79
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
36
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 ...
- 451
2
votes
1
answer
119
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,273
1
vote
0
answers
56
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 ...
- 447
1
vote
1
answer
109
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 ...
- 9,160
2
votes
2
answers
211
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\...
- 44.4k
3
votes
0
answers
120
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 ...
- 131
5
votes
1
answer
247
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,654
1
vote
1
answer
220
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 ...
- 564
2
votes
2
answers
153
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
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 \...
- 421
2
votes
1
answer
75
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 $\...
- 421
1
vote
2
answers
148
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 $...
- 303
4
votes
1
answer
254
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,581
9
votes
1
answer
397
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,581
4
votes
1
answer
186
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,143
1
vote
1
answer
141
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)$...
- 13
3
votes
0
answers
143
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 ...
- 2,922
0
votes
0
answers
41
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 $...
- 40.1k
2
votes
1
answer
110
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 ...
- 44.4k
2
votes
2
answers
411
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
236
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
161
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,273
0
votes
1
answer
211
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+...
- 23
1
vote
1
answer
129
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 ...
- 261
-1
votes
1
answer
112
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 ...
- 629
14
votes
1
answer
414
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
295
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 ...
- 59.3k
13
votes
2
answers
906
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
...
- 261
12
votes
0
answers
384
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$ ...
- 121
8
votes
0
answers
144
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 ...
- 111
1
vote
0
answers
120
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 ...
- 17.6k
6
votes
0
answers
149
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 ...
- 271
6
votes
0
answers
100
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
6
votes
1
answer
281
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
377
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 ...
- 36.8k