text:
# How to characterize a transmission line using a qubit as a probe

Characterize transmission-line bandwidth via probe measurements and the graph-based optimization engine

The Boulder Opal optimization engine provides a large, modular collection of configuration options that allows it to be used for a range of tasks in quantum control, including estimating Hamiltonian parameters in a model using measured data.

In this notebook, we show how the optimization engine can be used to determine the hardware parameters that impact the fidelity of control operations. Specifically, we focus on estimating the bandwidth of transmission lines via probe measurements.

## Transmission-line-bandwidth characterization overview

Our task is to identify a linear filter that alters the shape of the pulses in the control line. By feeding different control pulses and then measuring the qubit, we are able to extract information about the parameters that characterize the filter. This setup is illustrated in the figure below.

To exemplify this procedure, we will consider a one-qubit system obeying the following Hamiltonian:

$H(t) = \frac{1}{2} \mathcal{L} \left[ \alpha(t) \right] \sigma_x,$

where $\alpha(t)$ is a real time-dependent control pulse and $\mathcal{L}$ is a filter applied to the pulse. This linear filter acts on the control pulse $\alpha(t)$ according to the convolution product with some kernel $K(t)$:

$\mathcal{L} \left[ \alpha(t) \right] = \int_0^t \mathrm{d} s \; \alpha(s) K(t-s).$

To characterize this filter, we want to determine the parameters that provide the form of the kernel $K(t)$.

It is useful in many cases to approximate the linear filter using a Gaussian kernel characterized by two unknown parameters, a standard deviation $\sigma$ and a mean $\mu$:

$K(t) = \frac{1}{\sqrt{2\pi \sigma^2}} \exp \left\{ - \frac{(t-\mu)^2}{2\sigma^2} \right\}.$

The standard deviation $\sigma$ roughly represents the range of frequencies that the filter allows to pass, while the mean $\mu$ represents a time offset between when the pulses were intended to be generated and when they are actually produced. To estimate these two parameters, we will simulate the effect of this filter on a series of pulses and then use the simulated results to find the most likely form of the filter’s kernel.

## Summary workflow

### 1. Perform measurements to probe the system

To estimate the parameters $\sigma$ and $\mu$, we subject our system to a series of Gaussian pulses with different standard deviations and delays, and measure their effect on the qubit. Each of these Gaussian wave packets will contain a different range of frequencies, and thus be differently affected by the linear filter. The different delay timings also result in a different effect of the pulses by the offset of the filter, as later pulses will have a larger portion of their area outside the time interval before the measurement. The values of the final measurements are then used to obtain an estimate of the parameters that characterize the filter.

As the Hamiltonian we are considering is proportional to $\sigma_x$, we will normalize all the Gaussian pulses to produce $\pi$ pulses, prepare the qubit initially in the state $|0 \rangle$, and measure the population in state $| 1 \rangle$. If no filter was present, the initial state would be flipped by the $\pi$ pulse and the population in state $|1 \rangle$ would be 1. Any deviations from this behavior represent the effect of the filter $\mathcal{L}$.

We will assume that the measurement results are given by some physical parameter (given in arbitrary units) linearly proportional to the population in the state $|1 \rangle$, but not necessarily the same, because the populations might not be directly accessible by the measurement apparatus. This results in two additional parameters that connect the measured results $M$ to the population $P_1$ of state $|1 \rangle$:

$M = a P_1 + b.$

Together, $\sigma$, $\mu$, $a$, $b$ form the four variables that our optimization engine will attempt to determine.

### 2. Build a graph-based optimization encoding the problem

Next, you represent a cost function to be minimized using graphs. Begin by defining the parameters that you want to estimate in the graph using the graph.optimization_variable operation. If you have an idea of the expected value of the optimization variables, you can provide it in the form of initial_values for the optimization variable. In this case, the parameter $a$ is expected to have a value close to 1, while the parameter $b$ is expected to have a value close to 0.

Construct the problem such that the optimizer will try to find the form of the evolution that would most closely match the measured points. Given a set of input points $M_i$ and the corresponding values $m_i$ that would be expected from a chosen set of the filter parameters $\sigma, \mu, a, b$, the cost function is:

$C = \sum_i \frac{[M_i-m_i(\sigma, \mu, a, b)]^2}{2(\Delta M_i)^2},$

where $\Delta M_i$ is the standard deviation of each of the measured input points $M_i$. Minimizing this cost function is equivalent to minimizing the negative log likelihood that a certain set of parameters $\sigma, \mu, a, b$ could generate the points $M_i$, for the case where the probability distribution of the errors is a Gaussian. In this case, the probability of a certain curve $m_i(\sigma, \mu, a, b)$ generating the points $M_i$ is the product of all the individual Gaussian probabilities:

$P = \prod_i \frac{1}{\sqrt{2\pi (\Delta M_i)^2}} \exp \left\{ - \frac{[M_i - m_i(\sigma, \mu, a, b)]^2}{2 (\Delta M_i)^2} \right\}.$

It is easy to see that the negative logarithm of $P$ is the cost $C$ plus constants.

Execute the optimization using qctrl.functions.calculate_optimization by assigning the optimization variables to output nodes of the graph. Minimizing this cost gives us the best choice of parameters that generated the original dynamics of the system, and also allows us to calculate the precision of the estimated parameters. This is done by using the Cramér–Rao bound to identify the Hessian of the cost function with the inverse of the covariance matrix for the variables estimated.

## Worked example: Estimating the parameters of a Gaussian filter with simulated qubit measurements

The following code blocks begin by simulating the response of a qubit driven by a filtered pulse. The results of this simulation are taken as proxy measurements on which we perform the system identification task below.

import matplotlib.pyplot as plt
import numpy as np
from qctrlvisualizer import get_qctrl_style

from qctrl import Qctrl

plt.style.use(get_qctrl_style())

# Start a Boulder Opal session
qctrl = Qctrl()

# Define parameters to be estimated
actual_sigma = 300e-9  # s
actual_mu = 100e-9  # s
actual_a = 1.7
actual_b = -0.5

total_duration = 1000e-9  # s

# Define parameters of the Gaussian pulses to probe the filter
max_width = total_duration / 6.0
mean_values = np.linspace(max_width, total_duration - max_width, 6)
width_values = np.linspace(max_width / 8.0, max_width / 2.0, 4)

# Define sampled times
segments = 150
t_values = np.linspace(0.0, total_duration, segments + 1)

def population(pulse_widths, pulse_means, filter_sigma, filter_mu):
"""
Calculates the transfer probability between states |0> and |1> for a
batch of Gaussian pulses with given widths and means, while applying
a Gaussian filter to the pulses with a given cutoff frequency and offset.
"""

def gaussian_pulse(t, mean, width):
return np.exp(-0.5 * ((t - mean) / width) ** 2.0) * np.sqrt(
0.5 * np.pi / width**2.0
)

graph = qctrl.create_graph()

alpha = graph.pwc_signal(
gaussian_pulse(
t_values[None, None, :],
pulse_means[None, :, None],
pulse_widths[:, None, None],
),
total_duration,
)

shift_signal = graph.convolve_pwc(
pwc=alpha,
kernel=graph.gaussian_convolution_kernel(std=filter_sigma, offset=filter_mu),
)
shift = 0.5 * shift_signal * graph.pauli_matrix("X")

population = 1.0 - graph.infidelity_stf(
sample_times=t_values,
hamiltonian=shift,
target=graph.target(graph.pauli_matrix("M")),
)
population.name = "populations"

graph_result = qctrl.functions.calculate_graph(
graph=graph, output_node_names=["populations"]
)

return graph_result.output["populations"]["value"]

populations = population(
pulse_widths=width_values,
pulse_means=mean_values,
filter_mu=actual_mu,
filter_sigma=actual_sigma,
)

Your task calculate_graph (action_id="1164523") has started. You can use the qctrl.get_result method to retrieve previous results.

# Create measurement results with some uncertainty associated to them,
# we will estimate the standard deviation of this error as 1% of the population
population_errors = 0.01 * np.ones_like(populations)

measurement_results = (
actual_a * np.random.normal(loc=populations, scale=population_errors) + actual_b
)

# Rescale error to arbitrary units
measurement_errors = np.abs(actual_a) * population_errors

# Plot inputs
fig, axs = plt.subplots(1, 4, figsize=(16, 4))
axs[0].set_ylabel("Measured values, M (a.u.)")
for n in range(len(width_values)):
axs[n].set_title(f"Pulses with width {width_values[n] * 1e6:.2f} µs")
axs[n].set_xlabel("Pulse center (µs)")
axs[n].errorbar(
mean_values * 1e6,
measurement_results[n],
yerr=2.0 * measurement_errors[n],
fmt="s",
)

plt.show()

Each of these graphs represents the average measurement results of a series of simulated experiments where the offset of the Gaussian $\pi$ pulses vary. In each graph the width of the Gaussian control pulse is different, as indicated in their titles. The measured values $M$ plotted above are linearly proportional to the populations $P_1$:

$M = a P_1 + b.$

The measured values are assumed to be subject to errors with Gaussian probability distributions that have a standard deviation that is 1% of $a$. This means that we are assuming that the error in the value of the of the population is of about 1%. The error bars in the graphs represent two times the standard deviation, having therefore a reliability of 95%.

### Estimating the parameters of the filter

The next step involves performing an optimization in which the four unknown parameters are estimated. This is done by the optimizer by trying to find the form of the evolution that would most closely match the measured points. The optimization engine involves performing a simulation of system evolution in order to fit the measured data.

graph = qctrl.create_graph()

# Parameters to estimate
mu = graph.optimization_variable(
count=1, lower_bound=0.0, upper_bound=total_duration, name="mu"
)
sigma = graph.optimization_variable(
count=1, lower_bound=total_duration / 100, upper_bound=total_duration, name="sigma"
)
a = graph.optimization_variable(
count=1, lower_bound=-10.0, upper_bound=10.0, initial_values=np.array([1]), name="a"
)
b = graph.optimization_variable(
count=1, lower_bound=-10.0, upper_bound=10.0, initial_values=np.array([0]), name="b"
)

# Define Gaussian pulse, normalized to generate pi-pulses
def gauss_pulse(t, mean, width):
return graph.exp(-0.5 * ((t - mean) / width) ** 2.0) * graph.sqrt(
0.5 * np.pi / width**2.0
)

# Create Hamiltonian term
# Create a 2D batch of signals with all values of mean and width you want to simulate.
# This batch is preserved through the entire computation, which ends up being faster than
# looping through all values.
alpha = graph.pwc_signal(
values=gauss_pulse(
t_values[None, None, :], mean_values[None, :, None], width_values[:, None, None]
),
duration=total_duration,
name="alpha",
)

gaussian_kernel = graph.gaussian_convolution_kernel(std=sigma, offset=mu)
alpha_filtered = graph.convolve_pwc(pwc=alpha, kernel=gaussian_kernel)
shift = 0.5 * alpha_filtered * graph.pauli_matrix("X")

