text:
Corner detection

Corner detection

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D modelling and object recognition. Corner detection overlaps with the topic of interest point detection.

Formalization

A corner can be defined as the intersection of two edges. A corner can also be defined as a point for which there are two dominant and different edge directions in a local neighborhood of the point.

An interest point is a point in an image which has a well-defined position and can be robustly detected. This means that an interest point can be a corner but it can also be, for example, an isolated point of local intensity maximum or minimum, line endings, or a point on a curve where the curvature is locally maximal.

In practice, most so-called corner detection methods detect interest points in general, rather than corners in particular.[citation needed] As a consequence, if only corners are to be detected it is necessary to do a local analysis of detected interest points to determine which of these are real corners. Examples of edge detection that can be used with post-processing to detect corners are the Kirsch-Operator and the Frei-Chen masking set.[1]

"Corner", "interest point" and "feature" are used interchangeably in literature, confusing the issue. Specifically, there are several blob detectors that can be referred to as "interest point operators", but which are sometimes erroneously referred to as "corner detectors". Moreover, there exists a notion of ridge detection to capture the presence of elongated objects.

Corner detectors are not usually very robust and often require expert supervision or large redundancies introduced to prevent the effect of individual errors from dominating the recognition task.

One determination of the quality of a corner detector is its ability to detect the same corner in multiple similar images, under conditions of different lighting, translation, rotation and other transforms.

A simple approach to corner detection in images is using correlation, but this gets very computationally expensive and suboptimal. An alternative approach used frequently is based on a method proposed by Harris and Stephens (below), which in turn is an improvement of a method by Moravec.

The Moravec corner detection algorithm

This is one of the earliest corner detection algorithms and defines a corner to be a point with low self-similarity.[2] The algorithm tests each pixel in the image to see if a corner is present, by considering how similar a patch centered on the pixel is to nearby, largely overlapping patches. The similarity is measured by taking the sum of squared differences (SSD) between the two patches. A lower number indicates more similarity.

If the pixel is in a region of uniform intensity, then the nearby patches will look similar. If the pixel is on an edge, then nearby patches in a direction perpendicular to the edge will look quite different, but nearby patches in a direction parallel to the edge will result only in a small change. If the pixel is on a feature with variation in all directions, then none of the nearby patches will look similar.

The corner strength is defined as the smallest SSD between the patch and its neighbors (horizontal, vertical and on the two diagonals). If this number is locally maximal, then a feature of interest is present.

As pointed out by Moravec, one of the main problems with this operator is that it is not isotropic: if an edge is present that is not in the direction of the neighbours, then it will not be detected as an interest point.

The Harris & Stephens / Plessey / Shi-Tomasi corner detection algorithm

Harris and Stephens[3] improved upon Moravec's corner detector by considering the differential of the corner score with respect to direction directly, instead of using shifted patches. (This corner score is often referred to as autocorrelation, since the term is used in the paper in which this detector is described. However, the mathematics in the paper clearly indicate that the sum of squared differences is used.)

Without loss of generality, we will assume a grayscale 2-dimensional image is used. Let this image be given by I. Consider taking an image patch over the area (u,v) and shifting it by (x,y). The weighted sum of squared differences (SSD) between these two patches, denoted S, is given by:

$S(x,y) = \sum_u \sum_v w(u,v) \, \left( I(u+x,v+y) - I(u,v)\right)^2$

I(u + x,v + y) can be approximated by a Taylor expansion. Let Ix and Iy be the partial derivatives of I, such that

$I(u+x,v+y) \approx I(u,v) + I_x(u,v)x+I_y(u,v)y$

This produces the approximation

$S(x,y) \approx \sum_u \sum_v w(u,v) \, \left( I_x(u,v)x + I_y(u,v)y \right)^2,$

which can be written in matrix form:

$S(x,y) \approx \begin{pmatrix} x & y \end{pmatrix} A \begin{pmatrix} x \\ y \end{pmatrix},$

where A is the structure tensor,

$A = \sum_u \sum_v w(u,v) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} = \begin{bmatrix} \langle I_x^2 \rangle & \langle I_x I_y \rangle\\ \langle I_x I_y \rangle & \langle I_y^2 \rangle \end{bmatrix}$

This matrix is a Harris matrix, and angle brackets denote averaging (i.e. summation over (u,v)). If a circular window (or circularly weighted window, such as a Gaussian) is used, then the response will be isotropic.

A corner (or in general an interest point) is characterized by a large variation of S in all directions of the vector $\begin{pmatrix} x & y \end{pmatrix}$. By analyzing the eigenvalues of A, this characterization can be expressed in the following way: A should have two "large" eigenvalues for an interest point. Based on the magnitudes of the eigenvalues, the following inferences can be made based on this argument:

1. If $\lambda_1 \approx 0$ and $\lambda_2 \approx 0$ then this pixel (x,y) has no features of interest.
2. If $\lambda_1 \approx 0$ and λ2 has some large positive value, then an edge is found.
3. If λ1 and λ2 have large positive values, then a corner is found.

Harris and Stephens note that exact computation of the eigenvalues is computationally expensive, since it requires the computation of a square root, and instead suggest the following function Mc, where κ is a tunable sensitivity parameter:

$M_c = \lambda_1 \lambda_2 - \kappa \, (\lambda_1 + \lambda_2)^2 = \operatorname{det}(A) - \kappa \, \operatorname{trace}^2(A)$

Therefore, the algorithm does not have to actually compute the eigenvalue decomposition of the matrix A and instead it is sufficient to evaluate the determinant and trace of A to find corners, or rather interest points in general.

The Shi-Tomasi[4] corner detector directly computes min12) because under certain assumptions, the corners are more stable for tracking. Note that this method is also sometimes referred to as the Kanade-Tomasi corner detector.

The value of κ has to be determined empirically, and in the literature values in the range 0.04 - 0.15 have been reported as feasible.

The covariance matrix for the corner position is A − 1, i.e.

$\frac{1}{\langle I_x^2 \rangle \langle I_y^2 \rangle - \langle I_x I_y \rangle^2} \begin{bmatrix} \langle I_y^2 \rangle & -\langle I_x I_y \rangle\\ -\langle I_x I_y \rangle & \langle I_x^2 \rangle \end{bmatrix}.$

The multi-scale Harris operator

The computation of the second moment matrix (sometimes also referred to as the structure tensor) A in the Harris operator, requires the computation of image derivatives Ix,Iy in the image domain as well as the summation of non-linear combinations of these derivatives over local neighbourhoods. Since the computation of derivatives usually involves a stage of scale-space smoothing, an operational definition of the Harris operator requires two scale parameters: (i) a local scale for smoothing prior to the computation of image derivatives, and (ii) an integration scale for accumulating the non-linear operations on derivative operators into an integrated image descriptor.

With I denoting the original image intensity, let L denote the scale-space representation of I obtained by convolution with a Gaussian kernel

$g(x, y, t) = \frac {1}{2{\pi} t}e^{-(x^2+y^2)/2t}$

with local scale parameter t:

$L(x, y, t)\ = g(x, y, t) * I(x, y)$

and let $L_x = \partial_x L$ and $L_y = \partial_y L$ denote the partial derivatives of L. Moreover, introduce a Gaussian window function g(x,y,s) with integration scale parameter s. Then, the multi-scale second-moment matrix [5][6] can be defined as

$\mu(x, y; t, s) = \int_{\xi = -\infty}^{\infty} \int_{\eta = -\infty}^{\infty} \begin{bmatrix} L_x^2(x-\xi, y-\eta; t) & L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) \\ L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) & L_y^2(x-\xi, y-\eta; t) \end{bmatrix} g(\xi, \eta; s) \, d\xi \, d\eta.$

Then, we can compute eigenvalues of μ in a similar way as the eigenvalues of A and define the multi-scale Harris corner measure as

$M_c(x, y; t, s) = \operatorname{det}(\mu(x, y; t, s)) - \kappa \, \operatorname{trace}^2(\mu(x, y; t, s))$.

Concerning the choice of the local scale parameter t and the integration scale parameter s, these scale parameters are usually coupled by a relative integration scale parameter γ such that s = γ2t, where γ is usually chosen in the interval [1,2]. Thus, we can compute the multi-scale Harris corner measure Mc(x,y;t2t) at any scale t in scale-space to obtain a multi-scale corner detector, which responds to corner structures of varying sizes in the image domain.

In practice, this multi-scale corner detector is often complemented by a scale selection step, where the scale-normalized Laplacian operator[5][7]

$\nabla^2_{norm} L(x, y; t)\ = t \nabla^2 L(x, y, t) = t (L_{xx}(x, y, t) + L_{yy}(x, y, t))$

is computed at every scale in scale-space and scale adapted corner points with automatic scale selection (the "Harris-Laplace operator") are computed from the points that are simultaneously[8]:

• spatial maxima of the multi-scale corner measure Mc(x,y;t2t)
$(\hat{x}, \hat{y}; t) = \operatorname{argmaxlocal}_{(x, y)} M_c(x, y; t, \gamma^2 t)$
• local maxima or minima over scales of the scale-normalized Laplacian operator $\nabla^2_{norm}(x, y, t)$
$\hat{t} = \operatorname{argmaxminlocal}_{t} \nabla^2_{norm}L(\hat{x}, \hat{y}; t)$.

The level curve curvature approach