# Calculate |0> -> |1> transfer probability
calculated_populations = 1.0 - graph.infidelity_stf(
sample_times=t_values,
hamiltonian=shift,
target=graph.target(graph.pauli_matrix("M")),
name="infidelities",
)

# Create measured points
calculated_points = a * calculated_populations + b
calculated_points.name = "calculated_points"

# Calculate cost
cost = graph.sum(
(calculated_points - measurement_results) ** 2.0
/ (2.0 * measurement_errors**2.0),
name="cost",
)

# Calculate Hessian
hessian = graph.hessian(cost, [mu, sigma, a, b], name="hessian")

# Estimate the parameters
result = qctrl.functions.calculate_optimization(
graph=graph,
cost_node_name="cost",
output_node_names=["mu", "sigma", "a", "b", "hessian"],
optimization_count=10,
)

estimated_mu = result.output["mu"]["value"][0]
estimated_sigma = result.output["sigma"]["value"][0]
estimated_a = result.output["a"]["value"][0]
estimated_b = result.output["b"]["value"][0]

# Calculate 2-sigma uncertainties (error bars give 95% precision)
hessian = result.output["hessian"]["value"]
uncertainties = 2.0 * np.sqrt(np.diag(np.linalg.inv(hessian)))
uncertainty_mu, uncertainty_sigma, uncertainty_a, uncertainty_b = uncertainties

Your task calculate_optimization (action_id="1164541") has started. You can use the qctrl.get_result method to retrieve previous results.

mean_range = np.linspace(0.1 * total_duration, 0.9 * total_duration, 30)

calculated_curves = estimated_b + estimated_a * population(
pulse_widths=width_values,
pulse_means=mean_range,
filter_mu=estimated_mu,
filter_sigma=estimated_sigma,
)

ideal_curves = actual_b + actual_a * population(
pulse_widths=width_values,
pulse_means=mean_range,
filter_mu=actual_mu,
filter_sigma=actual_sigma,
)

Your task calculate_graph (action_id="1164560") has started. You can use the qctrl.get_result method to retrieve previous results.

# Print parameter estimates
print(f"\nactual sigma = {actual_sigma/1e-6} µs")
print(
f"estimated sigma = ({estimated_sigma/1e-6:.3f} ± {uncertainty_sigma/1e-6:.3f}) µs"
)

print(f"\nactual mu = {actual_mu/1e-6} µs")
print(f"estimated mu = ({estimated_mu/1e-6:.3f} ± {uncertainty_mu/1e-6:.3f}) µs")

print(f"\nactual a = {actual_a} au")
print(f"estimated a = ({estimated_a:.3f} ± {uncertainty_a:.3f}) au")

print(f"\nactual b =", actual_b, "au")
print(f"estimated b = ({estimated_b:.3f} ± {uncertainty_b:.3f}) au")

# Plot results
fig, axs = plt.subplots(1, 4, figsize=(16, 4))
axs[0].set_ylabel("Measurement values, M (a.u.)")

for n in range(len(width_values)):
axs[n].set_title(f"Pulses with width {width_values[n] * 1e6:.2f} µs")
axs[n].set_xlabel("Pulse center (µs)")
axs[n].errorbar(
mean_values * 1e6,
measurement_results[n],
yerr=2.0 * measurement_errors[n],
fmt="s",
color="C0",
label="Measured values",
)
axs[n].plot(
mean_range * 1e6, ideal_curves[n], color="C0", label="Ideal values", alpha=0.3
)
axs[n].plot(
mean_range * 1e6,
calculated_curves[n],
"--",
label="Estimated values",
color="C1",
)
axs[n].legend(loc=3)

plt.show()

actual sigma = 0.3 µs
estimated sigma = (0.306 ± 0.028) µs

actual mu = 0.1 µs
estimated mu = (0.095 ± 0.007) µs

actual a = 1.7 au
estimated a = (1.797 ± 0.099) au

actual b = -0.5 au
estimated b = (-0.583 ± 0.095) au

In the graphs above, we can compare the curves that represent the values that would be measured if the system followed the estimated filter (dashed), and the values that would be measured if perfect measurements were performed on a system subject to the real filter (solid). Each graph corresponds to sets of experiments where pulses of the same width are applied at different points in time, as indicated in their titles and $x$ axis. The close match between the two curves highlights the fact that the estimated parameters are close to the real values.

Above we also provide explicit estimates of the parameters $\sigma$ (sigma) and $\mu$ (mu) of the Gaussian kernel of the linear filter. The errors estimated for the variables above have a certainty of 2 times the standard deviation, or 95%.

This notebook was run using the following package versions. It should also be compatible with newer versions of the Q-CTRL Python package.

Package Version
Python 3.9.12
matplotlib 3.5.1
numpy 1.23.3
scipy 1.9.1
qctrl 19.5.0
qctrl-commons 17.3.0
qctrl-toolkit 1.9.0
qctrl-visualizer 4.0.0


text:
# scanpy.tl.dpt¶

scanpy.tl.dpt(adata, n_dcs=10, n_branchings=0, min_group_size=0.01, allow_kendall_tau_shift=True, neighbors_key=None, copy=False)

Infer progression of cells through geodesic distance along the graph [Haghverdi16] [Wolf19].

Reconstruct the progression of a biological process from snapshot data. Diffusion Pseudotime has been introduced by [Haghverdi16] and implemented within Scanpy [Wolf18]. Here, we use a further developed version, which is able to deal with disconnected graphs [Wolf19] and can be run in a hierarchical mode by setting the parameter n_branchings>1. We recommend, however, to only use dpt() for computing pseudotime (n_branchings=0) and to detect branchings via paga(). For pseudotime, you need to annotate your data with a root cell. For instance:

adata.uns['iroot'] = np.flatnonzero(adata.obs['cell_types'] == 'Stem')[0]

This requires to run neighbors(), first. In order to reproduce the original implementation of DPT, use method=='gauss' in this. Using the default method=='umap' only leads to minor quantitative differences, though.

New in version 1.1.

dpt() also requires to run diffmap() first. As previously, dpt() came with a default parameter of n_dcs=10 but diffmap() has a default parameter of n_comps=15, you need to pass n_comps=10 in diffmap() in order to exactly reproduce previous dpt() results.

Parameters
adata : AnnDataAnnData

Annotated data matrix.

n_dcs : intint (default: 10)

The number of diffusion components to use.

n_branchings : intint (default: 0)

Number of branchings to detect.

min_group_size : floatfloat (default: 0.01)

During recursive splitting of branches (‘dpt groups’) for n_branchings > 1, do not consider groups that contain less than min_group_size data points. If a float, min_group_size refers to a fraction of the total number of data points.

allow_kendall_tau_shift : boolbool (default: True)

If a very small branch is detected upon splitting, shift away from maximum correlation in Kendall tau criterion of [Haghverdi16] to stabilize the splitting.

neighbors_key : str, None (default: None)

If not specified, dpt looks .uns[‘neighbors’] for neighbors settings and .obsp[‘connectivities’], .obsp[‘distances’] for connectivities and distances respectively (default storage places for pp.neighbors). If specified, dpt looks .uns[neighbors_key] for neighbors settings and .obsp[.uns[neighbors_key][‘connectivities_key’]], .obsp[.uns[neighbors_key][‘distances_key’]] for connectivities and distances respectively.

copy : boolbool (default: False)

Copy instance before computation and return a copy. Otherwise, perform computation inplace and return None.

Return type

AnnData, None

Returns

Depending on copy, returns or updates adata with the following fields.

If n_branchings==0, no field dpt_groups will be written.

dpt_pseudotimepandas.Series (adata.obs, dtype float)

Array of dim (number of samples) that stores the pseudotime of each cell, that is, the DPT distance with respect to the root cell.

dpt_groupspandas.Series (adata.obs, dtype category)

Array of dim (number of samples) that stores the subgroup id (‘0’, ‘1’, …) for each cell. The groups typically correspond to ‘progenitor cells’, ‘undecided cells’ or ‘branches’ of a process.

Notes

The tool is similar to the R package destiny of [Angerer16].

format: plain


text:
# Homework Help: Adding waves of the same frequency but different phases

1. Sep 11, 2015

### lcr2139

1. The problem statement, all variables and given/known data
how do you add two waves with the same frequency but different phases?
E1 = 7*sin(omega*t + 70degrees)
E2 = 13*sin*(omega*t + 65degrees)

2. Relevant equations
Er = E1 + E2

3. The attempt at a solution
I know how to add waves that only have one phase, i.e.
E1 = E01*sin(omega*t)
E2 = E02*sin(omega*t + phase difference)

Can I subtract 65-70 degrees to make it
E1= E01*sin(omega*t)
E2 = E02*sin(omega*t - 5degrees)
?

2. Sep 11, 2015

### RUber

Kind of...it depends on what sort of result you are looking for.
Normally to adjust the phase, you would need a shift in t.
For example, $\sin (\omega t + \phi) = \sin (\omega (t+\phi/\omega) )$
So, if you replace t with $\tau$, and define $\tau = t+ \phi / \omega$, then you can have a similar set up to what you are used to dealing with and then substitute the definition for tau back into your solution to get what you are looking for.

3. Sep 11, 2015


text:
#### Volume 12, issue 2 (2012)

 Recent Issues
Author Index
 The Journal About the Journal Editorial Board Subscriptions Editorial Interests Editorial Procedure Submission Guidelines Submission Page Ethics Statement ISSN (electronic): 1472-2739 ISSN (print): 1472-2747 To Appear Other MSP Journals
Free group automorphisms with parabolic boundary orbits

### Arnaud Hilion

Algebraic & Geometric Topology 12 (2012) 933–950
##### Abstract

For $N\ge 4$, we show that there exist automorphisms of the free group ${F}_{N}$ which have a parabolic orbit in $\partial {F}_{N}$. In fact, we exhibit a technology for producing infinitely many such examples.

##### Keywords
automorphism of free group, fixed point, symbolic dynamics
##### Mathematical Subject Classification 2010
Primary: 20E05, 20E36, 37B25, 37E15
Secondary: 20F65, 37B05


text:
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Using R snippets written by other developers can be unendingly maddening.  There are a variety of reasons for this, most of which boil down to a simple issue: most code is written such that a system must be configured in precisely the same way as the code’s author’s machine.  Anyone who’s ever seen a line like this:
read.xls("C:/Users/MCaine/code/R/projecteuler/someotherdirectory/data.xls")
knows what I am talking about. To use this without modification, you must:

1. Use Windows.
2. Have exactly the directory structure specified by the address (which is highly unlikely, unless you were the one who wrote it).
3. Have the gdata package installed and included in the project (which is both unlikely, and difficult to know without already being a regular user of the package).

You can see how it would already be easier to just change the address to whatever works on your machine.  For this problem, I’m afraid I have no easy solution.  My preferred approach is to provide URLs, so that the directory structure doesn’t depend on the user’s machine, but this obviously provides its own host of problems.  However, I can take aim at this third issue.

Package management in R is a silly thing, both because it is so easy and it is so easy to screw up.  Most people who write R write it like analysts: they write exactly enough code the get the desired output on their machine, and leave it at that.  When such R Code is made public, it tends to be very difficult to use it in actual replication.  But there are some simple ways around that.

Consider this gist.  Instead of calling library(package), which fails if the library is not installed on the user’s machine, getPackage(package) invokes that safer require function, which doesn’t fail when the local machine doesn’t have the requisite package.  Instead, it returns false, which triggers the R script to download the package from the user’s default CRAN mirror and then bring it into the user’s working session.  If anything goes wrong, then it throws an error, but it won’t do that for anything silly like the user not having a package that is a mere two commands away.

One note: because of the esoteric manner in which R treats package names, you must pass this function a string and not a package name.  If you’re not on top of your type-know-how, this means that getPackage(plyr) will fail.  You should instead write getPackage("plyr").

Now, I’m sure there’s a very good reason hidden deep in R’s core that this is a bad way to do things, but it has saved me time and headaches.  R is recognized as a difficult language both within the programming world (for its strange inconsistencies and its non-grown-up hacker culture), and outside of it (because programming is hard).  I wish that more R functions were written in the defensive way to decrease the cognitive barriers to using R for the latter group.


text:
# which of the following sets are countable

are the following sets countable?

1. set of all sequences of non-negative integers.

2. The set of all sequences of non-negative integers with only a finite number of non zero terms

could any one tell me how to solve this?

-

HINTS:

For (1): Consider just the sequences of zeroes and ones. Each such sequence corresponds to a set of natural numbers: if $\langle b_0,b_1,\dots\rangle$ is such a sequence, it corresponds to the set $\{k\in\Bbb N:b_k=1\}$. Thus, there are at least as many sequences of natural numbers as there are subsets of $\Bbb N$. Is this a countable collection?

For (2): How many sequences have $0$ non-zero terms? How many have $1$ non-zero term? How many have $2$ non-zero terms? In general, how many have $n$ non-zero terms for a fixed $n>0$? And how big is a countable union of countable sets?

-
1. No.
2. Yes.

How to solve this. Depends on your level.

1. Let $S = \mathbb{N}^{\mathbb{N}}$ the set of all sequences, clearly $\{0,1\}^{\mathbb{N}}$ can be seen as subset. But any function on $\mathbb{N}$ that takes only values $0$ and $1$ is uniquely described by it's preimage under $0$, so corresponds to an element of $\mathcal{P}(\mathbb{N})$, an uncountable set. You can think of choosing an element of $\mathbb{N}$ to be in a subset if its value under the sequence is $1$ and not be in it if its value is $0$.

2. This set is a countable union of a finite product of countable sets and therefore countable. You can imagine it to be $S_0 = \mathbb{N}^{(\mathbb{N})} = \bigcup_{k \in \mathbb{N}} \mathbb{N}^k$, where $k$ is the "word"-length of such a sequence, before it becomes constantly zero, and $\mathbb{N}^k$ to capture the first $k$ entries in this sequence.

-
1. $\mathbb{N}^{\mathbb{N}} \geq 2^{\mathbb{N}}=\mathcal{P}(\mathbb{N})$, so $\mathbb{N}^{\mathbb{N}}$ is uncountable.

2. If $E$ is the set of non-negative integers with only a finite number of non zero terms, there is a surjection from $\cup_{n \in \mathbb{N}} \mathbb{N}^n$ onto $E$. So $E \leq\cup_{n \in \mathbb{N}} \mathbb{N}^n$. This is a countable union of countable sets, so it is countable.

-


text:
# Tag Info

Proposition aimed at 1/2/3/4 of the last section of the question: chained hybrid encryption. We'll use A fast symmetric authenticated encryption scheme, such as AES-GCM or ChaCha20-Poly1305 with 256-bit secret key, encryption with key $K$ noted $C=E_K(M)$ and decryption $M=D_K(C)$. An asymmetric encryption scheme capable of encrypting 256-bit messages, with ...
Alternatively, is there a way to generate three random number sequences R1, R2, R3 from three keys K1, K2, K3 such that R1 XOR R2 XOR R3 = 0? That part's easy; we can just define: $$R1 = \text{SHAKE}(K1) \oplus \text{SHAKE}(K2)$$ $$R2 = \text{SHAKE}(K3) \oplus \text{SHAKE}(K1)$$ $$R3 = \text{SHAKE}(K2) \oplus \text{SHAKE}(K3)$$ (where $\text{SHAKE}$ can be, ...


text:
# [NTG-context] We have a problem --- Old file no longer compiles

Thu Jul 5 00:35:07 CEST 2007

On Wed, 4 Jul 2007, Aditya Mahajan wrote:

> On Wed, 4 Jul 2007, David Arnold wrote:
>
>> Here is another example, this time not within a block, but within an
>> enumeration again:
>
>
> \unexpanded\def\frac#1#2{\mathematics{\genfrac{}{}{}\donothing{#1}{#2}}}
>
> and it should work fine. I do not really understand why this is
> failing.

Ok. The third argument of \genfrac should be {} and not \empty,
otherwise \ifx @#3@ in \genfrac evaluates to false. So, either we need
to change \ifx @#3@ to something more robust, or revert back to older
definitions of (d|t)frac.


text:
# Lumos StepUp - SBAC Online Practice and Assessments - Grade 11 Mathematics Tangent to a circle

#### Get Full Access to Lumos StepUp - SBAC Online Practice and Assessments - Grade 11 Mathematics

Currently, you have limited access to Lumos StepUp - SBAC Online Practice and Assessments - Grade 11 Mathematics. The Full Program includes,

Online Program

## A worker wishes to determine the radius of a fluid tank, but access is only available to the outside of the structure. The worker devises a plan to determine the radius by utilizing the relationship of the tangent line to the radius as shown in the diagram below.The following measurements were taken.AB = AC = 12 ft. AD = 6 ft. Complete the steps below to determine the radius of the tank.a) Determine $$\textit{m}\;\angle ABO.$$

### Ratings

Rate this Question?
0

0 Ratings & 0 Reviews

5
0
0
4
0
0
3
0
0
2
0
0
1
0
0


text:
# 9.5: Untitled Page 221

## Chapter 9

problem is to assume that the net rate of production of the reactive intermediate or the Bodenstein product can be approximated by

Local Reaction Equilibrium:

R

 0

(9‐51)

A

This simplification is often referred to as the steady‐state assumption or the steady state hypothesis or the pseudo steady state hypothesis. These are appropriate phrases when kinetic mechanisms are being studied by means of a batch reactor; however, the phrase local reaction equilibrium is preferred since it is not process-dependent. Use of Eq. 9‐51 with Eq. 9‐50b leads to

I

II

III

2

R

R

R

k c

k c

k c c

0

(9‐52)

A

A

A

I A

II A

III A A

and from this we determine the concentration of the reactive intermediate to be 2

k c

I A

c

(9‐53)

A

k k

c

II

III A

We now make use of Eq. 9‐50c to express the net rate of production of ethane as I

II

III

R

R

R R

R

(9‐54)

B

B

B

B

C2H6

and application of Eqs. 9‐48c and 9‐48d provides the chemical reaction rate equation given by

R

k c

(9‐55)

C

2H6

II

A

At this point we use Eq. 9‐53 in order to express the net rate of production of ethane as

2

k k c

I

II A

R

C2H6

k

(9‐56)

k

c

II

III A

in which c represents the concentration of azomethane, (CH ) N . Here we A

3 2

2

can see that the two limiting rate expressions for high and low concentrations are given by

2

k k c

k k / k

c , high concentration

I

II A

 I II

III 

A

R

(9‐57)

C

2H6

2

k

k

c

II

III

A

k c

, low concentration

I A

Reaction Kinetics

411

which is consistent with the experimental results of Ramsperger (1927) illustrated by Eq. 9‐29. We can be more precise about what is meant by high concentration and low concentration by expressing these ideas as c

 k / k ,

high concentration

A

II

III

(9‐58)

c

 k / k ,

low concentration

A

II

III

Here we see that the relatively simple process suggested by Eq. 9‐27 is governed by the relatively complex rate equation indicated by Eq. 9‐56. The analysis leading to this result is based on three concepts: (A) local and elementary stoichiometry, (B) mass action kinetics, and (C) the approximation of local reaction equilibrium. The simplifying assumptions associated with this development are discussed in the following paragraphs.

Assumptions and Consequences

A reasonable assumption concerning the continuous stirred tank reactor shown in Figure 9‐5 is that only azomethane, ethane and nitrogen participate in the reaction. This assumption, in turn, leads to the chemical kinetic schema illustrated both in Eq. 9‐27 and in Figure 9‐6. Experimental measurement of the concentrations in the inlet and outlet streams might confirm the assumption that only (CH ) N , C H and N are present in the reactor. However, the 3 2

2

2

6

2

experimental determination of the reaction rate is not in agreement with Eq. 9‐28.

In reality, our analysis is based on the restriction that no significant amount of reactive intermediate enters or exits the reactor, and we state this idea as

at the entrance and

Restriction:

c

 c , c , c ,

(9‐59)

A

A

B

C

exit of the reactor

While the concentration of the reactive intermediate might be small compared to the other species, it is certainly not zero. If it were zero, Eq. 9‐55 would indicate that the rate of production of ethane would be zero and that is not in agreement with experimental observation.

Given that c

is not zero, one can wonder about the assumption (see A

Eq. 9‐51) that R

is zero. In reality, R

A

A must be small enough so that it can be

approximated by zero, and we need to know how small is small enough. To find out, we make use of Eq. 9‐50b to determine that the net rate of production of A

is given by

412


text:
## Simple Probability

13.4  Simple Probability

 Example A box contains $$8$$ green balls, $$12$$ black balls and a number of white balls. A white ball is chosen at random from the box. The probability of getting a white ball is $$\dfrac{3}{7}$$. What is the number of white balls in the box? Let $$w$$ be the number of white balls. Then, \begin{aligned}n(S)&=8+12+w\\\\&=20+w.\\\\\end{aligned} So, \begin{aligned} P(w)&=\dfrac{n(w)}{n(S)} \\\\\dfrac{3}{7}&=\dfrac{w}{20+w} \\\\3(20+w)&=7(w) \\\\60+3w&=7w \\\\4w&=60 \\\\w&=15.\\\\ \end{aligned} Thus, the number of white balls in the box is $$15$$.


text:
# The two-element boolean algebra generates the variety of boolean algebras

I just want to check that my proof is correct. For a given variety $K$, I let $F_K(X)$ denote the free $K$-algebra with generator set $X$.