An earlier approach to corner detection is to detect points where the curvature of level curves and the gradient magnitude are simultaneously high.[9][10] A differential way to detect such points is by computing the rescaled level curve curvature (the product of the level curve curvature and the gradient magnitude raised to the power of three)

$\tilde{\kappa}(x, y;t) = L_x^2 L_{yy} + L_y^2 L_{xx} - 2 L_x L_y L_{xy}$

and to detect positive maxima and negative minima of this differential expression at some scale t in the scale-space representation L of the original image.[7] A main problem with this approach, however, is that it may be sensitive to noise and to the choice of the scale level. A better method is to compute the γ-normalized rescaled level curve curvature

$\tilde{\kappa_{norm}}(x, y;t) = t^{2 \gamma} (L_x^2 L_{yy} + L_y^2 L_{xx} - 2 L_x L_y L_{xy})$

with γ = 7 / 8 and to detect signed scale-space extrema of this expression, that are points and scales that are positive maxima and negative minima with respect to both space and scale

$(\hat{x}, \hat{y}; \hat{t}) = \operatorname{argminmaxlocal}_{(x, y; t)} \tilde{\kappa}_{norm}(x, y; t)$

in combination with a complementary localization step to handle the increase in localization error at coarser scales.[5][7] In this way, larger scale values will be associated with rounded corners of large spatial extent while smaller scale values will be associated with sharp corners with small spatial extent. This approach is the first corner detector with automatic scale selection (prior to the "Harris-Laplace operator" above) and has been used[11] for tracking corners under large scale variations in the image domain.

LoG, DoG, and DoH feature detection

LoG[7][8] is an acronym standing for Laplacian of Gaussian, DoG[12] is an acronym standing for Difference of Gaussians (DoG is an approximation of LoG), and DoH is an acronym standing for Determinant of the Hessian.[7]

These detectors are more completely described in blob detection, however the LoG and DoG blobs do not necessarily make highly selective features, since these operators may also respond to edges. To improve the corner detection ability of the DoG detector, the feature detector used in the SIFT[12] system uses an additional post-processing stage, where the eigenvalues of the Hessian of the image at the detection scale are examined in a similar way as in the Harris operator. If the ratio of the eigenvalues is too high, then the local image is regarded as too edge-like, so the feature is rejected. The DoH operator on the other hand only responds when there are significant grey-level variations in two directions.[6][7]

Affine-adapted interest point operators

The interest points obtained from the multi-scale Harris operator with automatic scale selection are invariant to translations, rotations and uniform rescalings in the spatial domain. The images that constitute the input to a computer vision system are, however, also subject to perspective distortions. To obtain an interest point operator that is more robust to perspective transformations, a natural approach is to devise a feature detector that is invariant to affine transformations. In practice, affine invariant interest points can be obtained by applying affine shape adaptation where the shape of the smoothing kernel is iteratively warped to match the local image structure around the interest point or equivalently a local image patch is iteratively warped while the shape of the smoothing kernel remains rotationally symmetric.[5][6][8] Hence, besides the commonly used multi-scale Harris operator, affine shape adaptation can be applied to other corner detectors as listed in this article as well as to differential blob detectors such as the Laplacian/Difference of Gaussian operator, the determinant of the Hessian [6] and the Hessian-Laplace operator.

The Wang and Brady corner detection algorithm

The Wang and Brady[13] detector considers the image to be a surface, and looks for places where there is large curvature along an image edge. In other words, the algorithm looks for places where the edge changes direction rapidly. The corner score, C, is given by:

$C = \nabla^2I - c|\nabla I|^2,$

where c determines how edge-phobic the detector is. The authors also note that smoothing (Gaussian is suggested) is required to reduce noise. In this case, the first term of C becomes the Laplacian (single-scale) blob detector.

Smoothing also causes displacement of corners, so the authors derive an expression for the displacement of a 90 degree corner, and apply this as a correction factor to the detected corners.

The SUSAN corner detector

SUSAN[14] is an acronym standing for Smallest Univalue Segment Assimilating Nucleus.

For feature detection, SUSAN places a circular mask over the pixel to be tested (the nucleus). The region of the mask is M, and a pixel in this mask is represented by $\vec{m} \in M$. The nucleus is at $\vec{m}_0$. Every pixel is compared to the nucleus using the comparison function:

$c(\vec{m}) = e^{\left(-\frac{(I(\vec{m}) - I(\vec{m}_0))^6}{t}\right)}$

where t determines the radius, and the power of the exponent has been determined empirically. This function has the appearance of a smoothed top-hat or rectangular function. The area of the SUSAN is given by:

$n(M) = \sum_{\vec{m}\in M} c(\vec{m})$

If c is the rectangular function, then n is the number of pixels in the mask which are within t of the nucleus. The response of the SUSAN operator is given by:

$R(M) = \begin{cases} g - n(M) & \mbox{if}\ n(M) < g\\ 0 & \mbox{otherwise,} \end{cases}$