Lemma 1. Assume a variety $V$ has arbitrary (small) coproducts as a category, which we denote by $\sqcup$. Then for all set $X$, $F_V(X) \simeq \displaystyle\sqcup_{x\in X} F_V(\{x\})$

Indeed, let $f: X\to A$ be any function, where $A$ is the underlying set of the algebra $\mathfrak{A}$. Then we obtain restriction functions $f_x: \{x\} \to A$ for all $x\in X$, and thus we obtain a unique morphism $\overline{f}_x: F_V(\{x\}) \to \mathfrak{A}$ and thus by the universal property of coproducts we get a unique morphism $\displaystyle\sqcup_{x\in X} F_V(\{x\}) \to \mathfrak{A}$.

Thus $\displaystyle\sqcup_{x\in X} F_V(\{x\})$ has the universal property of the free algebra with generating set $X$, thus it is isomorphic to it.

Lemma 2. Let $V$ be the variety of boolean algebras. Then $V$ has arbitrary (small) coproducts.

(2nd EDIT: For those interested, it's in this proof that the error noted by Keith Kearnes lies. What I call $\mathfrak{C}$ is not a subalgebra of $\mathfrak{B}$ )

Let $(\mathfrak{B}_i)_{i\in I}$ be a family of boolean algebras. We let $\mathfrak{B}= \displaystyle\prod_{i\in I} \mathfrak{B}_i$, and $\mathfrak{C}$ is the subalgebra of $\mathfrak{B}$ whose elements are those with only a finite number of nonzero coordinates, or all of its coordinates are $1$. Obviously, $\mathfrak{C} \in \mathbf{SP}(V) = V$.

We want to show that $\mathfrak{C}$ is a coproduct of the $\mathfrak{B}_i$'s. Let $\iota_i : \mathfrak{B}_i \to \mathfrak{C}$ be the morphism that sends $b$ to the family consisting of all $0$'s + a $b$ in place $i$. Let $f_i : \mathfrak{B}_i \to \mathfrak{A}$ be algebra homomorphisms.

Assume we have a morphism $f: \mathfrak{C}\to \mathfrak{A}$ such that $f\circ \iota_i = f_i$. Then for $c=$ all zeroes except in positions $i_1,...,i_n$ where there is $b_1,...,b_n$, well $c= \iota_{i_1}(b_1)\lor ... \lor \iota_{i_n}(b_n)$ so that $f(c)= f\circ\iota_{i_1}(b_1)\lor...\lor f\circ\iota_{i_n}(b_n) = f_{i_1}(b_1)\lor...\lor f_{i_n}(b_n)$ and $f(1,...,1,...) = 1$. Therefore $f$ is unique.

Conversely, defining $f$ by the above formulas shows that $f$ exists : $\mathfrak{C}$ is a coproduct (and so, up to isomorphism, the coproduct) of the $\mathfrak{B}_i$'s.

Lemma 3. Let $V$ be the variety of boolean algebras. For all $x$, $F_V(\{x\}) \in \mathbf{HSP}(\mathbf{B}_2)$ where $\mathbf{B}_2$ is the $2$-element boolean algebra.

It suffices to show it for one $x$, since all free algebras on one generator are isomorphic. For this we thus describe the free boolean algebra on one element. Let $B= \{ 0, x, y 1\}$ where $x\neq 0, 1$.Defining $x\land x= x, x\lor x = x, x\land 1= x, x\lor 1 = 1, x\land 0 = 0, x\lor 0 = x$, similar clauses for $y$, and $x\lor y = 1, x\land y =0$, $x' = y$, $y' = x$, we get that the algebra $\mathfrak{B}$ is a boolean algebra, and it is obviously free with one generator. Moreover, $\mathfrak{B} \simeq \mathbf{B}_2 ^2$. Indeed, sending $x\to (1,0)$ for instance provides an isomorphism.

Conclusion: By Lemma 3, for all $x$, $F_V(\{x\}) \in \mathbf{HSP}(\mathbf{B}_2)$. By lemmas 1 and 2, for all $X$, $F_V(X) \in \mathbf{HSP}(\mathbf{B}_2)$. Since any boolean algebra is the homomorphic image of a free boolean algebra, it follows that for any $\mathfrak{B}\in V$, $\mathfrak{B} \in \mathbf{HSP}(\mathbf{B}_2)$. It therefore follows that $V= \mathbf{HSP}(\mathbf{B}_2)$

Thank you for reading so far. My questions are: is this proof valid ? Are there any easier proofs of this fact ? Or not necessarily simpler, but essentially different ?

EDIT: Hopefully this remark will save the proof (which is not correct according to an answer below): when I claim that $F_V(X) \in \mathbf{HSP}(\mathbf{B}_2)$, it is because the coproduct of boolean algebras is a subalgebra of their product, that is it belongs to the variety generated by these algebras. Maybe I should have made this clearer by stating lemma 2 as "Let $V$ be a variety of boolean algebras" instead of "Let $V$ be the variety of boolean algebras".

• In the proof of Lemma 2, the functions $\iota_i$ are not BA morphisms. Jun 28, 2017 at 11:28
• @KeithKearnes : Yes actually it seems I completely forgot about the complements. Jun 28, 2017 at 11:34

## 1 Answer

The proof is not correct.

Let $V$ be the variety of Boolean algebras (= the variety axiomatized by the identities of Boolean algebras). The 2-element BA belongs to $V$, so $HSP(B_2)\subseteq V$. You correctly claim that $F_V(\{x\})$ belongs to $HSP(B_2)$. You then incorrectly deduce that the coproduct $F_V(X)$ must also belong to $HSP(B_2)$ for any $X$, and hence that $V=HSP(B_2)$.

Given varieties $U\subseteq V$, the coproduct of $U$-algebras, computed in $V$, need not belong to $U$. (Here $U=HSP(B_2)$.) Otherwise we would have $V = HSP(F_V(\{x\}))$ for every variety. This fails for the varieties of groups, rings, lattices, ETC.

For a correct proof, might try these steps:

1. Every variety is generated by is subdirectly irreducible members.
2. $B_2$ is the only subdirectly irreducible member of the variety axiomatized by the identities of Boolean algebra.
• But here I show that the coproduct is the subalgebra of the product, so why not ? Si $HSP(B_2)$ is stable under these operations, and $F_V(\{x\}) \in HSP(B_2)$, then any subalgebra of any product of $F_V(\{x\})$'s must belong to $HSP(B_2)$, and so, since $F_V(X)$ is isomorphic to said coproduct, it must also be in $HSP(B_2)$. Where's the mistake in that ? Thank you for your answer ! Jun 28, 2017 at 11:00
• If in lemma 2, I had written "a variety of boolean algebras", instead of "the variety", the proof would go similarly, would it not ? Jun 28, 2017 at 11:01
• But here I show that the coproduct is the subalgebra of the product...'' The statement of Lemma 2 is correct, but its proof is not. (1) $\mathfrak C$ is not a subalgebra. (2) in general, the coproduct of two BA's is not embeddable in their product. Jun 28, 2017 at 11:11
• Oh right, I had forgotten about the complements ! That's why $\mathfrak{C}$ is not a subalgebra, right ? (or I made yet another mistake ?) Thank you so much ! Jun 28, 2017 at 11:18
• (and thank you for the correct proof, I can show both of the items and therefore I can conclude !) Jun 28, 2017 at 11:57


text:
What is the integral of 0?

I am trying to convince my friend that the integral of 0 is C, where C is an arbitrary constant. He can't seem to grasp this concept. Can you guys help me out here? He keeps saying it is 0.

-
Let $0$ be the only answer to the integral of $\int0\;dx$. Thus, $\dfrac{d}{dx}f(x)=0$ is satisfied ONLY by $f(x)=0$ However, Let $f(x)=0+c,c\in \mathbb{R}$. $$\dfrac{d(0+c)}{dx} =0$$ Thus the assumption that there is only one function satisfying the condition is false. $$\blacksquare$$ –  Inquest Jan 26 '13 at 2:30
Whether or not the integral is $0$ or $C$ depends on whether you are talking about the indefinite or definite integral. –  anon Jan 26 '13 at 2:47
Maybe it is confusing cause it is "the" integral. Make it clear that "the" integral is not a single function.... –  N. S. Jan 26 '13 at 3:14
Definite integrals $\ne$ Primitive integrals $=$ Antiderivatives. –  Did Jan 26 '13 at 3:15
Definite integrals still have a constant, but the constant cancels itself out. –  Ryan Amos Jan 26 '13 at 12:56
show 1 more comment

Taking the derivative of any constant function is 0, i.e. $\frac {d}{dx} c = 0$ So the indefinite integral $\int0 \,dx$ produces the class of constant functions, that is $f(x) = c$ for some $c$.

There's something that you have to look at here though, that is "what about the fact $\alpha \int f dx = \int \alpha f dx$?" Can't you say:

$$\int 0 dx = \int 0 \cdot 1 \,dx = 0 \int 1 \,dx = 0x = 0$$

This gives two conflicting answers. The question is far more complicated that you would first think. But when you say $\int f dx$ and the interval over which you're integrating isn't obvious or defined, what you really mean is "the class of functions that when derived with respect to $x$ produce $f$". The rule stated only applies for definite integrals. That is:

$$\int_a^b\alpha fdx = \alpha \int_a^bf dx$$

And if you look at textbooks on real analysis (I just looked at Rudin) that's the form in which you will find the theorem.

It should also be noted that the definite integral of $0$ over any interval is $0$, as $\int 0 dx = c - c = 0.$

-

You are correct, $\int 0 dx = 0 + C = C$

Your friend is not entirely wrong because $C$ could equal $0$. ie. if
$f(x) = 0$ is one antiderivative. But in general we do not know $C$ unless we are given some initial condition.

-
@downvote ??? Lol. –  Rustyn Jan 26 '13 at 6:02
If $C$ is assumed to be selected randomly, the probability that the friend is right is 0. [tongue in cheek] –  Thomas Jan 26 '13 at 7:19

How about drawing sum upper and lower sums! You won't get very far because you'll be married to the horizontal axis and then, of course, all of the sums are zero and since a definite integral is always sandwiched between any upper and any lower sum. The value is trapped by 0. I.E. 0 <= the integral <= 0. This of course works only for a definite integral. If you are looking for an anti derivative, it shouldn't be too hard to convince your buddy that only constant functions f(x) = C have zero slope.

-
Indefinite integrals (anti-derivatoves) are known modulo a constant function. With definite integrals, the case is different: $$\int_a^b0\,\mathrm{d}t=0$$
One way to verify that $C$ is the anti-derivative of $0$ is simply $$\frac{\mathrm{d}}{\mathrm{d}t}C=0$$


text:
# Spearman's rho correlation coefficient and p-values

I am analysing data from questionnaires. I have 344 valid responses. When I run the spearman's rho correlation test to see if there's any correlation between students' home province and their attitudes to a number of other criteria I get low coefficient values (mostly positive but some negative) but high p-values. The coefficient values and their corresponding p-values are:

0.037/0.496,
0.014/0.795,
-0.049/0.363,
0.03/0.574,
0.029/0.597,
-0.026/0.636,
0.104/0.053,

I think that in most of these cases the coefficient values mean that the correlation is slightly positive or negative (depending) and the high p-values mean that there is strong evidence to support the null hypothesis. Is it accurate of me to argue that while the correlation coefficient values are low they could be seen as significant as there is a large number of responses (344). Would that be a correct understanding of this data?

• Please clarify how you are using Spearman's test for this purpose. That test compares two variables that have ranks, and it's not clear how you could put ranks on the home provinces. – EdM Jun 21 '16 at 14:38
• Welcome to CV. Based on the brief description, it sounds to me like you may be misusing the correlation coefficient. Home province is nominally scaled or categorical information, even if it's given a number from, e.g., 1 to 5. You need to elaborate more on how you're doing your analysis. – Mike Hunter Jun 21 '16 at 14:38

Both @EdM and @DJohnson are right to point that it is not clear that you can use Spearman's test on this data, because home province is a categorical variable. An alternative approach you might want to use is to compare the mean responses to a question for students of different provinces to see if province might influence their attitudes.

Whether or not something is "significant" depends on the choice you made of what is a "significant" result. Basically, you define a priori a p-value below which you will consider a correlation significant. It is possible that your field has a "traditional" level often used for sigificance.

Most of the p-values that you report above are very high and therefore it indicates that you do not have enough evidence to reject the null hypothesis which is that there is no correlation between your different variables. Therefore you should conclude that you have not found any significant correlations, if it weren't for the fact that probably your first issue here is that you should use a different test.

There is a lot of discussion around p-values and their use. One thing to keep in mind is that with enough data, every relationship is likely to appear significant (meaning it will get a small p-value in a correlation or regression context), but that might not mean that it has practical relevance (because more data will allow you to detect effects that are smaller in size).

Two places to start learning more about p-values:

Understanding p-value

p-value related posts on Andrew Gelman's blog

• I've ranked the provinces from 1 to 30 with 1 corresponding to the province with the highest average rate of disposable income and 30 corresponding to the province with the lowest average rate of disposable income. My field is Applied Linguistics. This is my first time doing statistical analysis and I'm still trying to figure out SPSS, what scales to apply to different variables. Thank you very much Antoine for those links. – Rob D Jun 21 '16 at 17:03
• @RobD So what you're really doing is a rank-based correlation between mean home province disposable income and attitude, which is a reasonable analysis. From the original post, it seemed that provinces had no particular ordering, which would be a big problem for correlation analysis (since changing the arbitrary ordering would give different results). – Nuclear Wang Nov 21 '18 at 15:28


text:
Pysound simple sine waves

Martin McBride
2021-09-30

In this example, we will create a simple sine wave.

The code

Here is the code:

from pysound.buffer import BufferParams
from pysound.oscillators import sine_wave
from pysound import soundfile
from pysound.graphs import Plotter

params = BufferParams()
out = sine_wave(params, frequency=500)
soundfile.save(params, 'sine-500.wav', out)

After importing several modules, there are just 3 lines of code.

First, we create a BufferParams object. This object controls the length of the sound, and also the sample rate. The default constructor specifies a sound that is 1 second long, and has a sample rate of 44,100 samples per second (this is the sample rate used by an audio CD):

params = BufferParams()

Next, we call the sine_wave function, which creates a sine wave tone.

out = sine_wave(params, frequency=500)

We pass in the params object to tell the function how long the sound should last, and what sample rate to use.

We also pass in a frequency of 500, to set the wave frequency to 500 Hz.

The sine_wave function takes several other parameters too, but we will use the default values. This creates a sine wave tone with an audio frequency of 500 Hz and an amplitude of 1.0.

The function returns a NumPy array, that we store in out.

Finally, we write the data out to a WAV file:

soundfile.save(params, 'sine-500.wav', out)

This takes the data and converts it to WAV format. It is stored as sine-500.wav in the current folder.

Listening to the sound

You should be able to play the wav file using your system media player.

You can also use Audacity, an open-source audio editor. This is a very useful program that can be used to play, view and edit sound files, it is well worth installing.

Plotting the wave

The Pysound graphs module allows us to create a plot of a sound buffer.

We use the Plotter object to create a graph of the first part of the wave:

## Plot a graph of the first part of the previous sine wave
Plotter(params, 'sine-500.png', out).with_timerange(0, 0.01)\
.with_title("500 Hz sine wave")\
.in_milliseconds()\
.plot()

The Plotter constructor accepts params and out from the previous code, and also the string 'sine-500.png' which tell Pysound where to store the image file.

We also set the time range, so that the plot only includes the first 0.01 seconds of the wave.

Since the wave has a frequency of 500 Hz, one cycle of the wave takes 0.002 seconds (ie, one 500th of a second). This means that the first 0.01 seconds of the waveform contains 5 full cycles of the wave. Here is the graph:

The graph is scaled in milliseconds (ms) as this is easier than dealing with small fractions. 0.01 seconds is 10 ms, 0.002 seconds is 2 ms.

If we tried to plot the whole one second of the wave, we wouldn't be able to see the individual waves, they would be far too close together. By plotting a 10 ms section of the wave, the waveform can be seen easily.

For a full description, see the later tutorial on the graphs module.


text:
# A short survey of von Neumann regular rings

I’ve talked a lot about von Neumann regular rings on this blog, so I thought I’d write an informal short survey on them, collecting some facts we’ve already seen and many new ones. It should give you an idea of what von Neumann regular rings are. Most of the facts that I did not explicitly cite here are found in the book

Goodearl, K. R. von Neumann regular rings. Second edition. Robert E. Krieger Publishing Co., Inc., Malabar, FL, 1991. xviii+412 pp. ISBN: 0-89464-632-X

## The definition

A von Neumann regular ring is an associative ring $A$ such that for each $x\in A$ there exists a $y\in A$ such that $xyx = x$. A popular alternative and equivalent definition is that a ring $A$ is von Neumann regular if and only if every left $A$-module is flat. This is in fact equivalent to every right $A$-module being flat. So we can just drop left and right here.

## Examples of von Neumann regular rings

A ring $A$ is von Neumann regular if and only if every $A$-module is flat. So in particular, fields are von Neumann regular. You can also see that using the other definition: if $x$ is a nonzero element in a field, then $xx^{-1}x = x$. If $x = 0$, then any $y$ such as $y=0$ satisfies $xyx = x$.

By the Artin-Wedderburn theorem, finite products of full matrix rings over division rings are von Neumann regular. That’s because So for example, the ring of $2\times 2$ matrices over a field is von Neumann regular.

It’s easy to see that von Neumann regular rings are closed under taking arbitrary products. So infinite products of fields and full matrix rings over division rings are also von Neumann regular. Such examples give von Neumann rings that are not semisimple: for example, in the infinite product $A = \prod_{i=1}^\infty F$ where $F$ is a field, the infinite direct sum $I = \oplus_{i=1}^\infty F$ is such that $A/I$ is flat but not projective. For a proof, see my post on a finitely-generated flat module that is not projective.

Here are some ring constructions and how they can produce von Neumann regular rings:

Theorem. von Neumann regular rings are closed under the following operations:

1. Direct products
2. Direct limits
3. Homomorphic images
4. Centers

All four conditions are suggested exercises for the reader. Another way to get von Neumann regular rings is to take endomorphisms:

Theorem. For any finitely-generated projective module $M$ over a von Neumann regular ring $A$, the endomorphism ring ${\rm End}_A(M)$ is von Neumann regular.

## Equivalent conditions

We have already mentioned this somewhat, but here is a fleshing out of the most basic equivalent conditions for a ring to be von Neumann regular.

Theorem. For an associative ring $A$, the following are equivalent:

1. $A$ is von Neumann regular
2. Every $A$-module is flat
3. For every left ideal $I$ of $A$, the left $A$-module $A/I$ is flat
4. For every right ideal $I$ of $A$, the right $A$-module $A/I$ is flat
5. Every principal left (right) ideal is generated by an idempotent
6. Every finitely generated left (right) ideal is generated by an idempotent

Here is the sketch of the proof that a ring is von Neumann regular if and only if every principal ideal is generated by an idempotent. First, if $A$ is von Neumann regular and $xR$ is a principal right ideal, select a $y$ such that $xyx = x$. Then $yx$ is an idempotent and $xyA = xA$. Conversely, suppose every right ideal is generated by an idempotent. Then for any $x\in A$, we have $xA = eA$ for some idempotent $e\in A$. By definition, there exists a $y\in A$ such that $e = xy$, and $y$ is an element such that $xyx = x$.

In the paper

Ming, Roger Yur Chi. On (von Neumann) regular rings. Proc. Edinburgh Math. Soc. (2) 19 (1974/75), 89—91

Ming gave some conditions for a ring to be von Neumann regular. He proved that a reduced ring $A$ is von Neumann regular if and only if every principal left ideal is the left annihilator of some element of $A$. That’s not really for all von Neumann regular rings, though. But he also gave the following equivalent conditions:

Theorem. For an associative ring $A$, the following are equivalent:

1. $A$ is von Neumann regular
2. Every left $A$-module is $p$-injective
3. Every left cyclic $A$-module is $p$-injective

Recall that a left $A$-module $M$ is $p$-injective if for every left principal left ideal $I$ of $A$ and every left $A$-module homomorphism $f:I\to M$, there exists a $y\in M$ such that $f(b) = by$ for all $b\in I$. This is just the usual Baer criterion for injectivity, but restricted to principal ideals. Of course, if every $A$-module were injective, then $A$ would be semismimple, and hence every $A$-module would be projective.

## Commutative von Neumann regular rings

Commutative von Neumann regular rings are not as hard to characterize.

Theorem. The following are equivalent for a commutative ring $A$:

1. $A$ is von Neumann regular
2. The localization $A_M$ is a field for all maximal ideals $M$ of $A$
3. $A$ is reduced and has Krull dimension zero
4. All simple $A$-modules are injective

I already talked a little bit about the equivalency of (1) and (3).

## Structure theorems for modules

A classic structure theorem for von Neumann regular rings is:

Theorem. If $M$ is a countably generated projective right module over a von Neumann regular ring $A$, then $M$ is a direct sum of modules, each of which is isomorphic to a principal right ideal of $A$.

## Unit regular rings and K-Theory

For a ring $A$, let $A^\times$ denote the group of units of $A$, and let $V(A)$ be the subgroup of $A^\times$ generated by the set
$$\{ (ab+1)(ab + 1)^{-1} : ab + 1\in A^\times\}.$$ A von Neumann regular ring $A$ is called unit regular if for each $x\in A$ there exists a unit $y\in A$ such that $xyx = x$. Unit regular rings satsify the cancellation law for finitely-generated projective modules: if $M,N_1,N_2$ are such modules over a unit regular ring, then $M\oplus N_1\cong M\oplus N_2$ implies $N_1\cong N_2$. Another equivalent condition for unit regular is: a von Neumann regular ring is unit regular if and only if whenever $xA + yA = A$, there exists a $z\in A$ such that $x + yz$ is a unit (“stable range 1” condition).

Mencal and Moncasi in

Menal, Pere; Moncasi, Jaume. $K_1$ of von Neumann regular rings. J. Pure Appl. Algebra 33 (1984), no. 3, 295—312.

proved the following:

Theorem. If $A$ is a unit regular von Neumann regular ring then $K_1(A) \cong A^\times/V(A)$.

Going back to unit regular rings, there is a slightly stronger condition for cancellation. A von Neumann regular ring is called separative if for every finitely-generated projective $A$-modules $M$ and $N$, the two conditions

1. $M\oplus M\cong M\oplus N$
2. $M\oplus N\cong N\oplus N$

imply that $M\cong N$ as $A$-modules. In the paper

Ara, P.; Goodearl, K. R.; O’Meara, K. C.; Pardo, E. Diagonalization of matrices over regular rings. Linear Algebra Appl. 265 (1997), 147—163

the authors proved that if $X$ is a square $k\times k$ matrix over a separative von Neumann regular ring, there exists $k\times k$ matrices $Y$ and $Z$ such that $ZXY$ is diagonal.

Let us end with a characterization of unit regular rings given in the paper

Camillo, Victor P.; Khurana, Dinesh. A characterization of unit regular rings. Comm. Algebra 29 (2001), no. 5, 2293—2295.

Here, the authors prove:

Theorem. An associative ring $A$ is unit regular if and only if for every $x\in A$, there exists an idempotent $e\in A$ and a unit $u\in A$ such that $x = e + u$ and $eA\cap xA = \{0\}$.


text:
# Warning when adding package minted?

I am for some reason getting an warning when i try to load the package minted in sharelatex.

The warning is

Command \@parboxrestore has changed.

Package fvextra Warning: csquotes should be loaded after fvextra, to avoid a warning from the lineno package on input line 37.

I am not sure how i should interpret this?.. I've been very picky with my error messages, and trying avoid all kind of error messages, so why am I getting this warning when using minted in sharelatex, and how do i get rid of it?

Here is my preamble.tex

\documentclass[11pt,twoside]{article}

% ------- Enable UTF8 characters ------- %
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}

\usepackage[toc,page]{appendix}

\usepackage{listings}
\usepackage{color}
\usepackage[colorinlistoftodos]{todonotes}

\usepackage{epstopdf}
\usepackage{csquotes}
\usepackage{wrapfig}
\usepackage{pdfpages}
\usepackage{todonotes}
\usepackage{multicol}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{commath} % Added by Me - Used for norm
\usepackage{smartdiagram} % Added by Me - Smartdiagram
\usepackage{glossaries} % Added by Me - Glossary
\usepackage[shortlabels]{enumitem}
\makeglossaries
%-------------- Glossary -----------------%
\input{glossaries/glossaries_entries.tex}
% ------------ Code Listing ------------- %

\usepackage{minted}

% ------- Page layout ------- %
\usepackage{fullpage}
\usepackage{hyperref} % clickable references
\hypersetup{
citecolor=black,
filecolor=black,
urlcolor=black
}
\usepackage{multicol}
\setlength{\columnsep}{1cm}

% ------- Images ------- %
\usepackage{graphicx}
\usepackage{caption}
\usepackage{float}
%\usepackage{subfigure}
\usepackage{subcaption}
%\DeclareCaptionFont{gray}{\color{gray}}
%\captionsetup{textfont={footnotesize,sc,gray},font={footnotesize,sc,gray}}