where g is named the `geometric threshold'. In other words the SUSAN operator only has a positive score if the area is small enough. The smallest SUSAN locally can be found using non-maximal suppression, and this is the complete SUSAN operator.

The value t determines how similar points have to be to the nucleus before they are considered to be part of the univalue segment. The value of g determines the minimum size of the univalue segment. If g is large enough, then this becomes an edge detector.

For corner detection, two further steps are used. Firstly, the centroid of the SUSAN is found. A proper corner will have the centroid far from the nucleus. The second step insists that all points on the line from the nucleus through the centroid out to the edge of the mask are in the SUSAN.

This technique is patented with UK patent 2272285.

The Trajkovic and Hedley corner detector

In a manner similar to SUSAN, this detector[15] directly tests whether a patch under a pixel is self-similar by examining nearby pixels. $\vec{c}$ is the pixel to be considered, and $\vec{p} \in P$ is point on a circle P centered around $\vec{c}$. The point $\vec{p'}$ is the point opposite to $\vec{p}$ along the diameter.

The response function is defined as:

$r(\vec{c}) = \min_{\vec{p} \in P}\quad (I(\vec{p}) - I(\vec{c}))^2 + (I(\vec{p'}) - I(\vec{c})) ^2$

This will be large when there is no direction in which the centre pixel is similar to two nearby pixels along a diameter. P is a discretised circle (a Bresenham circle), so interpolation is used for intermediate diameters to give a more isotropic response. Since any computation gives an upper bound on the min , the horizontal and vertical directions are checked first to see if it is worth proceeding with the complete computation of c.

AST based feature detectors

AST is an acronym standing for Accelerated Segment Test. This test is a relaxed version of the SUSAN corner criterion. Instead of evaluating the circular disc only the pixels in a Bresenham circle of radius r around the candidate point are considered. If n contiguous pixels are all brighter than the nucleus by at least t or all darker than the nucleus by t, then the pixel under the nucleus is considered to be a feature. This test is reported to produce very stable features.[16] The choice of the order in which the pixels are tested is a so called Twenty Questions problem. Building short decision trees for this problem results in the most computationally efficient feature detectors available.

The first corner detection algorithm based on the AST is FAST (Features from Accelerated Segment Test).[16] Although r can in principle take any value, FAST uses only a value of 3 (corresponding to a circle of 16 pixels circumference), and tests show that the best results are achieved with n being 9. This value of n is the lowest one at which edges are not detected. The order in which pixels are tested is determined by the ID3 algorithm from a training set of images. Confusingly, the name of the detector is somewhat similar to the name of the paper describing Trajkovic and Hedley's detector.

Automatic synthesis of detectors

Trujillo and Olague[17] introduced a method by which genetic programming is used to automatically synthesize image operators that can detect interest points. The terminal and function sets contain primitive operations that are common in many previously proposed man-made designs. Fitness measures the stability of each operator through the repeatability rate, and promotes a uniform dispersion of detected points across the image plane. The performance of the evolved operators has been confirmed experimentally using training and testing sequences of progressively transformed images. Hence, the proposed GP algorithm is considered to be human-competitive for the problem of interest point detection.

Bibliography

1. ^ Shapiro, Linda and George C. Stockman (2001). Computer Vision, p. 257. Prentice Books, Upper Saddle River. ISBN 0130307963.
2. ^ H. Moravec (1980). "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover". Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute.
3. ^ C. Harris and M. Stephens (1988). "A combined corner and edge detector". Proceedings of the 4th Alvey Vision Conference. pp. 147–151.
4. ^ J. Shi and C. Tomasi (June 1994). "Good Features to Track,". 9th IEEE Conference on Computer Vision and Pattern Recognition. Springer.

5. ^ a b c d T. Lindeberg (1994). Scale-Space Theory in Computer Vision. Springer. ISBN 0-7923-9418-6.
6. ^ a b c d T. Lindeberg (2008/2009). Scale-Space. "Wiley Encyclopedia of Computer Science and Engineering". Encyclopedia of Computer Science and Engineering (Benjamin Wah, ed), John Wiley and Sons IV: 2495–2504. doi:10.1002/9780470050118.ecse609. ISBN 047005011X.
7. ^ a b c d e f Tony Lindeberg (1998). "Feature detection with automatic scale selection". International Journal of Computer Vision 30 (2): p. 77–116.
8. ^ a b c K. Mikolajczyk, K. and C. Schmid (2004). "Scale and affine invariant interest point detectors" (PDF). International Journal of Computer Vision 60 (1): pp 63–86. doi:10.1023/B:VISI.0000027790.02288.f2.
9. ^ L. Kitchen and A. Rosenfeld (1982). "Gray-level corner detection"". Pattern Recognition Letters 1 (2).
10. ^ J. J. Koenderink and W. Richards (1988). "Two-dimensional curvature operators". Journal of the Optical Society of America: Series A 5 (number 7): pp. 1136--1141.
11. ^ L. Bretzner and T. Lindeberg (1998.). "Feature tracking with automatic selection of spatial scales". Computer Vision and Image Understanding 71,: pp. 385--392.
12. ^ a b D. Lowe (2004). "Distinctive Image Features from Scale-Invariant Keypoints". International Journal of Computer Vision 60 (2): 91. doi:10.1023/B:VISI.0000029664.99615.94.
13. ^
14. ^ S. M. Smith and J. M. Brady (May 1997). "SUSAN - a new approach to low level image processing". International Journal of Computer Vision 23 (1): 45–78. doi:10.1023/A:1007963824710.
S. M. Smith and J. M. Brady (January 1997), "Method for digitally processing images to determine the position of edges and/or corners therein for guidance of unmanned vehicle". UK Patent 2272285, Proprietor: Secretary of State for Defence, UK.
15. ^ M. Trajkovic and M. Hedley (1998). "Fast corner detection". Image and Vision Computing 16 (2): 75–87. doi:10.1016/S0262-8856(97)00056-5.
16. ^ a b E. Rosten and T. Drummond (May 2006). "Machine learning for high-speed corner detection,". European Conference on Computer Vision.
17. ^ Leonardo Trujillo and Gustavo Olague (2008). "Automated design of image operators that detect interest points". Evolutionary Computation 16 (4): 483–507. doi:10.1162/evco.2008.16.4.483. PMID 19053496.

Reference implementations

This section provides external links to reference implementations of some of the detectors described above. These reference implementations are provided by the authors of the paper in which the detector is first described. These may contain details not present or explicit in the papers describing the features.

• DoG detection (as part of the SIFT system), Windows and x86 Linux executables
• Harris-Laplace, static Linux executables. Also contains DoG and LoG detectors and affine adaptation for all detectors included.
• FAST detector, C, C++, MATLAB source code and executables for various operating systems and architectures.
• lip-vireo,[LoG, DoG, Harris-Laplacian, Hessian and Hessian-Laplacian],[SIFT, flip invariant SIFT, PCA-SIFT, PSIFT, Steerable Filters, SPIN][Linux, Windows and SunOS] executables.
• FAST Detector for the iPhone, Adaptation of Edward Rosten's implementation to the iPhone. Achieves real time results.

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Corner (disambiguation) — A corner is the place where two lines of different dimensions meet at an angle. Corner may also refer to: Contents 1 People 2 Fictional characters 3 Places 4 The arts …   Wikipedia

• Feature detection (computer vision) — In computer vision and image processing the concept of feature detection refers to methods that aim at computing abstractions of image information and making local decisions at every image point whether there is an image feature of a given type… …   Wikipedia

• Blob detection — Feature detection Output of a typical corner detection algorithm …   Wikipedia

• Interest point detection — is a recent terminology in computer vision that refers to the detection of interest points for subsequent processing. An interest point is a point in the image which in general can be characterized as follows:* it has a clear, preferably… …   Wikipedia

• HMCS Corner Brook (SSK 878) — is a long range hunter killer (SSK) submarine of the Canadian Navy, the third ship of the Victoria class. She is named after the city of Corner Brook, Newfoundland. She is the former Upholder class HMS Ursula (S42) purchased from the Royal Navy.… …   Wikipedia

• Convective storm detection — is the meteorological observation of deep, moist convection (DMC) and consists of detection, monitoring, and short term prediction. This term includes the minority of storms which do not produce lightning and thunder. Convective storms can… …   Wikipedia

• HMCS Corner Brook (SSK 878) — Dienstzeit Typ: Flotten U Boot …   Deutsch Wikipedia

• Harris Corner Detector — Bild mit markanten Punkten (rote Kreuze). Benutzt wurde der Harris Corner Detector Mit Interest Operatoren werden auf dem Bereich der Bildverarbeitung Algorithmen bezeichnet, die markante Stellen in Bildern extrahieren und gleichzeitig eine oder… …   Deutsch Wikipedia

• Harris affine region detector — In the fields of computer vision and image analysis, the Harris affine region detector belongs to the category of feature detection. Feature detection is a preprocessing step of several algorithms that rely on identifying characteristic points or …   Wikipedia

• Scale-invariant feature transform — Feature detection Output of a typical corner detection algorithm …   Wikipedia


text:
# GSEB Solutions Class 11 Physics Chapter 13 Kinetic Theory

Gujarat Board GSEB Textbook Solutions Class 11 Physics Chapter 13 Kinetic Theory Textbook Questions and Answers.

## Gujarat Board Textbook Solutions Class 11 Physics Chapter 13 Kinetic Theory

### GSEB Class 11 Physics Kinetic Theory Text Book Questions and Answers

Question 1.
Estimate the fraction of molecular volume to the actual volume occupies by oxygen gas at STP. Take the radius of an oxygen molecule to be roughly 3Å?
A gram, mole of oxygen gas occupies a volume at S.T.P.,
V = 22400 × 10-6m3 (∵ 1 ml = 1 cm3)
r = Radius of an oxygen molecule = 3Å = 3 × 10-10 m
Molecular volume of one mole of oxygen, V’
= Volume of one molecule of O2 × Avogadro’s number (N)
= $$\frac{4}{3}$$πr3 × N
or V’ = $$\frac{4}{3}$$π × (3 × 10-10)3 × 6.023 × 1023
∴ Fraction of molecular volume of the actual volume occupied by oxygen = Ratio of two volumes
= $$\frac{V}{V’}$$

= 4 × 10-4

Question 2.
Molar volume is the volume occupied by 1 mole of any (ideal) gas at standard temperature and pressure (STP : 1 atmospheric pressure, 0°C). Show that it is 22.4 litres.
Here, at STP conditions
P = 1 atm = 7.6 m of Hg column
= 0.76 × 13.6 × 103 × 9.8
= 1.013 × 105 Nm-2
T = 0°C = 273 K
R = 8.31 J mol-1 K-1
n = 1 mole, To prove V = 22.4 litre
∴ Using the gas equation,
PV = nRT, we get
V = $$\frac{nRT}{P}$$ = $$\frac{1 \times 8.31 \times 273}{1.013 \times 10^{5}}$$
= 22.4 × 10-3m3 = 22.4 litre.
Hence proved.

Question 3.
Figure below shows plot of PV/T versus P for 1.00 × 10-3 kg of oxygen gas at two different temperatures?

(a) What does the dotted plot signify?
(b) Which is true T1 > T2 or T1 > T2?
(c) What is the value of PV/T where the curves meet on the Y-axis?
(d) If we obtained similar plots for 1.00 × 10-3 kg of hydrogen, would we get the same value of PV/T at the point where the curves meet on the Y-axis? If not, what mass of hydrogen yields the same value of PV/T (for low pressure – high temperature region of the plot)? Molecular mass of H2 = 2.02 u, of O2 = 32.0 u, R = 8.31 J mol-1 K-1).
(a) The dotted plot corresponds to ‘ideal’ gas behaviour as it is parallel to P-axis and it tells that value of PV/T remains same (= nR) even when P is changed.

(b) The upper position of PV/T shows that its value is lesser for T1, thus T1 > T2. This is because the curve at T1 is more close to dotted plot than the curve at T2. Since the behaviour of a real gas approaches the perfect gas behaviour, as the temperature is increased.

(c) Where the curve meets PV/T axis, the ideal gas curve also meets the same as PV = nRT applicable at this point i.e. if the amount of gas under consideration is 1 mole, then the value of PV/T will be R(= 8.31 J mol-1k-1).
∴ The value of $$\frac{PV}{T}$$ = nR

To find n:
We know that 3.2 × 10-3 kg of O2 = 1 mole
∴ 1.00 × 10-3 kg of O2 = $$\frac{1}{32 \times 10^{-3}}$$ × 1 × 103
i.e. n = $$\frac{1}{32}$$
R = 8.32 JK-1 mol-1
∴ $$\frac{PV}{T}$$ = $$\frac{1}{32}$$ × 8.31 = 0.26 JK-1.

(d) No, the same value of PV/T will not be obtained for H2 as its value depends on mass and mass of H2 is lesser than O2.
Let m kg be the required mass of hydrogen which yields the same value of PV/T.
∴ n = $$\frac{\mathrm{m}}{2.02 \times 10^{3}}$$ ………………. (i)
for $$\frac{PV}{T}$$ = nR = 2.26 JK-1, n is given by
n = $$\frac{0.26}{R}$$ = $$\frac{0.26 \mathrm{JK}^{1}}{8.31 \mathrm{JK}^{-1} \mathrm{~mol}^{-1}}$$
= 0.0313 mol ……………………. (ii)
∴ From (i) and (ii), we get
m = 2.02 × 10-3 n
= 2.02 × 10-3 × 0.313
= 0.0632 × 10-3 kg
= 6.32 × 10-5 kg.

Question 4.
An oxygen cylinder of volume 30 litres has anlnitial gauge pressure of 15 atm and a temperature of 27°C. After some oxygen is withdrawn from the cylinder, the gauge pressure drops to 11 atm and its temperature drops to 17°C. Estimate the mass of oxygen taken out of the cylinder. (R = 8.31 JK-1 mol-1, molecular mass of O2 = 32 u.)
Here, initially in the oxygen cylinder,
V1 = 30 litres
= 30 × 10-3 m3
P1 = 15 atm = 15 × 1.013 × 105 Pa
T1 = 27+ 273
= 300 K
R = 8.31 JK-1 mol-1
If n1 be the moles of oxygen gas contained in the cylinder, then using the gas equation PV = nRT, we get
n = $$\frac{P_{1} V_{1}}{R T_{1}}$$ = $$\frac{15 \times 1.013 \times 10^{5}}{8.31 \times 300}$$
= 18.253
For oxygen, molecular weight,
M = 32 g = 32 × 10-3 kg
= 584.1 × 10-3 kg
Finally in the oxygen cylinder let n, moles of oxygen be left
Here, V2 = 30 × 10-3 m3
P2 = 11 atm= 11 × 1.013 × 105 Pa
T2 = 17+ 273
= 290 K

= 13. 847
∴ Final mass of oxygen gas in the cylinder,
m2 = 13.847 × 32 × 103
= 453.1 × 10-3 kg
∴ Mass of oxygen taken out of the cylinder
= m1 – m2
= (584.1 – 453.1) × 10-3 kg
= 141 × 103 kg
= 0.141 kg.

Question 5.
An air bubble of volume 1.0 cm3 rises from the bottom of a lake 40 m deep at a temperature of 12°C. To what volume does it grow when it reaches the surface, which is at a temperature 35°C?
When the air bubbles is at a depth of 40 m,
then V1 = 1.0 cm3
= 1.0 × 106 m3
T1 = 12°C = 12 + 273 = 285 K
P1 = 1 atm + 40 m depth of water
= 1 atm + h1ρg
= 1.013 × 105 + 40 × 103 × 9.8
= 493000 Pa = 4.93 × 105 Pa.
When the air bubble reaches at the surface of lake, then
V2 = ?
T2 = 35°C
= 35 + 273
= 308 K
P2 = 1 atm
= 1.013 × 105 Pa

= 5. 275 × 10-6m3
= 5.3 × 106m3.

Question 6.
Estimate the total number of air molecules (inclusive of oxygen, nitrogen, water vapour and other constituents) in a room of capacity 25.0 m3 at a temperature of 27°C and 1 atm pressure.
Here, V = 25.0 m3
T = 27°C = 27 + 273
= 300 K
k = 1.38 × 1023 JK-1
P = 1 atm
= 1.013 × 105 Pa
Now the gas equation, PV = nRT may be written as
P = $$\frac{nRT}{V}$$
= $$\frac{n}{V}$$(Nk)T (∵ $$\frac{R}{N}$$ = k)
= (nV) $$\frac{kT}{V}$$ = N $$\frac{kT}{V}$$
Where N’ = nN = total number of air molecules in the given gas
∴ N’ = $$\frac{PV}{kT}$$ = $$\frac{\left(1.013 \times 10^{5}\right) \times 25}{1.38 \times 10^{-23} \times 300}$$
= 6.10 × 1026.

Question 7.
Estimate the average thermal energy of helium atom of

1. room temperature (27°C),
2. the temperature on the surface of the Sun (6000 K),
3. the temperature of 10 million kelvin (the typical core temperature in the case of a star).

According to kinetic theory of gases, the average kinetic energy of the gas at a temperature T (i.e. average thermal energy) is given by
E = $$\frac{3}{2}$$ kT
Here k = 1.38 × 1023 JK-1.
Now
1. At T = 27°C = 273 + 27 = 300 K
E = $$\frac{3}{2}$$ × 1.38 × 10-23 × 300
= 621 × 1023 J
= 6.21 × 1023 J.

2. Here, T = 6000 K
∴ E = $$\frac{3}{2}$$ × 1.38 × 10-23 × 6000
= 1.24 × 1019 J

3. Here T = 10 × 106 K = 107 K
∴ E = $$\frac{3}{2}$$ × 1.38 × 10-23 × 107
= 2.07 × 1016J = 2.1 × 10-16 J.

Question 8.
Three vessels of equal capacity have gases at the same temperature and pressure. The first vessel contains neon (monoatomic gas) the secqnd contains chlorine (diatomic) and the third contains uranium hexafluoride (polyatomic). Do the vessels contain equal number of respective molecules? Is the root mean square speed of molecules the same in the three cases? If not, in which case is vrms the largest?
Yes. According to Avogadro’s hypothesis, the condition of temperature and pressure remain same, the equal volumes of all gases have equal number of molecules. So the number of molecules in the three vessels containing different gases must be same i.e. the three vessels contain equal no. of respective molecules.
No. r.m.s. speed of molecules is not same in three cases as explained below:
We know that the rms velocity of a gas is given by:
Vr.m.s = $$\sqrt{\frac{3 R T}{M}}$$ or Vr.m.s ∝ $$\frac{1}{\sqrt{\mathrm{M}}}$$ where M = Molecular mass and is different gases, therefore Vr.m.s of three gases will be different.
As Vr.m.s is inversely proportional to mass of molecules of the gas and since neon is the lightest of the three gases, therefore Vr.m.s for neon gas is largest.

Question 9.
At what temperature is the root mean square speed of an atom in an argon gas cylinder equal to the rms speed of a helium gas atom at – 20°C? (Atomic mass of Ar = 39.9 u of He = 4.0 u).
Let C1 and C2 be the r.m.s. speed of argon and helium gas atoms at temperature T1 and T2 respectively.
Here, M1 = 39.9 × 103 kg
M2 = 4.0 × 10-3 kg
T1 = ?
T2 = – 20 + 273
= 253 K
Now we know that r.m.s. speed is given by

or T = 2523.7 K = 2524 K
= 2.524 × 103 K.

Question 10.
Estimate the mean free path and collision frequency of a nitrogen molecule in a cylinder containing nigrogen at 2.0 atm and temperature 17°C. Take the radius of a nitrogen molecule to be roughtly 1.0 Å. Compare the collision time with the time the molecule moves freely between two successive collisions (molecular mass of N2 = 28.0 u).
According to Maxwell’s correction, the mean free path (λ) of a gas molecule is given by
λ = $$\frac{1}{\sqrt{2} \pi \mathrm{nd}^{2}}$$
where d = diameter of a molecule
and n = $$\frac{N}{V}$$ = image 6
At 2 atm pressure, the volume of the gas of mass M is given by
V = $$\frac{RT}{P}$$
T = 273 + 17° = 290 K
∴ n = $$\frac{N}{V}$$ = $$\frac{N.P}{RT}$$
Now N = 6.023 × 1023 mol-1
P = 2 atm = 2 × 1.013 × 105 Nm-2
R = 8.3 JK-1 mol-1

The r.m.s. velocity is given by
C = $$\sqrt{\frac{3 R T}{M}}$$
Putting R = 8.31 J mol-1 k-1
T = 290 K
M = 28 × 10-3 kg
we get, C = $$\sqrt{\frac{3 \times 8.31 \times 290}{28 \times 10^{-3}}}$$ = 5.08 × 102 ms-1
= 5.10 × 102 ms-1
∴ Collision frequency (v) is given by
v = $$\frac{C}{λ}$$ = $$\frac{5.1 \times 10^{2}}{1.0 \times 10^{-7}}$$ = 5.1 × 109s-1
Ler τ be the time between two successive collisions
∴ τ = $$\frac{λ}{C}$$ = $$\frac{1.0 \times 10^{-7} \mathrm{~m}}{5.1 \times 10^{2} \mathrm{~ms}^{-1}}$$
= 2.0 × 10-10s ……………………….. (i)
Also let t = time taken for the collision,

or τ = 500 t i.e. the time taken between successive collisions is 500 times the time taken for a collision to take place i.e. the two molecules are in contact. This shows that the molecule in a gas moves nearly free for most of the time.

format: plain


text:
# Does the Bible solve an NP-hard problem? [closed]

In the Bible, a census is taken of the 12 tribes of Israel:

Simeon: 59,300 Levi: 22,000 Judah: 74,600 Issachar: 54,400 Joseph: 72,700 Benjamin: 35,400 Reuben: 46,500 Gad: 45,650 Asher: 41,500 Zebulun: 57,400 Dan: 62,700 Naphtali: 53,400

In the book of Deuteronomy 27: 12-13, the tribes are partitioned into two groups, the first group consisting of Simeon, Levi, Judah, Issachar, Joseph, Benjamin, and the second group consisting of Reuben, Gad, Asher, Zebulun, Dan, Naphtali.

Someone mentioned to me that this particular partition is the optimal in the sense that it minimizes the absolute value of the total number of people in the first group minus the total number of people in the second group. This partition problem is an NP-hard problem. http://en.wikipedia.org/wiki/Partition_problem

Is this calculation correct?

• "Check my answer" questions are off-topic. It's hard to see how "check somebody else's answer" questions could be on-topic. And your title is misleading: solving a single instance of an NP-hard problem is not the same as solving the problem. – David Richerby Jun 27 '14 at 21:27
• My point is that all answer-checking problems are off-topic. It doesn't matter if the answer is yours or somebody else's. As for "solving NP-hard problems", is the Boolean formula $X$ satisfiable? Is the one-vertex graph 3-colourable? Great! We can all solve single instances of NP-complete problems. – David Richerby Jun 27 '14 at 21:44
• But every question is an answer-checking problem, by definition. – Craig Feinstein Jun 27 '14 at 22:37
• Solving an instance of an NP-hard problem is not the same as solving an NP-hard problem. The latter requires being able to solve all instances in polynomial time. – mhum Jun 28 '14 at 1:30
• @babou Well, I guess that when I say "solve", I'm actually implying "solve in polynomial time" which is the context I inferred from the asker's question. If instead "solve" was intended to mean "find a solution", brute force enumeration would be sufficient. – mhum Jun 30 '14 at 17:44

## 1 Answer

The partition provided in that passage is not optimal:

(Simeon + Levi + Judah + Issachar + Joseph + Benjamin) - (Reuben + Gad + Asher + Zebulun + Dan + Naphtali) = 318400 - 307150 = 11250

(Asher + Benjamin + Joseph + Reuben + Simeon + Zebulun) - (Dan + Gad + Issachar + Judah + Levi + Naphtali) = 312800 - 312750 = 50

• I got the same result. Indeed the bible did not solve an optimisation problem. Even if they had, it wouldn't mean anything - they may well have brute forced it. (only need to check 4096 possibilities) – d'alar'cop Jun 28 '14 at 1:45
• Naturally, I also brute-forced it. Given how few possibilities there were to check, I'd wonder why anyone would even claim that original partition was optimal (in the sense given by the asker). – mhum Jun 28 '14 at 1:52
• It seems the asker did not know how to verify themselves. And, if I may, this kind of bombastic, fallacious mathematical or scientific claim is quite common among certain religious circles. – d'alar'cop Jun 28 '14 at 2:00
• I just heard a rabbi say that one of his congregants told him this. – Craig Feinstein Jun 29 '14 at 2:15
• If Levi is excluded, the optimal partition is obtained by (Benjamin+Asher+Gad+Zeubulun+Simeon+Dan) - (Reuben+Naphtali+Issachar+Joseph+Judah) = 301950 - 301600 = 350. – mhum Jun 30 '14 at 17:52


text:
# Kernel (statistics)

Jump to: navigation, search

The term kernel has several distinct meanings in statistics.

## In Bayesian statistics

In statistics, especially in Bayesian statistics, the kernel of a probability density function (pdf) or probability mass function (pmf) is the form of the pdf or pmf in which any factors that are not functions of any of the variables in the domain are omitted.[citation needed] Note that such factors may well be functions of the parameters of the pdf or pmf. These factors form part of the normalization factor of the probability distribution, and are unnecessary in many situations. For example, in pseudo-random number sampling, most sampling algorithms ignore the normalization factor. In addition, in Bayesian analysis of conjugate prior distributions, the normalization factors are generally ignored during the calculations, and only the kernel considered. At the end, the form of the kernel is examined, and if it matches a known distribution, the normalization factor can be reinstated. Otherwise, it may be unnecessary (for example, if the distribution only needs to be sampled from).

For many distributions, the kernel can be written in closed form, but not the normalization constant.

An example is the normal distribution. Its probability density function is

${\displaystyle p(x|\mu ,\sigma ^{2})={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}e^{-{\frac {(x-\mu )^{2}}{2\sigma ^{2}}}}}$

and the associated kernel is

${\displaystyle p(x|\mu ,\sigma ^{2})\propto e^{-{\frac {(x-\mu )^{2}}{2\sigma ^{2}}}}}$

Note that the factor in front of the exponential has been omitted, even though it contains the parameter ${\displaystyle \sigma ^{2}}$ , because it is not a function of the domain variable ${\displaystyle x}$ .

## In pattern analysis

The kernel of a reproducing kernel Hilbert space is used in the suite of techniques known as kernel methods to perform tasks such as statistical classification, regression analysis, and cluster analysis on data in an implicit space. This usage is particularly common in machine learning.

## In non-parametric statistics

In non-parametric statistics, a kernel is a weighting function used in non-parametric estimation techniques. Kernels are used in kernel density estimation to estimate random variables' density functions, or in kernel regression to estimate the conditional expectation of a random variable. Kernels are also used in time-series, in the use of the periodogram to estimate the spectral density where they are known as window functions. An additional use is in the estimation of a time-varying intensity for a point process where window functions (kernels) are convolved with time-series data.

Commonly, kernel widths must also be specified when running a non-parametric estimation.

### Definition

Further information: Integral kernel

A kernel is a non-negative real-valued integrable function K satisfying the following two requirements:

• ${\displaystyle \int _{-\infty }^{+\infty }K(u)\,du=1\,;}$
• ${\displaystyle K(-u)=K(u){\mbox{ for all values of }}u\,.}$

The first requirement ensures that the method of kernel density estimation results in a probability density function. The second requirement ensures that the average of the corresponding distribution is equal to that of the sample used.

If K is a kernel, then so is the function K* defined by K*(u) = λKu), where λ > 0. This can be used to select a scale that is appropriate for the data.

### Kernel functions in common use

Several types of kernel functions are commonly used: uniform, triangle, Epanechnikov,[1] quartic (biweight), tricube,[2] triweight, Gaussian, quadratic[3] and cosine.

In the table below, 1{…} is the indicator function.

Kernel Functions, K(u) ${\displaystyle \textstyle \int u^{2}K(u)du}$ ${\displaystyle \textstyle \int K(u)^{2}du}$ Efficiency* relative to the Epanechnikov kernel
Uniform ${\displaystyle K(u)={\frac {1}{2}}\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {1}{3}}}$   ${\displaystyle {\frac {1}{2}}}$ 92.9%
Triangular ${\displaystyle K(u)=(1-|u|)\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {1}{6}}}$   ${\displaystyle {\frac {2}{3}}}$ 98.6%
Epanechnikov ${\displaystyle K(u)={\frac {3}{4}}(1-u^{2})\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {1}{5}}}$   ${\displaystyle {\frac {3}{5}}}$ 100%
Quartic
(biweight)
${\displaystyle K(u)={\frac {15}{16}}(1-u^{2})^{2}\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {1}{7}}}$   ${\displaystyle {\frac {5}{7}}}$ 99.4%
Triweight ${\displaystyle K(u)={\frac {35}{32}}(1-u^{2})^{3}\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {1}{9}}}$   ${\displaystyle {\frac {350}{429}}}$ 98.7%
Tricube ${\displaystyle K(u)={\frac {70}{81}}(1-{\left|u\right|}^{3})^{3}\,\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle {\frac {35}{243}}}$   ${\displaystyle {\frac {175}{247}}}$ 99.8%
Gaussian ${\displaystyle K(u)={\frac {1}{\sqrt {2\pi }}}e^{-{\frac {1}{2}}u^{2}}}$   ${\displaystyle 1\,}$   ${\displaystyle {\frac {1}{2{\sqrt {\pi }}}}}$ 95.1
Cosine ${\displaystyle K(u)={\frac {\pi }{4}}\cos \left({\frac {\pi }{2}}u\right)\mathbf {1} _{\{|u|\leq 1\}}}$   ${\displaystyle 1-{\frac {8}{\pi ^{2}}}}$   ${\displaystyle {\frac {\pi ^{2}}{16}}}$ 99.9%
Logistic ${\displaystyle K(u)={\frac {1}{e^{u}+2+e^{-u}}}}$   ${\displaystyle {\frac {\pi ^{2}}{3}}}$   ${\displaystyle {\frac {1}{6}}}$ 88.7%
Sigmoid function ${\displaystyle K(u)={\frac {2}{\pi }}{\frac {1}{e^{u}+e^{-u}}}}$   ${\displaystyle {\frac {\pi ^{2}}{4}}}$   ${\displaystyle {\frac {2}{\pi ^{2}}}}$ 84.3%
Silverman kernel[4] ${\displaystyle K(u)={\frac {1}{2}}e^{-{\frac {|u|}{\sqrt {2}}}}\cdot \sin \left({\frac {|u|}{\sqrt {2}}}+{\frac {\pi }{4}}\right)}$   ${\displaystyle 0}$   ${\displaystyle {\frac {3{\sqrt {2}}}{16}}}$ not applicable
• Efficiency is defined as ${\displaystyle \left(\int u^{2}K(u)du\right)^{\frac {1}{2}}\cdot \int K(u)^{2}du}$.

## References

1. ^ Named for Epanechnikov, V. A. (1969). "Non-Parametric Estimation of a Multivariate Probability Density". Theory Probab. Appl. 14 (1): 153–158. doi:10.1137/1114019.
2. ^ Altman, N. S. (1992). "An introduction to kernel and nearest neighbor nonparametric regression". The American Statistician. 46 (3): 175–185. doi:10.1080/00031305.1992.10475879.
3. ^ Cleveland, W. S.; Devlin, S. J. (1988). "Locally weighted regression: An approach to regression analysis by local fitting". Journal of the American Statistical Association. 83: 596–610. doi:10.1080/01621459.1988.10478639.
4. ^ Silverman, B. W. (1986). Density Estimation for Statistics and Data Analysis. Chapman and Hall, London.
• Li, Qi; Racine, Jeffrey S. (2007). Nonparametric Econometrics: Theory and Practice. Princeton University Press. ISBN 0-691-12161-3.
• Comaniciu, D; Meer, P (2002). "Mean shift: A robust approach toward feature space analysis". IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (5): 603–619. doi:10.1109/34.1000236. CiteSeerX: 10.1.1.76.8968.


text:
# Can the original data be extracted from an RSA private key signed message

I'm working on a system that the main objective is to verify the message was written by the right person, but it would also be desirable if the message can't be understood by anyone sniffing it.

It runs on Java/Android using RSA/ECB/PKCS1Padding (so it's not textbook RSA, but a real implementation) and the data is guaranteed not bigger than the RSA 2048 bits.

The public key on this case is not really public, it is sent to the server over standard SSL/HTTPs with certificate pinning and kept there.

The desired message is later sent over an insecure channel signed with the private key and the server can verifies the sender.

The question: can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?

edit:

Adding here to give a more complete explanation to Martin Boner.

I'm mostly a Android developer with general notion of cryptography, that's why I'm making sure to ask questions that might be dumb for some, but it's better be sure I'm not messing up important things.

For that reason, I'm not sure the direct answer to Martin, so I'll just show the code. It's Android/Kotlin code, but it's standard Java APIs:

private const val TRANSFORMATION = "RSA/ECB/PKCS1Padding"

internal fun rsaEncrypt(data: String, keyPair: KeyPair): String {
val cipher = Cipher.getInstance(TRANSFORMATION)
cipher.init(Cipher.ENCRYPT_MODE, keyPair.private)
val bytes = cipher.doFinal(data.toByteArray(Charsets.UTF_8))
return Base64.encodeToString(bytes, 0)
}

So this returned String is what's being sent. I manually tested that val bytes when converter back to string is unreadable and I have the inverse operation (below) that runs on my tests that I know the original data can be reconstructed with the public key.

internal fun rsaDecrypt(data: String, keyPair: KeyPair): String {
val cipher = Cipher.getInstance(TRANSFORMATION)
cipher.init(Cipher.DECRYPT_MODE, keyPair.public)
val bytes = Base64.decode(data, 0)
val decrypted = cipher.doFinal(bytes)
return String(decrypted, Charsets.UTF_8)
}

How the other end exactly is doing, I don't know because that was up for the Ruby developers, but it's perfectly reasonable to assume it's very similar to the above.

With this edit in mind, I'll add a secondary question:

1. (original question) Can someone that sniffed the message over that insecure channel recreate (within reasonable time frame) the original message?
2. (Bonus) Is there any other security concern/issue here? For example, could someone after sniffing a few messages over the insecure channel, be able to regenerate or fake the private key and pretend be the proper user?
• Do you mean just the signature is sent over the insecure channel, or the message and the signature are sent over the channel? If the former, how does the recipient retrieve the message; if the latter, then the message is visible in plain-text. – Martin Bonner Jun 18 at 14:18
• Hi @MartinBonner I've edited my question with some detailed information. Thanks for looking up my question. – Budius Jun 18 at 19:52

Whenever you see the letters ECB, you should run away screaming. This is a telltale sign that something has gone terribly, horribly wrong. The code fragment you quoted implements what we sometimes call ‘textbook RSA’, which is a polite way to discreetly announce to the cocktail partygoers that you are desperately in need of a professional cryptographer.

This is not your fault: whoever designed the Java API that requires you to specify ECB in a string and which you will use to ‘encrypt with the private key and decrypt with the public key’ (which is a contradiction in terms that makes cryptographers twitch involuntarily, sometimes leading to a cocktail dribbling down your face and shirt) did not have the decency to ask for a professional opinion—which is what you are more or less doing now!—before they inflicted a monumentally wrong confusion of ideas into an API set in stone.

Let's back up a moment. What do you and your peer have in common, and what security do you want?

• If you share a secret already, and you want to exchange unforgeable and possibly secret messages, what you want is a symmetric-key authenticator like HMAC-SHA256, or a symmetric-key authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305. But you mentioned public keys, so maybe you and your peer don't share a secret yet—maybe all you have is your respective public keys, which are known to be correct but are not secret.

• If you share a public telephone book with public keys, and you want to exchange unforgeable and possibly secret messages, what you want is public-key key agreement like X25519, which is a way for you to use your private key and your peer's public key in the telephone book to compute a secret, which can also be computed by your peer using their private key and your public key in the telephone book so that you and your peer have a shared secret; or you want public-key authenticated encryption, like NaCl crypto_box_curve25519xsalsa20poly1305, which works by stringing together public-key key agreement (X25519) and symmetric-key authenticated encryption (crypto_secretbox_xsalsa20poly1305).

• If your peer has a public telephone book where you are named, and you want to send a message to your peer that your peer can show to a third party and convince the third party it came from you, then what you want is public-key signatures like Ed25519.

You could also use an RSA-based signature scheme like PKCS#1 v2.1 RSASSA-PSS, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer Ed25519, unless the cost of verification is your principal bottleneck.

• If you have a public telephone book where your peer is named, and you want to send a message to your peer anonymously so that only your peer can read it but not necessarily verify it came to you, then what you want is public-key anonymous encryption like NaCl crypto_box_curve25519xsalsa20poly1305 with an ephemeral public key.

You could also use an RSA-based encryption scheme like PKCS#1 v2.1 RSAES-OAEP, strung together with an authenticated cipher like AES-GCM, but unless you have a specific technical reason motivating the use of RSA, you are better off using the smaller faster safer NaCl crypto_box_curve25519xsalsa20poly1305 with ephemeral keys, unless the cost of encrypting messages is your principal bottleneck.

But OK, let's suppose you are using some RSA signature scheme.

Any serious RSA-based signature scheme involves hashing the message. The simplest one, RSA-FDH, uses a hash function $$H$$ that hashes messages into all or nearly all of the set $$\{0, 1, 2, \dots, n - 1\}$$; a signature under public key $$n$$ on a message $$m$$ is an integer $$s$$ such that $$s^3 \equiv H(m) \pmod n$$. From the signature $$s$$, even if you don't have the message $$m$$, you can recover $$H(m)$$ simply by computing $$s^3 \bmod n$$, but if $$H$$ is a good hash function this doesn't help to recover $$m$$.

With RSASSA-PSS, the equation is more like $$s^3 \equiv 2^t r + H(r \mathbin\| H(m)) \equiv n$$, where $$H$$ is a smaller hash function like SHA-256. Again, you can recover $$H(r \mathbin\| H(m))$$ this way, but not $$m$$.

There are some ‘message-recovery’ variants of RSA signature schemes, in which some part of the message $$m$$ is embedded in $$s$$ alongside $$H(m)$$, but they are not widely used and you would probably know if you were using one.

All that said: Usually what you do is send a signed message, i.e. a message alongside its signature; otherwise, how does the recipient act on the message, or even find what message the signature corresponds to? And if you do that, there is nothing a priori that prevents anyone but the intended recipient from reading the message—after all, in a signature, only the sender's keys are involved.

You can combine public-key signature and public-key encryption, but this is usually a bad idea for two reasons:

1. A secure composition is hard to get right; OpenPGP and S/MIME got it wrong.
2. Public-key signature also usually guarantees that third parties can verify messages, which is usually not what you want for private conversations.

So, you are most likely better off using NaCl crypto_box_curve25519xsalsa20poly1305, which does it all in one: combines you private key, your peer's public key, a 192-bit message number, and a message, and returns a ciphertext that your peer and only your peer can check for forgery and decrypt.

• How thorough, clear, and useful! – Patriot Jun 19 at 2:40
• One shouldn't always run away screaming from "ECB". I've just written some secure code using ECB (at least I think it's secure). ... It implements CTR. I accept that this is the only usage that won't cause raised eyebrows from cryptographers. – Martin Bonner Jun 19 at 5:25


text:
# nLab apartness relation

Apartness relations

# Apartness relations

## Idea

An apartness relation is a binary relation that, instead of saying when two things are the same (as an equivalence relation), states when two things are different – an inequality relation.

Apartness relations are most used in constructive mathematics; in classical mathematics, equivalence relations can take their place (mediated by negation).

The apartness relations that we discuss here are sometimes called point–point apartness, to distinguish this from the related concepts of set–set or point–set apartness relations; see proximity space and apartness space (respectively) for these.

## Definitions

### Abstract

A set $S$ equipped with an apartness relation is a groupoid (with $S$ as the set of objects) enriched over the cartesian monoidal category $TV^\op$, that is the opposite of the poset of truth values, made into a monoidal category using disjunction. By the law of excluded middle (which says that $TV$ is self-dual under negation), this is equivalent to equipping $S$ with an equivalence relation (which makes $S$ a groupoid enriched over the cartesian category $TV$ itself). But in constructive mathematics (or interpreted internally), it is a richer concept with a topological flavour.

### Concrete

Of course, nobody but a category-theorist would use the above as a definition of an apartness relation. Normally, one defines an apartness relation on $S$ as a binary relation $\#$ satisfying these three properties:

• irreflexivity: for all $x: S$, $x \# x$ is false;
• symmetry: for all $x, y: S$, if $y # x$, then $x # y$;
• comparison: for all $x, y, z: S$, if $x # z$, then $x # y$ or $y # z$.

(Notice that these are dual to the axioms for an equivalence relation; like those axioms, these correspond to identity morphisms, inverses, and composition in a groupoid.)

The negation of an apartness relation is an equivalence relation. (On the other hand, the statement that every equivalence relation is the negation of some apartness relation is equivalent to excluded middle, and the statement that the negation of an equivalence relation is always an apartness relation is equivalent to the nonconstructive de Morgan law.) An apartness relation is tight (see connected relation) if this equivalence relation is equality; any apartness relation defines a tight apartness relation on the quotient set. A tight apartness relation, also called an inequality, is often written $\ne$ instead of $\#$, but keep in mind that $\ne$ is not the negation of $=$; rather, $=$ is the negation of $\ne$. (So inequality, when it exists, is more basic than equality.)

If $S$ and $T$ are both sets equipped with apartness relations, then a function $f\colon S \to T$ is strongly extensional if $x \# y$ whenever $f(x) \# f(y)$; that is, $f$ reflects apartness. The strongly extensional functions are precisely the enriched functors between $TV^\op$-enriched groupoids, so they are the correct morphisms. (Note that there is no nontrivial notion of enriched natural isomorphism, at least not when the apartness in $T$ is tight.)

## The category of inequality spaces

By an inequality space, I mean a set equipped with a tight apartness relation. By a map, I mean a strongly extensional function between inequality spaces.

The category of inequality spaces has all (small) limits, created by the forgetful functor to Set. (For example, $(a,b) \ne (x,y)$ iff $a \ne x$ or $b \ne y$.) Similarly, it has all finite coproducts, and it has quotients of equivalence relations. In fact, this category is a complete pretopos. It is not, however, a Grothendieck topos (or even a topos at all), because it doesn't have all infinite coproducts. (To be precise, the statement that it has all small coproducts, or even that it has a subobject classifier, seems to be equivalent to excluded middle.)

We can say, however, that it has coproducts indexed by inequality spaces, although to make this precise is a triviality. More interestingly, it has products indexed by inequality spaces; that is, it is (even locally) a cartesian closed category. In particular, given inequality spaces $X$ and $Y$, the set $\StrExt(X,Y)$ of maps from $X$ to $Y$ becomes an inequality space under the rule that $f \ne g$ iff $f(x) \ne g(x)$ for some $x\colon X$.

If you generalise from inequality spaces to allow non-tight apartness relations, then you get (at first) a different category. However, now you also have $2$-morphisms which serve to identify unequal but equivalent (that is, not apart) elements of a space, so the resulting bicategory is equivalent to the category of inequality spaces.

## Topological aspects

### The apartness topology

Let $S$ be a set equipped with an apartness relation $\ne$. Using $\ne$, many topological notions may be defined on $S$. (Often one assumes that the apartness is tight; this corresponds to the $T_0$ separation axiom in topology.)

If $U$ is a subset of $S$ and $x$ is an element, then $U$ is a $\ne$-neighbourhood (or $\ne$-neighborhood) of $x$ if, given any $y\colon S$, $x \ne y$ or $y \in U$; note that $x \in U$ by irreflexivity. The neighbourhoods of $x$ form a filter: a superset of a neighbourhood is a neighbourhood, and the intersection of $0$ or $2$ (hence of any finite number) of neighbourhoods is a neighbourhood.

A subset $G$ is $\ne$-open if it's a neighbourhood of all of its members. The open subsets form a topology (in the sense of Bourbaki): any union of open subsets is open, and the intersection of $0$ or $2$ (hence of any finite number) of open subsets is open.

The $\ne$-complement of $x$ is the subset $\{y\colon S \;|\; x \ne y\}$; this is open by comparison. More generally, the $\ne$-complement of any subset $A$ is the set $\tilde{A}$, defined as:

$\tilde{A} \coloneqq \{y \;|\; \forall{x} \in A,\; x \ne y\} .$

This is not in general open, but you would use it where you would classically use the set-theoretic complement. However, if $A$ is open to begin with, then $\tilde{A}$ equals the set-theoretic complement.

If $x \ne y$, then $x \in \tilde{y}$ and $y \in \tilde{x}$. Thus, if $\ne$ is tight, then $(S, \ne)$ satisfies the $T_1$ separation axiom. Symmetry is important here; if we removed symmetry from the axioms of apartness (obtaining a quasi-apartness?) but retained tightness, then we would still get a $T_0$ topology, but it would not be $T_1$. This is a version of the fact that failure of $T_1$ is given by a partial order (or a preorder if $T_0$ might also fail).

The $\ne$-closure $\bar{A}$ of a subset $A$ is the complement of its complement. This closure is a closure operator: $A \subset \bar{A}$, $\overline{\bar{A}} = \bar{A}$ (in fact, $\overline{\tilde{A}} = \tilde{A}$), $\bar{A} \subset \bar{B}$ whenever $A \subset B$, $\overline{S} = S$ (in fact, $\bar{\empty} = \empty$ too), and $\overline{A \cap B} = \bar{A} \cap \bar{B}$ (but not $\overline{A \cup B} = \bar{A} \cup \bar{B}$).

The antigraph of a function $f\colon S \to T$ is

$\{(x,y) \;|\; x\colon S, y\colon T \;|\; f(x) \ne y\} .$

Recall that in ordinary topology, a function between Hausdorff spaces is continuous iff its graph is closed. Similarly, a function $f\colon S \to T$ is strongly extensional iff its antigraph is open. (Then the graph of $f$ is the complement of the antigraph.)

One important topological concept that doesn't appear classically is locatedness; in an inequality space, a subset $A$ is located if, given any point $x$ and any neighbourhood $U$ of $x$, either $U \cap A$ is inhabited (that is, it has a point) or some neighbourhood of $x$ (not necessarily $U$) is contained in $\tilde A$. Note that every point is located. (For an example of a set that need not be located, consider $\{x\colon S \;|\; p\}$, where $p$ is an arbitrary truth value. In an inhabited space, this set is located iff $p$ is true or false.)

### Relation to metric spaces

Recall that, as Bill Lawvere taught us, a metric space is a groupoid (or $\dagger$-category) enriched over the category $([0,\infty[^\op,+)$ of nonnegative real numbers, ordered in reverse, and made monoidal under addition. (Actually, you get a metric only if you impose a tightness condition, although again you can recover this up to equivalence from the $2$-morphisms. Furthermore, Lawvere advocated using $[0,\infty]$ instead of $[0,\infty[$, and also dropping the symmetry requirement to get enriched categories instead of groupoids. Thus, he dealt with extended quasipseudometric spaces. These details are not really important here.)

There is a monoidal functor from $([0,\infty[^\op,+)$ to $TV^\op$ that maps a nonnegative real number $x$ to the truth value of the statement that $x \gt 0$. Accordingly, any (symmetric) metric space becomes an inequality space, and any function satisfying $d(f(x),f(y)) \leq d(x,y)$) is strongly extensional.

The topological properties of metric spaces fit well with those of inequality spaces if you always work in this direction. For example, a set which is $d$-open will also be $\ne$-open, but not necessarily the other way around. Similarly, a (merely) continuous function between metric spaces is (still) strongly extensional.

### Relation to gauge spaces and uniform spaces

In analysis, many spaces are given as gauge spaces, that is by families of pseudometrics; these also become inequality spaces by declaring that $x \ne y$ iff $d(x,y) \gt 0$ for some pseudometric $d$ in the family. (This will actually be a tight apartness iff the family of pseudometrics is separating.)

Classically, any uniform space may be given by a family of pseudometrics, but this doesn't hold constructively. In particular, a topological group may not be an inequality group (as in the next section). However, we can generalize a bit beyond gauge spaces: any uniformly regular uniform space becomes an inequality space by declaring that $x \ne y$ iff there is an entourage $U$ with $(x,y)\notin U$. (If the uniform space is not uniformly regular, the result is merely an inequality relation, not an apartness.)

### Relation to proximity spaces

The constructive theory of proximity spaces is based on a generalisation of apartness relations (which here go between points) to an apartness relation between sets. These are called apartness spaces; just as apartness relations (between points) are classically equivalent to equivalence relations, so apartness spaces are classically equivalent to proximity spaces, with two sets being proximate if and only if they are not apart.

Of course, any apartness space has an apartness relation between points: $x$ and $y$ are apart iff $\{x\}$ and $\{y\}$ are apart.

### Relation to locales

Let $X$ be a set, regarded as a discrete locale, whose frame of opens is $O(X) = P(X)$, the power set of $X$. That is, the opens in the locale $X$ are precisely the subsets of the set $X$. Since discrete locales are locally compact (every set is the union of its K-finite subsets), the locale product $X\times X$ agrees with the spatial product, so that $X\times X$ is also discrete and every subset of $X\times X$ is open. Thus, the opens in the locale $X\times X$ are precisely the subsets of $X\times X$. In particular, an equivalence relation on the set $X$ can be identified with an open equivalence relation (in Loc) on the discrete locale $X$.

Thus, the following theorem gives a different precise sense in which apartness relations are dual to equivalence relations.

###### Theorem

An apartness relation on a set $X$ is the same as a (strongly) closed equivalence relation on the discrete locale $X$. Moreover, the apartness topology defined above is, as a locale, the quotient of this equivalence relation.

###### Proof

By definition, a (strongly) closed sublocale of a locale $Y$ is one of the form $\mathsf{C}U$, for some open $U\in O(Y)$. Thus, when $X$ is a discrete locale, a closed sublocale of $X\times X$ is of the form $\mathsf{C}U$ for some subset $U$ of $X\times X$. This subset is the extension of the apartness relation, i.e. $U = \{ (x,y) \mid x\#y \}$.

For the first claim, therefore, it remains to show that the three axioms of an equivalence relation for $\mathsf{C}U$ correspond to the apartness axioms for $\#$. Note that pullback along locale maps respects closed complements, i.e. $f^*(\mathsf{C}U) = \mathsf{C}(f^*U)$. Thus, the pullback of $\mathsf{C}U$ along the twist map $X\times X \to X\times X$ is the closed sublocale corresponding to the twist of $U$, i.e. the set $\{ (x,y) \mid y\#x \}$. Since $\mathsf{C}$ is a contravariant order-isomorphism between the posets of open and closed sublocales, symmetry for $\mathsf{C}U$ is equivalent to symmetry for $\#$. Similarly, pulling $\mathsf{C}U$ back to $X\times X\times X$ along one of the three canonical projections gives the closed sublocale dual to the corresponding pullback of $U$ itself, and $\mathsf{C}$ transforms unions to intersections; thus transitivity for $\mathsf{C}U$ is equivalent to comparison for $\#$. Finally, the pullback of $\mathsf{C}U$ along the diagonal is the closed sublocale dual to the similar pullback of $U$, so to say that the former is all of $X$ is equivalent to saying that the latter is $\emptyset$; thus reflexivity for $\mathsf{C}U$ is equivalent to irreflexivity for $\#$.

Now, the quotient in $Loc$ of such an an equivalence relation in particular comes equipped with a surjective locale map from $X$. Thus, it is a spatial locale and can be regarded as a topology on the set $X$. Moreover, quotients in $Loc$ are constructed as equalizers in $Frm$, so we have to compute the equalizer of the two maps $O(X) = P(X) \to O(\mathsf{C}U)$, where $O(\mathsf{C}U)$ is the frame of opens of $\mathsf{C}U$ regarded as a locale in its own right. Equivalently, this means the equalizer of the two maps $P(X) \xrightarrow{\pi_i} P(X\times X) \xrightarrow{j_{\mathsf{C}U}} P(X\times X)$, where $j_{\mathsf{C}U}$ is the nucleus corresponding to $\mathsf{C}U$.

Now by definition, $j_{\mathsf{C}U}(V) = V\cup U$. Thus, the elements of this equalizer — which is to say, the opens in the locale quotient — are subsets $V$ of $X$ such that $(V\times X) \cup U = (X\times V) \cup U$. Reexpressed in terms of $\#$, that means that for any $x,y\in X$ we have $(x\in V \vee x\#y) \iff (y\in V \vee x\#y)$. But since $\#$ is symmetric, this is equivalent to the unidirectional implication $(x\in V \vee x\#y) \to (y\in V \vee x\#y)$, and since $x\#y$ always implies itself, this is equivalent to $x\in V \to (y\in V \vee x\#y)$, which is precisely the condition defining the open sets in the apartness topology above.

Recall that the negation of an apartness relation on $X$ is an equivalence relation on the set $X$. This is the spatial part of the above closed localic equivalence relation, which in general (constructively) need not be itself spatial. The apartness relation is tight just when this spatial part is the diagonal. (By contrast, to say that the closed localic equivalence relation is itself the diagonal is to say that the discrete locale $X$ is Hausdorff, which is only true if $X$ has decidable equality.)

Another characterization of the $\#$-open sets is that $U$ is $\#$-open if $U\times X \subseteq (X\times U) \cup W_\#$, where $W_\#$ is $\#$ regarded as a subset of $X\times X$. Rephrased in terms of complementary closed sublocales, this says that $\mathsf{C}U$ is “closed under the equivalence relation” dual to $\#$. Thus, the closed sublocales of $X$ with its $\#$-topology (i.e. the formal complements of $\#$-open sets) correspond precisely to the closed sublocales of $X$ (the formal complements of arbitrary subsets of $X$) that respect this equivalence relation.

As a partial converse to the above theorem, if $X$ is a localically strongly Hausdorff topological space, meaning that its diagonal is a strongly closed sublocale, then the pullback of this diagonal to the discrete locale on the set of points of $X$ is a closed localic equivalence relation, hence an apartness, whose $\ne$-topology refines the given topology. See this theorem. If we are given an apartness relation $\ne$, it is unclear whether the $\ne$-topology is localically strongly Hausdorff; but if it is, then the apartness relation resulting from this topology is stronger than the given $\ne$.

## In algebra

Since inequality spaces have finite limits, the usual constructions of universal algebra apply; it's straightforward to define inequality groups, inequality rings, and so on.

The various subsets that appear in algebra (such as subgroups, ideals, and cosets) become less fundamental than certain subsets that are, classically, simply their complements. For example, a left ideal in a ring $R$ is a subset $I$ such that $0 \in I$, $x + y \in I$ whenever $x, y \in I$, and $x y \in I$ whenever $x \in I$. But a left antiideal in an inequality ring $R$ is an $\ne$-open subset $A$ such that $0 \in A$ is false, $x \in A$ or $y \in A$ whenever $x + y \in A$, and $x \in A$ whenever $x y \in A$. (The $\ne$-openness requirement is automatic if $\neg(0\in A)$ is strengthened to $p\ne 0$ for all $p\in A$, using that the ring operations are strongly extensional.) Note that the complement of an antiideal is an ideal, but not every ideal can be constructively shown to be the complement of an antiideal; so antiideals are more fundamental than ideals, in an inequality ring.

Prime ideals are even more interesting. A two-sided antiideal $A$ (so also satisfying that $y \in A$ whenever $x y \in A$) is antiprime (or simply prime if no confusion is expected) if $1 \in A$ and $x y \in A$ whenever $x, y \in A$. Now the complement of an antiprime antiideal may not be a prime ideal (as normally defined). But in fact, it is antiprime antiideals that are more important in constructive algebra. In particular, an integral domain in constructive algebra is an inequality ring in which the antiideal of nonzero elements is antiprime.

The localic perspective on apartness relations extends naturally to anti-algebra: an antiideal is the same as a closed ideal in a discrete localic ring that respects the closed equivalence relation corresponding to $\ne$. Equivalently, this is a closed ideal of the $\ne$-topology regarded as a (non-discrete) localic ring. The spatial part of this closed localic ideal is then the ordinary ideal complementary to the antiideal, and so on. Moreover, since unions of closed sublocales correspond to intersections of their open complements, an antiideal $A$ is antiprime exactly when its corresponding closed localic ideal $\mathsf{C}A$ is “prime” in an appropriate internal sense in Loc, namely that $m^*(\mathsf{C}A) \subseteq (\mathsf{C}A \times R) \cup (R\times \mathsf{C}A)$, where $m:R\times R\to R$ is the multiplication. The fact that the complement of an antiprime antiideal need not be prime in the usual sense corresponds to the fact that taking the spatial part of sublocales doesn’t commute with unions.

For more about apartness algebra, see antisubalgebra.

basic symbols used in logic

$\phantom{A}$symbol$\phantom{A}$$\phantom{A}$meaning$\phantom{A}$
$\phantom{A}$$\in$$\phantom{A}$element relation
$\phantom{A}$$\,:$$\phantom{A}$typing relation
$\phantom{A}$$=$$\phantom{A}$equality
$\phantom{A}$$\vdash$$\phantom{A}$$\phantom{A}$entailment / sequent$\phantom{A}$
$\phantom{A}$$\top$$\phantom{A}$$\phantom{A}$true / top$\phantom{A}$
$\phantom{A}$$\bot$$\phantom{A}$$\phantom{A}$false / bottom$\phantom{A}$
$\phantom{A}$$\Rightarrow$$\phantom{A}$implication
$\phantom{A}$$\Leftrightarrow$$\phantom{A}$logical equivalence
$\phantom{A}$$\not$$\phantom{A}$negation
$\phantom{A}$$\neq$$\phantom{A}$negation of equality / apartness$\phantom{A}$
$\phantom{A}$$\notin$$\phantom{A}$negation of element relation $\phantom{A}$
$\phantom{A}$$\not \not$$\phantom{A}$negation of negation$\phantom{A}$
$\phantom{A}$$\exists$$\phantom{A}$existential quantification$\phantom{A}$
$\phantom{A}$$\forall$$\phantom{A}$universal quantification$\phantom{A}$
$\phantom{A}$$\wedge$$\phantom{A}$logical conjunction
$\phantom{A}$$\vee$$\phantom{A}$logical disjunction
$\phantom{A}$$\otimes$$\phantom{A}$$\phantom{A}$multiplicative conjunction$\phantom{A}$
$\phantom{A}$$\oplus$$\phantom{A}$$\phantom{A}$multiplicative disjunction$\phantom{A}$

## References

According to Troelstra and van Dalen:

Brouwer (1919) introduced the notion of apartness (örtlich verschieden, Entfernung)…. The axioms of the theory of apartness were formulated by Heyting (1925).

• L.E.J. Brouwer, Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossenen Dritten II: Theorie der Punktmengen. 1919

• Arend Heyting, Intuïtionistische Axiomatiek der Projectieve Meetkunde (Dutch), Ph.D. Thesis, 1925

• Errett Bishop‘s Foundations of Constructive Analysis (1967) uses apartness for the real numbers and more general metric spaces.

• The 1985 edition with Douglas Bridges, Constructive Analysis, includes the general definition of apartness relation, there called an “inequality relation” (though in many other sources, as here, an inequality relation need not satisfy comparison).

• Anne Troelstra's and Dirk van Dalen's Constructivism in Mathematics (1988) uses apartness for the reals (volume 1), and general apartness relations in algebra (volume 2, chapter 8). They say “preapartness” and “apartness” instead of “apartness” and “tight apartness” respectively.

• Apartness plays a minimal role in A Course in Constructive Algebra (also 1988), by Ray Mines, Fred Richman, and Wim Ruitenburg.

• A great reference for point-set topology in constructive mathematics is the Ph.D. thesis of Frank Waaldijk, Modern Intuitionist Topology (1996).

Last revised on July 3, 2018 at 10:23:31. See the history of this page for a list of all contributions to it.