\newcommand{\figscale}{0.7\linewidth}
\newcommand{\smallfigscale}{0.07\linewidth}

\usepackage{blindtext}

%References
%\usepackage[numbers]{natbib} %Natbib supports both [i] and Author (year) citation styles. \citet and \citep replace \cite.
%\bibliographystyle{ieeetr}
%\bibliographystyle{plainnat}
\usepackage{url}

\usepackage[style=ieee,natbib=true,backend=biber,bibencoding=utf8,url=true]{biblatex}

\usepackage{fancyhdr}

% Test

\usepackage{tikz}
\newcommand{\mx}[1]{\mathbf{\bm{#1}}} % Matrix command
\newcommand{\vc}[1]{\mathbf{\bm{#1}}} % Vector command
minimum width=3.5cm,minimum height=1cm,align=center,node distance=1.5cm]
\tikzstyle{inter arrow}=[->,ultra thick,-{Triangle[angle=45:8pt]}]

• Well, you're loading csquotes before minted (which in turn loads fvextra). Change the loading order. By the way, hyperref should be loaded last. – egreg Jul 15 '17 at 18:36

The fvextra package is loaded by minted, so you should load minted before csquotes.
Another thing you should do is loading hyperref last: very few packages should come later than this one and you are loading none of them.
Side note: commath is a very buggy package
• Do you have an alternative to commath – dfh Jul 15 '17 at 19:40


text:
## Riddler Classic for 23 March 2018 (part 2)

We’ve seen a generalization of the problem to multiplicative factors other than 2 and bases other than 10. A third generalization would be to shift more than one digit.

Take a positive integer $j$ in base $b$ and move its last $m$ digits to the front. What is the smallest $j$ such that when you do this, the result $k$ is exactly $p$ times $j$ (where $p$ is in the range $[2,b-1 ]$)?

Let $j= b^m \times y+x$, where $b^{m-1}\le x< b^m$ . So the digits of $x$ are the final $m$ digits of $j$ and the initial $m$ digits of $k$, and the digits of $y$ are the remaining digits of both. Let $n$ be the number of digits in $y$. Then we require

$p(b^my+x)= b^nx+y$.

Solving, $(pb^m-1)y=(b^n-p)x$ or

$y= \frac{b^n -p}{pb^m-1}x .$

Now let $g=\gcd(pb^m-1,x)$ and let $w=x/g$, $v=(pb^m-1)/g$. Then

$y= \frac{b^n-p}{v}w$

and since $v$ and $w$ are relatively prime, we must have

$b^n=p\mod v$.

So we must calculate $pb^m-1$ and then, for each possible value of $x$, obtain $v$ and look for the least $n$ that satisfies the above relation. (The minimal value of $x$ is in fact not $b^{m-1}$ but $pb^{m-1}$, since there can be no carry to an additional digit when $j$ is multiplied by $p$.) Then we can compute $y$, and verify that it does indeed have $n$ digits. The smallest such $y$ and associated $x$ solve the problem.

If $(pb^m-1)$ is prime, then $v = (pb^m-1)$ for all possible $x$ and the smallest $k$ results when $x=pb^{m-1}$. But if $(pb^m-1)$ has a common factor with some $x$, then $v$ is some factor of $(pb^m-1)$. Generally $n$, the number of digits in $y$, is on the order of $v$, so when $(pb^m-1)$ is prime the solution tends to be many orders of magnitude larger than when it is not.

For instance, consider $p=3$ and $b=10$. For $m=2$, $(pb^m-1)=299=13\times 23$. In that case some values of $x$ have a common factor with $(pb^m-1)$. E.g., $x=46$ gives

$y= \frac{10^n-3}{13}w$

where

$10^n=3\mod 13$.

The solution is $n=4$, leading to

$j=153846$, $k=3j=461538$.

But for $m=1$, $(pb^m-1)=29$ is prime. The number of digits in $y$ then turns out to be 27, and

$j=1034482758620689655172413793$.

And for $m=3$, $(pb^m-1)=2999$ is prime too. We end up with the 1499 digit solution

$j = 100033344448149383127709236412137379126375458486162054018006\\ 0020006668889629876625541847282427475825275091697232410803601200\\ 4001333777925975325108369456485495165055018339446482160720240080\\ 0266755585195065021673891297099033011003667889296432144048016005\\ 3351117039013004334778259419806602200733577859286428809603201067\\ 0223407802600866955651883961320440146715571857285761920640213404\\ 4681560520173391130376792264088029343114371457152384128042680893\\ 6312104034678226075358452817605868622874291430476825608536178726\\ 2420806935645215071690563521173724574858286095365121707235745248\\ 4161387129043014338112704234744914971657219073024341447149049683\\ 2277425808602867622540846948982994331443814604868289429809936645\\ 5485161720573524508169389796598866288762920973657885961987329109\\ 7032344114704901633877959319773257752584194731577192397465821940\\ 6468822940980326775591863954651550516838946315438479493164388129\\ 3764588196065355118372790930310103367789263087695898632877625875\\ 2917639213071023674558186062020673557852617539179726575525175058\\ 3527842614204734911637212404134711570523507835945315105035011670\\ 5568522840946982327442480826942314104701567189063021007002334111\\ 3704568189396465488496165388462820940313437812604201400466822274\\ 0913637879293097699233077692564188062687562520840280093364454818\\ 2727575858619539846615538512837612537512504168056018672890963654\\ 5515171723907969323107702567522507502500833611203734578192730910\\ 3034344781593864621540513504501500500166722240746915638546182060\\ 6868956318772924308102700900300$.

If you’d asked me to guess, before I worked any of this out, the order of magnitude of the smallest positive integer which is exactly tripled when you move the last three digits to the front, I’m pretty sure I would have seriously underestimated it.

## Riddler Classic for 23 March 2018

Spoiler for last week’s fivethirtyeight.com Riddler Classic:

From Joseph Converse, a puzzle of digital manipulation:

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)

# One way

Write the number (call it $m$) as $10y+x$, where $x<10$; for instance, for 1,234, $y=123$ and $x=4$. Let $n$ be the number of digits in $y$; then the number resulting from moving the last digit to the front is $10^nx+y$. We want $2(10y+x)=10^nx+y$.

Solving, we get $y = (10^n-2)x/19$. Now, 19 is prime and $x<10$ so isn’t a multiple of 19, and therefore $(10^n-2)$ must be, that is, $10^n\mod 19 = 2$.

Going ahead and doing the long division ― that is, dividing 100, 1000, 10000… by 19 until a remainder of 2 is found ― we get $n=17$; $(10^{17}-2)/19 = 5263157894736842$. That has 16 digits, so $x=1$ won’t work; $x=2$ will give us a 17-digit $y=10526315789473684$, though. So the smallest number that works is $m = 105263157894736842 = 210526315789473684/2$.

# Another way

We require $2m$ to have the same number of digits as $m$, and that means the first digit of $2m$ can’t be 1. So let’s try making it 2. Then that’s also the last digit of $m$.

Now, the last digit of $2m$ is 4, which is also the second to last digit of $m$. And then the second to last digit of $2m$ is 8, which must be the third to last digit of $m$. Then the third to last digit of $2m$ is 6, with a carry. That means the fourth to last digit of $m$ is 6 and the fourth to last digit of $2m$ is 3, with a carry.

And so on, until we reach a place where the digit of $m$ is 1 and $2m$ is 2 without a carry. Stop there. Follow that procedure and you get $n = 105263157894736842$ as before.

Except we don’t know that this is the smallest answer. We need to do the same with last digit of $m$ running from 3 to 9. In fact (and as you’d expect having seen the other method) this is the smallest.

I’m rather surprised the second way didn’t occur to me sooner; it seems a good deal more obvious in retrospect. Then again, had I done it first I think I might’ve looked at the size of the result and been unconfident I hadn’t overlooked something that might give a smaller answer. The first method confirms it and makes it more clear, I think, that this really is the minimum. It also provides the insight that the answer is not just a mysterious sequence of digits but is connected with the decimal representation of 1/19.

# Triple?

Instead of moving the digit to get multiplication by 2, what about by 3? Or by $k$ generally? Adapting either method, one finds moving the last digit of 1034482758620689655172413793 to the front gives triple that number. For quadrupling we get a much smaller answer: 102564 = 410256/4. For quintupling we encounter for the first time the necessity of checking all possible last digits, not just the minimum one: Using 5 for the last digit we find 102040816326530612244897959183673469387755, but with 7 we get 142857! This is related to the fact that if you try the first method, you need $y = (10^n-5)x/49$, and 49 is not prime, so when $x=7$ we need $10^n \mod 7 = 5$ rather than $10^n \mod 49 = 5$.

Here’s a table for $k$ = 1 through 9. I am glad the Riddler puzzle didn’t ask for 6 (by hand)… I did these with a spreadsheet.

 1 1 2 105263157894736842 3 1034482758620689655172413793 4 102564 5 142857 6 1016949152542372881355932203389830508474576271186440677966 7 1014492753623188405797 8 1012658227848 9 10112359550561797752808988764044943820224719

Another generalization of the original puzzle is to do it in base $b$ instead of base 10. There’s no solution in binary, as you can figure out by trying to adapt either method above, or just by noting that doubling a number in binary means appending a 0 to the right end, so you can’t double a number and get a number with the same number of binary digits (bits). In base 3, starting with final digit 2 for $m$, the final digit for $2m$ is 1 with a carry of 1; 1 for the next digit of $m$ gives 0 for the next digit of $2m$ with a carry; 0 for $m$ gives 1 for $2m$; 1 for $m$ gives 2 for $2m$ and we’re done: $1012_3 = 2101_3/2$. In decimal, that’s 32 and 64. (In higher bases we need to check last digits from 2 to $b-1$.) Alternatively, we want $y = (3^n-2)x/5$ and so require $3^n \mod 5 = 2$. $n = 3$ works and then $y = 5x$. So with $x = 2$, $y = 10 = 101_3$ and $m = 1012_3$.

In all bases from 3 through 10:

 3 1012 4 102 5 13 6 1031345242 7 103524563142 8 25 9 10467842 10 105263157894736842

And if this Python script is bug free, then

$\mathrm{10179b72334c73ad1496e2dbd2c4365203047e46699e76b293dd5c8b5986ca406090d8cd44}\\ \mathrm{ded7537cbba27b41da580c131c2ab89cebea70a88550783c5b119263956824ae8e5e1621aa_{15}}$

is the smallest base 15 number which is multiplied by (decimal) 10 when the last digit is moved to the front. At 148 digits, it’s the longest such number for all bases up to 16 and all factors up to (base-1).

## Bignums on the small screen

I just learned the Calculator app in Android Marshmallow does arbitrary precision arithmetic. I asked it for $S(20)=\sqrt{12345679012345679012345679012345679012341}$ and it gave me the right answer to more than 500 decimals.

## Schizophrenic thinking

Some years ago I wrote up something about schizophrenic numbers. I read about these numbers in one of Clifford Pickover’s books, but he didn’t really get into what made them work the way they do, so I figured it out on my own. I posted it to the web. Now I can’t find a copy in my files or on my computer, and even the Internet Archive fails me — it didn’t archive it.

So I reconstructed it, more or less. I think.

The schizophrenic numbers are defined as follows. To start with we define

$f(x) = \begin{cases} 0& \mbox{if } m=0\\10f(m-1)+m& \mbox{if } m>0\end{cases}\\=\sum\limits_{k=0}^{m} 10^{m-k}k$

The first several $f(m)$ are

$f(0)=0 \\ f(1)=1\\f(2)=12\\f(3)=123\\f(4)=1234\\f(5)=12345\\f(6)=123456\\f(7)=1234567\\f(8)=12345678\\f(9)=123456789\\f(10)=1234567900\\f(11)=12345679011$

and so on. Now the mth schizophrenic number is

$S(m)=\sqrt{f(2m+1)}$

Are any of the $f(2m+1)$ perfect squares (for $m>0)$? No, they aren’t, as will become evident below. Therefore $S(0)$ is the only rational in the set. The rest are irrational, so should be non-repeating decimals.

But let’s look at $S(20)=\sqrt{12345679012345679012345679012345679012341}$. Its value is

$S(20)=111111111111111111111.111111111111111111...$

Wat.

It can’t be a rational number, unless it’s an integer, and it’s not an integer. What’s going on? Let’s get some more significant figures.

$S(20)=111111111111111111111.11111111111111111109005...$

Oh, okay, that’s better. It’s not a repeating decimal after all…

$S(20)=111111111111111111111.1111111111111111110900555555\\5555555555555555555555555555555...$

Wat.

$S(20)=111111111111111111111.1111111111111111110900555555\\555555555555555555555555555555535605416...$

Um, okay?

$S(20)=111111111111111111111.1111111111111111110900555555\\555555555555555555555555555555535605416666666666666666666...$

Wat.

Seems not to be able to make up its mind whether to be rational or not. Hence schizophrenic. Here’s about 500 decimal places, broken up into “rational” and “irrational” pieces:

$S(20)=111111111111111111111.111111111111111111 \\ 0900\\5555555555555555555555555555555555555\\3560541\\666666666666666666666666666666666\\2886115347\\22222222222222222222222222222\\1326704128428819\\444444444444444444444444\\2068634941610546874\\999999999999999999999\\32467614881946461588541\\6666666666666666\\465564871268691522639973958\\333333333333\\2714065492129693624196136474609374\\999999\\804414573486517125197501992119683159722159\\214377070903714104597488983578152126715487\\497795899993976792215472407658894849931527\\56767644661366482...$

(I calculated that by hand. HA HA HA no actually I used a Python script, with the mpmath library.) The repeating pieces get shorter and shorter, the non-repeating pieces get longer and longer, and then (apparently) the repetition stops (aside from random repeats) and it finally starts behaving like we expect irrational numbers to do.

I mean, sure, we all know there exist an infinite number of irrationals that have arbitrarily large (but finite) numbers of repeating digits in them. But who’d expect behavior like this from the square root of an integer? What’s going on?

Well, observe that if $x = 0.0123456790123456790123...$ then

$10^9x = 12345679.0123456790123456790123...=12345679+x \\ \Rightarrow x=12345679/999999999=1/81$

So $f(m)$ is a little smaller than $10^{m+1}/81$. In particular you can see if you think about it, and you can prove inductively using the recurrence formula for $f(m)$, that

$f(m)=10^{m+1}/81-(10+9m)/81$

which means

$S(m)=\sqrt{10^{2m+2}/81-(19+18m)/81} \\ =\frac{10^{m+1}}{9}\sqrt{1-\frac{19+18m}{10^{2m+2}}}$

Now you can use the Taylor series expansion

$\sqrt{1-y} = 1-y/2-y^2/4-y^3/8-5y^4/128...$.

Here $y$ is $(19+18m)/10^{2m+2}$, which for large $m$ is a bunch of zeros after the decimal point, followed by a few digits. In the expansion the terms after the first are powers of $y$ multiplied by an integer and divided by powers of 2, which for higher powers are lots of zeros after the decimal point, followed by some digits. The infinite sum gets divided by 9 — which turns the first term into $0.11111...$ and each of the following terms into zeros after the decimal point, followed by some digits, followed by some digit repeating to infinity — and then multiplied by $10^{m+1},$ which just shifts the decimal point. Look at the first few terms for $S(5)$:

$111111.111111... \\ -0.0000060555555...\\-0.000000000000000165013888888...\\-0.0000000000000000000000000089932569444444...\\-0.0000000000000000000000000056207855902777777...$

For the first three terms, there are enough zeros in the subsequent term to preserve some of the repeating digits in the sum. The fifth term, though, scribbles over the repeating 4s in the fourth term, and so we only see three sets of repeating digits in $S(5)$:

$S(5)=111111.111105055555555390541666657673409...$

But for larger $m$, each term has more leading zeros due to the power of $10^{2m+2}$ in the denominator, and more terms contribute repeating digits before the scribble-over point is reached. (And you get more and more 1s before and after the decimal point; in other words, you get closer and closer to a power of 10 times 1/9, so no, none of the corresponding $f(m)$ are perfect squares.) I referred somewhat facetiously to “rational” and “irrational” pieces above, but it’s sort of true; the repeating digits are where you can see that there is a finite number of rational terms in the Taylor series contributing to the sum.


text:
# Closure operator

In mathematics, a closure operator on a set S is a function ${\displaystyle \operatorname {cl} :{\mathcal {P}}(S)\rightarrow {\mathcal {P}}(S)}$ from the power set of S to itself that satisfies the following conditions for all sets ${\displaystyle X,Y\subseteq S}$

 ${\displaystyle X\subseteq \operatorname {cl} (X)}$ (cl is extensive), ${\displaystyle X\subseteq Y\Rightarrow \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)}$ (cl is monotone), ${\displaystyle \operatorname {cl} (\operatorname {cl} (X))=\operatorname {cl} (X)}$ (cl is idempotent).

Closure operators are determined by their closed sets, i.e., by the sets of the form cl(X), since the closure cl(X) of a set X is the smallest closed set containing X. Such families of "closed sets" are sometimes called closure systems or "Moore families", in honor of E. H. Moore who studied closure operators in his 1910 Introduction to a form of general analysis, whereas the concept of the closure of a subset originated in the work of Frigyes Riesz in connection with topological spaces.[1] Though not formalized at the time, the idea of closure originated in the late 19th century with notable contributions by Ernst Schröder, Richard Dedekind and George Cantor.[2]

Closure operators are also called "hull operators", which prevents confusion with the "closure operators" studied in topology. A set together with a closure operator on it is sometimes called a closure space.

## Applications

Closure operators have many applications:

In topology, the closure operators are topological closure operators, which must satisfy

${\displaystyle \operatorname {cl} (X_{1}\cup \dots \cup X_{n})=\operatorname {cl} (X_{1})\cup \dots \cup \operatorname {cl} (X_{n})}$

for all ${\displaystyle n\in \mathbb {N} }$  (Note that for ${\displaystyle n=0}$  this gives ${\displaystyle \operatorname {cl} (\varnothing )=\varnothing }$ ).

In algebra and logic, many closure operators are finitary closure operators, i.e. they satisfy

${\displaystyle \operatorname {cl} (X)=\bigcup \left\{\operatorname {cl} (Y):Y\subseteq X{\text{ and }}Y{\text{ finite}}\right\}.}$

In the theory of partially ordered sets, which are important in theoretical computer science, closure operators have a more general definition that replaces ${\displaystyle \subseteq }$  with ${\displaystyle \leq }$ . (See § Closure operators on partially ordered sets.)

## Closure operators in topology

The topological closure of a subset X of a topological space consists of all points y of the space, such that every neighbourhood of y contains a point of X. The function that associates to every subset X its closure is a topological closure operator. Conversely, every topological closure operator on a set gives rise to a topological space whose closed sets are exactly the closed sets with respect to the closure operator.

## Closure operators in algebra

Finitary closure operators play a relatively prominent role in universal algebra, and in this context they are traditionally called algebraic closure operators. Every subset of an algebra generates a subalgebra: the smallest subalgebra containing the set. This gives rise to a finitary closure operator.

Perhaps the best known example for this is the function that associates to every subset of a given vector space its linear span. Similarly, the function that associates to every subset of a given group the subgroup generated by it, and similarly for fields and all other types of algebraic structures.

The linear span in a vector space and the similar algebraic closure in a field both satisfy the exchange property: If x is in the closure of the union of A and {y} but not in the closure of A, then y is in the closure of the union of A and {x}. A finitary closure operator with this property is called a matroid. The dimension of a vector space, or the transcendence degree of a field (over its prime field) is exactly the rank of the corresponding matroid.

The function that maps every subset of a given field to its algebraic closure is also a finitary closure operator, and in general it is different from the operator mentioned before. Finitary closure operators that generalize these two operators are studied in model theory as dcl (for definable closure) and acl (for algebraic closure).

The convex hull in n-dimensional Euclidean space is another example of a finitary closure operator. It satisfies the anti-exchange property: If x is in the closure of the union of {y} and A, but not in the union of {y} and closure of A, then y is not in the closure of the union of {x} and A. Finitary closure operators with this property give rise to antimatroids.

As another example of a closure operator used in algebra, if some algebra has universe A and X is a set of pairs of A, then the operator assigning to X the smallest congruence containing X is a finitary closure operator on A x A.[3]

## Closure operators in logic

Suppose you have some logical formalism that contains certain rules allowing you to derive new formulas from given ones. Consider the set F of all possible formulas, and let P be the power set of F, ordered by ⊆. For a set X of formulas, let cl(X) be the set of all formulas that can be derived from X. Then cl is a closure operator on P. More precisely, we can obtain cl as follows. Call "continuous" an operator J such that, for every directed class T,

J(lim T)= lim J(T).

This continuity condition is on the basis of a fixed point theorem for J. Consider the one-step operator J of a monotone logic. This is the operator associating any set X of formulas with the set J(X) of formulas that are either logical axioms or are obtained by an inference rule from formulas in X or are in X. Then such an operator is continuous and we can define cl(X) as the least fixed point for J greater or equal to X. In accordance with such a point of view, Tarski, Brown, Suszko and other authors proposed a general approach to logic based on closure operator theory. Also, such an idea is proposed in programming logic (see Lloyd 1987) and in fuzzy logic (see Gerla 2000).

### Consequence operators

Around 1930, Alfred Tarski developed an abstract theory of logical deductions that models some properties of logical calculi. Mathematically, what he described is just a finitary closure operator on a set (the set of sentences). In abstract algebraic logic, finitary closure operators are still studied under the name consequence operator, which was coined by Tarski. The set S represents a set of sentences, a subset T of S a theory, and cl(T) is the set of all sentences that follow from the theory. Nowadays the term can refer to closure operators that need not be finitary; finitary closure operators are then sometimes called finite consequence operators.

## Closed and pseudo-closed sets

The closed sets with respect to a closure operator on S form a subset C of the power set P(S). Any intersection of sets in C is again in C. In other words, C is a complete meet-subsemilattice of P(S). Conversely, if CP(S) is closed under arbitrary intersections, then the function that associates to every subset X of S the smallest set YC such that XY is a closure operator.

There is a simple and fast algorithm for generating all closed sets of a given closure operator.[4]

A closure operator on a set is topological if and only if the set of closed sets is closed under finite unions, i.e., C is a meet-complete sublattice of P(S). Even for non-topological closure operators, C can be seen as having the structure of a lattice. (The join of two sets X,YP(S) being cl(X ${\displaystyle \cup }$  Y).) But then C is not a sublattice of the lattice P(S).

Given a finitary closure operator on a set, the closures of finite sets are exactly the compact elements of the set C of closed sets. It follows that C is an algebraic poset. Since C is also a lattice, it is often referred to as an algebraic lattice in this context. Conversely, if C is an algebraic poset, then the closure operator is finitary.

Each closure operator on a finite set S is uniquely determined by its images of its pseudo-closed sets.[5] These are recursively defined: A set is pseudo-closed if it is not closed and contains the closure of each of its pseudo-closed proper subsets. Formally: P ⊆ S is pseudo-closed if and only if

• P ≠ cl(P) and
• if Q ⊂ P is pseudo-closed, then cl(Q) ⊆ P.

## Closure operators on partially ordered sets

A partially ordered set (poset) is a set together with a partial order ≤, i.e. a binary relation that is reflexive (aa), transitive (abc implies ac) and antisymmetric (aba implies a = b). Every power set P(S) together with inclusion ⊆ is a partially ordered set.

A function cl: PP from a partial order P to itself is called a closure operator if it satisfies the following axioms for all elements x, y in P.

 x ≤ cl(x) (cl is extensive) x ≤ y implies cl(x) ≤ cl(y) (cl is increasing) cl(cl(x)) = cl(x) (cl is idempotent)

More succinct alternatives are available: the definition above is equivalent to the single axiom

x ≤ cl(y) if and only if cl(x) ≤ cl(y)

for all x, y in P.

Using the pointwise order on functions between posets, one may alternatively write the extensiveness property as idP ≤ cl, where id is the identity function. A self-map k that is increasing and idempotent, but satisfies the dual of the extensiveness property, i.e. k ≤ idP is called a kernel operator,[6] interior operator,[7] or dual closure.[8] As examples, if A is a subset of a set B, then the self-map on the powerset of B given by μA(X) = AX is a closure operator, whereas λA(X) = AX is a kernel operator. The ceiling function from the real numbers to the real numbers, which assigns to every real x the smallest integer not smaller than x, is another example of a closure operator.

A fixpoint of the function cl, i.e. an element c of P that satisfies cl(c) = c, is called a closed element. A closure operator on a partially ordered set is determined by its closed elements. If c is a closed element, then xc and cl(x) ≤ c are equivalent conditions.

Every Galois connection (or residuated mapping) gives rise to a closure operator (as is explained in that article). In fact, every closure operator arises in this way from a suitable Galois connection.[9] The Galois connection is not uniquely determined by the closure operator. One Galois connection that gives rise to the closure operator cl can be described as follows: if A is the set of closed elements with respect to cl, then cl: PA is the lower adjoint of a Galois connection between P and A, with the upper adjoint being the embedding of A into P. Furthermore, every lower adjoint of an embedding of some subset into P is a closure operator. "Closure operators are lower adjoints of embeddings." Note however that not every embedding has a lower adjoint.

Any partially ordered set P can be viewed as a category, with a single morphism from x to y if and only if xy. The closure operators on the partially ordered set P are then nothing but the monads on the category P. Equivalently, a closure operator can be viewed as an endofunctor on the category of partially ordered sets that has the additional idempotent and extensive properties.

If P is a complete lattice, then a subset A of P is the set of closed elements for some closure operator on P if and only if A is a Moore family on P, i.e. the largest element of P is in A, and the infimum (meet) of any non-empty subset of A is again in A. Any such set A is itself a complete lattice with the order inherited from P (but the supremum (join) operation might differ from that of P). When P is the powerset Boolean algebra of a set X, then a Moore family on P is called a closure system on X.

The closure operators on P form themselves a complete lattice; the order on closure operators is defined by cl1 ≤ cl2 iff cl1(x) ≤ cl2(x) for all x in P.

## Notes

1. ^ Blyth p.11
2. ^ Marcel Erné, Closure, in Frédéric Mynard, Elliott Pearl (Editors), Beyond Topology, Contemporary mathematics vol. 486, American Mathematical Society, 2009.
3. ^ Clifford Bergman, Universal Algebra, 2012, Section 2.4.
4. ^ Ganter, Algorithm 1
5. ^ Ganter, Section 3.2
6. ^ Giertz, p. 26
7. ^ Erné, p. 2, uses closure (resp. interior) operation
8. ^ Blyth, p. 10
9. ^ Blyth, p. 10

## References

• Garrett Birkhoff. 1967 (1940). Lattice Theory, 3rd ed. American Mathematical Society.
• Burris, Stanley N., and H.P. Sankappanavar (1981) A Course in Universal Algebra Springer-Verlag. ISBN 3-540-90578-2 Free online edition.
• Brown, D.J. and Suszko, R. (1973) "Abstract Logics," Dissertationes Mathematicae 102- 9-42.
• Castellini, G. (2003) Categorical closure operators. Boston MA: Birkhaeuser.
• Edelman, Paul H. (1980) Meet-distributive lattices and the anti-exchange closure, Algebra Universalis 10: 290-299.
• Ganter, Bernhard and Obiedkov, Sergei (2016) Conceptual Exploration. Springer, ISBN 978-3-662-49290-1.
• Gerla, G. (2000) Fuzzy Logic: Mathematical Tools for Approximate Reasoning. Kluwer Academic Publishers.
• Lloyd, J.W. (1987) Foundations of Logic Programming. Springer-Verlag.
• Tarski, Alfred (1983) "Fundamental concepts of the methodology of deductive sciences" in Logic, Semantics, Metamathematics. Hackett (1956 ed., Oxford University Press).
• Alfred Tarski (1956) Logic, semantics and metamathematics. Oxford University Press.
• Ward, Morgan (1942) "The closure operators of a lattice," Annals of Mathematics 43: 191-96.
• G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: Continuous Lattices and Domains, Cambridge University Press, 2003
• T.S. Blyth, Lattices and Ordered Algebraic Structures, Springer, 2005, ISBN 1-85233-905-5.
• M. Erné, J. Koslowski, A. Melton, G. E. Strecker, A primer on Galois connections, in: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, Vol. 704, 1993, pp. 103–125. Available online in various file formats: PS.GZ PS