text:
Change Coordinates -A 1.Bam -B 2.Bam -O 3.Bam?
4
4
Entering edit mode
10.4 years ago

I've got a BAM file 'short-A' of my short reads against the thousands of assembled contigs of my genome A, and I now would like to project the entries in BAM file 'short-A' onto the chromosomes in genome B. Genome A and genome B are too different to align the short reads from A straight to genome B, but close enough that I can align most of the thousands of assembled contigs from genome A to genome B, producing a 'contigs-A' file against genome B. So I now want to place each of the millions of short reads in my 'short-A' BAM file in the coordinates for genome B using the 'contigs-A' alignments as the guide.

Is there a standard way of doing that?

I don't know if it makes sense to have this in samtools or somewhere else, but I imagine it could be something like:

coordinateprojection -a readsAcontigsA.bam -b contigsAchrsB.bam -o readsAchrsB.bam

Just as an example dataset, here is the mouse readsets used for assembly piled up against the mouse contigs (here just the whole gene body of mouse PAX2, PAX5 and PAX8), and the mouse assembled contigs aligned to human using lastz:

And I would like to have a tool that does something like:

coordinateprojection -a readsMousecontigsMouse.bam -b contigsMousechrsHuman.bam -o readsMousechrsHuman.bam

Cheers

bam liftover samtools • 4.0k views
3
Entering edit mode

Why not re-align the reads to the new reference?

3
Entering edit mode

What do you use for genome A vs genome B alignment? What is the format of the output? Not sure about your genome, but often one can get MAF file where multiple regions of A map to multiple regions of B.

3
Entering edit mode

what do you mean by 'projection of coordinates' to the new contigs and in what way is that different than mapping the reads to the new contigs?

1
Entering edit mode

this would be easier if there were clear rules about dealing with ambiguities - multiple hits and converging hits

0
Entering edit mode

Genome A and genome B are too different to re-align the short reads from A straight to genome B.

0
Entering edit mode

@Jeremy Leipzig: Supposing one has already dealt with most of them using "bwa aln" to map the short reads and "bwa bwasw" to map the contigs, I would be happy to just copy the whole lot on the other coordinates.

0
Entering edit mode

@avilella, if you can write out the specifics of how you want this method to work then I can probably implement it for you (most likely in R) and get this question answered within 6 days.

0
Entering edit mode

I've now added an example dataset using lastz for mouse contigs against human chromosomes. From the lastz soft sam I created a bam. In parallel, I created the bam pileup of the mouse reads into the mouse contigs.

4
Entering edit mode
10.4 years ago
brentp 23k

UCSC has a tool called liftOver that may be of help. You'll have to create a .chain file that maps regions from one genome to the other. Here is an explanation of how to do this. Briefly, you use BLAT to find the regions of similarity that are used to make the alignments.

I'm not sure that this will do better than re-mapping the reads, but it seems to be what you are requesting.

After you have the chain file, then you can use liftOver on your BAM coordinates to map them to the new genome.

2
Entering edit mode
10.4 years ago

if I understood correctly your point, since remapping reads against genome B is not an option, then brentp's solution is the one I would follow: if you need to project positions from one genome to other the best available tool nowadays is UCSC's LiftOver. if this solution is not what you are looking for then I would go for a combined approach of what most of us think you should do (remapping) and what it seems you want to do (project coordinates).

if you already have your genome A assembled contigs, I would split the BAM file into several BAM files containing only the reads of each contig (1 BAM file per contig). then I would project each contig start and end position into genomeB's reference, generating several sections of the entire reference (1 fasta reference of genomeB per genomeA aligned contig). finally I would pair each contig files (genomeA BAM file and genomeB fasta reference) and remap each genomeA contig reads against the associated genomeB projected reference.

in summary, if genomeA and genomeB are as similar as you expect, then forcing all reads from a genomeA contig to map its corresponding genomeB reference would retain a similar coverage, and you would end up with several genomeB BAM files which you could eventually merge into a single final genomeB BAM file containing all original reads now mapped as desired.

2
Entering edit mode
10.4 years ago

Since I read your question for the first time, the feeling was bothering me that the approach you want to take is invalid. I have been thinking about a solution since then and now see the need to supply an answer. However, that might not be the answer you would like to have, some critical points also due to missing information in your question.

In one sentence: you will make up (fake) read alignments, indirectly claiming that reads map in a position of genome B, while they in fact don't align there and could only be aligned to genome A.

First, I have to question your statement:

Genome A and genome B are too different to align the short reads from A straight to genome B, but close enough that I can align most of the thousands of assembled contigs from genome A to genome B

How can you possibly claim that with only trying bwa? And what is the real distance between those genomes, what is the sequence identity, and what is the degree of genome rearrangements/syntheny?

One of the core problems of your approach is using bwa to align the reads. bwa has low sensitivity, especially when it comes to more different sequences. So, try a more sensitive aligner first to map the reads directly, eg. bfast, blat, mosaic, novoalign, lastz, or try LAST (thanx to darked's comment).

Why is the mapping approach invalid? There are two approaches I could think of:

• globally align whole contigs of genome A against Genome B (pretty much treating it like a large short read), yielding one mapping coordinate, ambiguity asside, for the contig of A in genome B.

• locally align the contigs such that partial contigs of A, with minimum sequence identity cut-off, within a contig can be aligned to a region in B, yielding possibly a set of genomic coordinates in B per contig.

Both approaches have in common that they don't deal with ambiguities, and that is a big deal.

Then, I claim that approach 1 in invalid and will create bogus mapped coordinates of reads, assigning them to regions where definitely do not align.

Only one example of what could go wrong: Imagine the following situation, a contig of genome A, consisting of three regions R1, R2, R3 of high sequence conservation (think of that for example as three highly conserved genes). All these regions are present in genome B as well (R1', R2', R3'), but due to a rearrangement, R2' is replaced by R4' and relocated to a different position. Now, following your relatively low sequence-identity threshold R1,R2,R3 -> R1',R4',R3'. Now for genome A, you got a lot of reads for R2, which now will be assigned to R1',R4',R3' but they will be assigned to region R4', where they definitely do not belong to.

Based on the above, the second approach would be much better, that would be best accomplished by a bidirectional best blast hit between the genomes (with eg. identity cut-off 90%), and then mapping those regions. Would also need to treat ambiguities somehow, and again bwa is not the tool of choice. However, if stretches of high sequence similarity existed, then the reads would possibly also align there directly.

Conclusion: Before thinking about how to technically perform an analysis, we have to think more about the validity of the approach. Lacking some important pieces of information, the above couldn't be the final word there. I consider mapping read alignments between distant genomes problematic. The risk is to build up the impression (or tricking yourself into believing) that there exist alignments where in fact they couldn't be aligned, and that ambiguities go unnoticed. Only alignments that can be found and proven are valid alignments, if your reads don't align, yes, then they don't align. Try more sensitive tools to align reads directly.

1
Entering edit mode

No, I tried lastZ, but ofc had to stripp the quality information converting to fasta, as a downside.

1
Entering edit mode

A few points. 1) I second that bwa is not sensitive enough for cross-species alignment, at least under the default. 2) No one is going to align contigs "globally". That is simply impossible most of time. 3) Most of large-scale changes are easier to detect from whole-genome alignment then from short reads. 4) In general, Albert takes the right strategy: aligning contigs and then converting the short read coordinates, which, if done correctly, should be better than directly mapping short reads. Nonetheless, there is no convenient tool for such an application.

0
Entering edit mode

Great answer. Short question about alternative mappers: did you use lastz for Illumina fastq reads mapping, or iz it a typo and it should be LAST (http://last.cbrc.jp/). BTW, I am using the later.

0
Entering edit mode

A few points. 1) I second that bwa is not sensitive enough for cross-species alignment, at least under the default. 2) No one is going to align contigs "globally". That is simply impossible most of time. 3) Most of large-scale changes are easier to detect from whole-genome alignment then from short reads. 4) In general, Albert takes the right strategy: aligning contigs and then converting the short read coordinates, which should be better than directly mapping short reads. Nonetheless, there is no convenient tool for such an application.

0
Entering edit mode

I've now added an example dataset using lastz for mouse contigs against human chromosomes. From the lastz soft sam I created a bam. In parallel, I created the bam pileup of the mouse reads into the mouse contigs.

0
Entering edit mode

@lh3, regarding 2) I had the impression that he just wanted to do this and that would be not a good idea, using bwa also for aligning the contigs, I read this out of one of avilella's comments. regarding 4) which albert, or do you mean avilella?

1
Entering edit mode
10.4 years ago
Darked89 4.2k

You did not provided info about the reads you are mapping (Illumina paired?), their lengths and the genomes (no exact species needed, but it may help if one knows if these are i.e. compact Eukaryote, complex mammals, or some even more exotic combination).

For inter-mammalian short read mapping you may look at LAST last.cbrc.jp): http://last.cbrc.jp/doc/last-tutorial.txt (see Example 8: Align aardvark fastq reads to the human genome). That way you may (or not...) sensibly align reads from A to B.

0
Entering edit mode

I've now added an example where I first assembled short reads from species A in contigs in species A, cross-align contigs in species A to species B using LASTZ, and also pile up all the reads from species A onto the assembled contigs in species A. I would now want to do the coordinate projection from one bam to another as described in the example.

Traffic: 1875 users visited in the last hour
FAQ
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.


text:
Can a topological manifold be non-connected and each component with different dimension?

These are two definitions in page 48 of the book an introduction to manifolds by Loring Tu.

Definition 5.1. A topological space $M$ is locally Euclidean of dimension $n$ if every point $p$ in $M$ has a neighborhood $U$ such that there is a homeomorphism $\phi$ from $U$ onto an open subset of $\mathbb R^n$.

Definition 5.2. A topological manifold is a Hausdorff, second countable, locally Euclidean space. It is said to be of dimension $n$ if it is locally Euclidean of dimension $n$.

In the last lines of page 48, we reed,

Of course, if a topological manifold has several connected components, it is possible for each component to have a different dimension.

But this is a bit strange for me. If a topological manifold has several connected components and each component has different dimension, then how this manifold can be locally Euclidean space, say for example of dimension $n$? That is, by the above definition of topological manifolad, can a non-connected toplogical space be a topological manifold?

• It seems like Definition 5.1 defines locally Euclidean of dimension n, as opposed to just locally Euclidean, which is used in Definition 5.2. Presumably, the definition of locally Euclidean is the same as Definition 5.1, except it allows $n$ to depend on $p$. That, at least, makes it logically consistent. – Jason DeVito May 9 '17 at 16:13

As written, the term "locally Euclidean" is in fact not even defined at all (only "locally Euclidean of dimension $n$" is defined). What it appears the author really intended is the following pair of definitions:

Definition 5.1'. A topological space $M$ is locally Euclidean of dimension $n$ at a point $p\in M$ if $p$ has a neighborhood $U$ such that there is a homeomorphism $\phi$ from $U$ onto an open subset of $\mathbb R^n$. A topological space $M$ is locally Euclidean if for each $p\in M$, there exists $n$ such that $M$ is locally Euclidean of dimension $n$ at $p$.

Definition 5.2'. A topological manifold is a Hausdorff, second countable, locally Euclidean space. It is said to be of dimension $n$ if it is locally Euclidean of dimension $n$ at every point.

I would add, however, that this definition is not very standard. Most people define manifolds such that they must have the same dimension at every point, even if they are disconnected.

We must allow a manifold to have connected components of different dimensions because such an object occurs naturally. For example, there is a theorem that the fixed point set of a compact Lie group acting smoothly on a manifold is a manifold (L. Tu, \textit{Introductory Lectures on Equivariant Cohomology}, Annals of Mathematics Studies, Princeton University Press, Th. 25.1, forthcoming). Now consider the action of the circle $$S^1$$ on the complex projective space $$\mathbb{C}P^2$$ by $$\lambda \cdot [z_0, z_1, z_2] = [z_0, z_1, \lambda z_2].$$ The fixed point set of this action has two connected components, the line $$[*,*,0]$$ and the single point $$[0,0,*]$$.

• Ok but to clarify, Eric Wofsey's answer is correct? – Selene Auckland May 10 at 11:54
• @SeleneAuckland: The disagreement here isn’t a matter of correctness. The issue is that are several slightly different well-established definitions of “manifold” in the literature — no one has emerged as the consensus standard. This answer and Eric’s are making different arguments for which definition is best, which is a somewhat subjective question. In any case it seems clear that both notions — the notion where dimension can vary between components, and the notion where it must be globally fixed — both are natural and useful notions, whichever one you choose to call “manifold”. – Peter LeFanu Lumsdaine May 10 at 18:28
• @PeterLeFanuLumsdaine Thanks for replying. I meant to ask if "As written, the term "locally Euclidean" is in fact not even defined at all" is correct and if Def 5.1' and Def 5.2' are likely what was intended. In that case, that is what I mean by Eric Wofsey's answer's being correct. I'm not saying anything like one definition is better than another definition. Prof Tu is saying that we must allow dimensionless manifolds. My response is " 'Ok' (that definition is acceptable) 'but to clarify' are Eric Wofsey's observations and conjectures of intended definitions 'correct' " ? – Selene Auckland May 11 at 8:28
• I think Eric Wofsey's answer is absolutely correct. It is good to first define "locally Euclidean of dimension $n$" at a point. – Loring Tu May 21 at 21:42
• @LoringTu Thanks, Prof Tu! PS I think you need to tag people by using '@' to notify them. – Selene Auckland May 28 at 23:39

This is an addendum to Eric's answer. I checked a fair number of books on topology and differential geometry. All but one (Lang's "Differential Manifolds") define manifolds in such a way that all connected components of a manifold have the same dimension (i.e. they define $$n$$-dimensional manifolds rather than just "manifolds"). Lang's definition is meant to be as general as possible (for instance, he does not assume Hausdorfness): Lang defines manifolds modeled on arbitrary Banach vector spaces, so, in a way, it makes sense for him to allow for different local models.

Remark. I also checked Veblen and Whitehead "Foundations of differential geometry" (first published in 1932), which is the first place where manifolds were rigorously defined (using an atlas of charts with transition maps that belong to a given pseudogroup). However, given their archaic terminology, I find it hard to tell what they meant.

Here is the list of other books that I checked (most are widely regarded as standard references in geometry and topology):

• Kobayashi, Nomizu "Foundations of differential geometry".

• Klingenberg, Gromoll, Meyer, "Riemannische Geometrie im Grossen".

• Helgason, "Differential geometry, Lie groups and symmetric spaces".

• do Carmo, "Riemannian Geometry".

• Bishop and Crittenden, "Geometry of manifolds".

• de Rham, "Differentiable Manifolds".

• Milnor "Topology from the differentiable viewpoint".

• Guillemin and Pollack, "Differential Topology".

• Hirsch, "Differential Topology".

• Lee, "Differential manifolds".

• Lee, "Topological manifolds".

• Hatcher, "Algebraic Topology".

• Massey, "A basic course in algebraic topology".

• Eilenberg, Steenrod, "Foundations of Algebraic Topology".

• Munkres, "Topology".

I stopped at that point.

It is quite clear (say, by looking at this list) that the standard definition is to require a manifold to have constant dimension. Of course, an author is free to give a nonstandard definition, but a responsible thing to do in this case is to state clearly that the given definition is nonstandard. I disagree with Tu's sentiment that

We must allow a manifold to have connected components of different dimensions because such an object occurs naturally.

There are many things which occur naturally. For instance, quotient spaces of finite group actions on manifolds also occur naturally but nobody (as far as I know) calls them manifolds (instead, people call them V-manifolds, orbifolds, stacks...). In the example with the fixed-point set one can simply say that each connected component is a manifold.

• Kinda agree with "a responsible thing to do in this case is to state clearly that the given definition is nonstandard" or at least there is some responsibility here. As a beginner, I don't really care about the definition, but I really cared about the lack of 1. an explicit definition, 2. emphasis such as with... 3. ...examples of manifolds of non-uniform dimensions, in particular the inconsistency with Exercise 9.1, 4. statements of conventions like "From now on, 'manifold' means 'manifold with dimension' ". – Selene Auckland Aug 9 at 1:06
• "In the example with the fixed-point set one can simply say that each connected component is a manifold." Might we say the same about (some if not all) manifolds with boundary? I think one advantage of defining a manifold (without boundary) to have non-uniform dimension is to describe different unions of manifolds: A circle and an open disk could unite to a manifold with (non-empty) boundary, while a circle and a point could unite to a manifold with non-uniform dimension. – Selene Auckland Aug 9 at 1:09

format: plain


text:
[SOLVED] bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$

By Ataraxia

I understand that both $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are of the same cardinality by the Shroeder-Bernstein theorem, meaning there exists at least one bijection between them. But I can't figure out what such a bijection would be. The paper that I'm reading gives an example of an injective function $f:\mathbb{N}\to\mathbb{N}\times\mathbb{N}$, $f(n)=(0,n)$, and an injective function $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, $g(a,b)=2^a3^b$. I was thinking perhaps if there were some way to combine these two, I could find a bijection, but I have no idea how to go about that or if it's even possible.

What is an example of a bijection between these two sets, and please explain the process by which you found it?

@dtldarek 2013-07-15 19:50:41

The easiest bijection $\mathbb{N}\times\mathbb{N} \to \mathbb{N}$ I know is like this:

$$\color{red}{42},\color{blue}{2013} \to \color{blue}{2}\, \color{red}{0}\, \color{blue}{0}\, \color{red}{0}\, \color{blue}{1}\, \color{red}{4}\, \color{blue}{3}\, \color{red}{2}\,.$$

The above is for base 10, but it works for any base $b \geq 2$.

Edit: As there was some confusion, some alternative explanations:

1. To obtain the result, one starts writing digits from the right side in alternating fashion, and if one of the numbers has no more digits, we put zeros.
2. Let $\varepsilon$ be the empty string, then \begin{align} f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{a_ma_{m-1}\ldots a_2}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2b_1}) &= f(\color{red}{\varepsilon}, \color{blue}{b_nb_{n-1}\ldots b_2}) \color{blue}{b_1}\color{red}{0} \\ f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) &= f(\color{red}{a_ma_{m-1}\ldots a_2a_1}, \color{blue}{\varepsilon}) \color{blue}{0}\color{red}{a_1} \\ f(\color{red}{a_1}, \color{blue}{\varepsilon}) &= \color{blue}{\varepsilon}\color{red}{a_1} \\ f(\color{red}{\varepsilon}, \color{blue}{\varepsilon}) &= \varepsilon \end{align}
3. Let numbers be treated as polynomials in their base, i.e. $\mathbf{123}(z) = 1z^2+2z^1+3z^0$, then $$f(\color{red}{\mathbf{a}}, \color{blue}{\mathbf{b}})(z) = \color{red}{\mathbf{a}}(z^2) + z\color{blue}{\mathbf{b}}(z^2).$$

Some more examples for the first method: \begin{align} \color{red}{0},\color{blue}{50} &\to \color{blue}{5}\, \color{red}{0}\, \color{blue}{0}\, \color{red}{0}\,,\\ \color{red}{50},\color{blue}{0} &\to \color{red}{5}\, \color{blue}{0}\, \color{red}{0}. \end{align}

An example for the second method:

\begin{align} f(\color{red}{42},\color{blue}{2013}) &= f(\color{red}{4},\color{blue}{201}) \,\color{blue}{3}\,\color{red}{2}\, \\ &= f(\color{red}{\varepsilon},\color{blue}{20}) \,\color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= f(\color{red}{\varepsilon},\color{blue}{2}) \, \color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\,\\ &= f(\color{red}{\varepsilon},\color{blue}{\varepsilon}) \, \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= \varepsilon\, \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, \\ &= \color{blue}{2}\,\color{red}{0}\,\color{blue}{0}\,\color{red}{0}\, \color{blue}{1}\,\color{red}{4}\,\color{blue}{3}\,\color{red}{2}\, . \end{align}

Finally, an example for the third method:

\begin{align} \color{red}{\mathbf{a}}(x) &= \color{red}{4}x+\color{red}{2} \\ \color{blue}{\mathbf{b}}(y) &= \color{blue}{2}y^3+\color{blue}{0}y^2+\color{blue}{1}y^1+\color{blue}{3}y^0 \\ \color{red}{\mathbf{a}}(z^2) &= 4z^2+2 \\ \color{blue}{\mathbf{b}}(z^2) &= 2z^6+z^2+3 \\ f(\color{red}{\mathbf{a}}, \color{blue}{\mathbf{b}})(z) &= \color{red}{\mathbf{a}}(z^2)+z\color{blue}{\mathbf{b}}(z^2) \\ &= 2z^7+z^3+4z^2+3z+2 \\ &= \color{blue}{2}z^7+\color{red}{0}z^6+\color{blue}{0}z^5+\color{red}{0}z^4+\color{blue}{1}z^3+\color{red}{4}z^2+\color{blue}{3}z^1+\color{red}{2}z^0 \end{align}

I hope this helps ;-)

@Asaf Karagila 2013-07-15 19:54:05

Is $0,50$ sent to $500$ or $50,0$ sent to $500$?

@celtschk 2013-07-15 19:56:31

@AsafKaragila: $(\color{red}{0},\color{blue}{50})=(\color{red}{00},\color{blue}{50})$ is sent to $\color{blue}5\color{red}0\color{blue}0\color{red}0$. I would have defined the bijection the other way, though.

@dtldarek 2013-07-15 19:58:58

Thank you celtschk. You are right, maybe the other way would be more intuitive, but as long as we are consistent it does not matter.

@DonAntonio 2013-07-15 20:03:06

I'm still not sure I got this: so one has to complete by means of zeros on the left the ammount of digits every coordinate has? Say, $\;(234,1)=(234,001)\;$? And then you write the digits odds-even, like $\,(234,\color{blue}{001})\mapsto \color{blue} 02\color{blue}03\color{blue}14=20314\;$ ?

@Asaf Karagila 2013-07-15 20:06:20

@dtldarek: So how many $00000$'s do you want $0$ to actually be? What about $1,11$ and $11,1$? What about $111,1111$ and $1111,111$?

@Brian M. Scott 2013-07-15 20:13:46

@Asaf: I take it that $\langle1,11\rangle\mapsto1011$ and $\langle11,1\rangle\mapsto0111$.

@dtldarek 2013-07-15 20:15:47

@AsafKaragila Let's treat a number as a polynomial in $b$, its base, that is, $123 = 1b^2+2b^1+3b^0$. Then $f(n,m) = n(b^2)+bm(b^2)$.

@dtldarek 2013-07-15 20:20:58

@DonAntonio Yes. Alternative formulation would be: you write the digits odd-even, and when you run out, you put zeros.

@dtldarek 2013-07-15 20:23:02

@AsafKaragila As there was some confusion, I would appreciate any suggestions on how I could make the construction more easily digestible.

@DonAntonio 2013-07-15 20:24:13

@dtldarek, I don't get that: how many zeros do I have to put when "I run out" (what does this mean, anyway?)? One, two, thirty five...?

@dtldarek 2013-07-15 20:32:52

@DonAntonio When you represent a polynomial $P(x) = 2x^3+0x^2+1x^1+3x^0$ as a sequence $a_0=3, a_1=1, a_2=0, a_3=2$, how many zeros do you put? For example, $a_4 = ?$, $a_5 = ?$ It does not matter, because $P(x) + 0\cdot x^{35}$ is still $P(x)$. In fact $(a_n)$ might be infinite sequence, but with finite support. The zeros are only so that number does make sense (a blank is not a number).

@DonAntonio 2013-07-15 23:12:31

With a polynomial is very simple: you have one zero for every power of $\,x\,$ with zero coefficient. Period. Of course, you can also add zeros to the left with no consequence (but getting bored, perhaps). In this case, you said you begin writing digits odd-even until you run out...run out of what? And where do you add the zeros? I still think that the soudner thing to do here is to add as many zeros on the left of the shorter number as to have the same number of digints in both coordinates, and then odd-even...

@dtldarek 2013-07-16 05:36:24

@DonAntonio You start from the right side and go until you run out of digits, or in terms of polynomials, until you run out of non-zero coefficients. I add zeros to the left whenever the second number is still going, because otherwise it would create blanks (e.g. 2_0_1432 for 42, 2013). When both numbers are finished, of course, as in polynomials, you can add more zeros to the left, that is, $00345=345$, but there is no reason to do so.

@DonAntonio 2013-07-16 06:47:15

Now I think I got it, @dtldarek . Thanks.

@dtldarek 2013-07-16 06:48:41

@DonAntonio Great, now if you could tell me, how can I make my post more accessible?

@DonAntonio 2013-07-16 06:53:11

Well, just writing down explicitly how to form the map, exactly how you explained to me. For one, beginning with the "writing the digits from the right " would be great, as this is what made things clear. But I think it'd be clearer to tell what we talked about above" complete with zeros on the left one of the numbers so that both have the same No. of digits and etc.

@dtldarek 2013-07-19 10:22:42

@DonAntonio Thanks, I fixed what I could.

@Asaf Karagila 2013-07-19 10:26:56

Yeah, it's a nice map. Far from "easiest", as the many comments indicate, though. :-)

@dtldarek 2013-07-19 10:49:08

@AsafKaragila I guess it depends on who's looking ;-) For me it is instantaneous that it is a bijection, and what the inverse is (both easy to code, as in some programming language). While it is intuitive that Cantor's example is a bijection, its inverse is more hairy and (correct me if I am wrong) you need to rely on existential results if you want to do this "elegantly".

@Asaf Karagila 2013-07-19 22:07:36

Which is why I usually prefer $2^m(2n+1)-1$. Although in the context of recursive functions and whatnot, it's far more striking that the Cantor pairing function is $\Sigma^0_0$ as are its inverses. That's an important feature.

@dtldarek 2013-07-19 22:44:33

@AsafKaragila Neat, I haven't noticed that. This is why I like math.SE so much, even if you answer a way more than ask, there is still a lot one can learn ;-) Thanks!

@N. S. 2013-07-15 19:54:47

Assuming than $\mathbb N$ contains $0$, then

$$f(m,n)=2^m(2n+1)-1$$

is a bijection from $\mathbb N \times \mathbb N$ to $\mathbb N$.

The inverse $g: \mathbb N \to \mathbb N \times \mathbb N$ is simple: $g(n)=(a,b)$ where $a$ is the largest power of $2$ dividing $n+1$ and $2b+1$ is the largest odd number dividing $n+1$.

If you don't include $0$ in $\mathbb N$, all you need is replace $m,n$ by $m-1, n-1$.

@Asaf Karagila 2013-07-15 19:45:47

I found such bijection when I was a freshman. Cantor found it, but I don't know how he came to notice it.

$$(m,n)\mapsto\frac{(m+n)(m+n+1)}2+m$$

Another function, which is simpler to prove is a bijection is the following, I don't know who came up with that one.

$$(m,n)\mapsto 2^m(2n+1)-1$$

The idea is that every pair encodes a unique number by writing it as an even number times an odd number, and reducing $1$ so we can get $0$ as well.

@egreg 2013-07-15 20:00:09

Let's call $f$ the first function. If $m+n=k$, then $f(m,n)=k(k+1)/2 + m$. So $f(0,0)=0$, $f(0,1)=1$, $f(1,0)=2$; $f(0,2)=3$, $f(1,1)=4$, $f(2,0)=5$; and so on. So we're counting the points on the lattice going through the diagonals. And we're lucky, because the $k$-th diagonal contains exactly $k+1$ points.

[SOLVED] Explicit bijection between $[0,1)$ and $(0,1)$

• 2015-09-07 15:38:15
• Gabriel Romon
• 2465 View
• 3 Score


text:
# LEAST function in Oracle

LEAST is one of the vital Numeric/Math functions of Oracle. It is used to get the least value from a list of expressions. The LEAST function is supported in the various versions of the Oracle/PLSQL, including, Oracle 12c, Oracle 11g, Oracle 10g, Oracle 9i and Oracle 8i.

Syntax:

LEAST( expr_1, expr_2, ... expr_n )

Parameters:
expr_1, expr_2, … expr_n: It is used to specify the expression to be evaluated.

Example 1:

LEAST( 5, 6, 9, 10 )

Output:

5

Explanation:
The LEAST value is 5 in the above expression.

Example 2:

LEAST( ‘5’, ‘6’, ‘9’, ‘10’ )

Output:

 ‘10’

Explanation:
Since it is a character comparison, hence ‘10’ here is LEAST since it has a lower character set value.

Example 3:

LEAST( ‘ant’, ‘boy’, ‘elephant’, ‘zebra’ )

Output:

 ‘ant’

Explanation:
Since it is a character comparison, hence ‘ant’ here is LEAST since it has a lower character set value.

Example 3:

LEAST( ‘ant’, ‘any’, ‘ani’, ‘ana’ )

Output:

 ‘ana’

Explanation:
Since it is a character comparison, hence ‘ana’ here is LEAST since it has a lower character set value.


text:
# Homework Help: Find the Summation Notation and the Radius of Convergence

1. Jul 17, 2011

### Mastur

1. The problem statement, all variables and given/known data
Find the Summation Notation and Radius of Convergence of this series.

5, x, 10, x, ....

3. The attempt at a solution
I don't know how did they come up with that equation.. But the summation seems right.. Can anyone tell me how did they arrive with that equation? I've tried using the common ratio but I don't know what to do after having the ratio..

And for the radius of convergence, its L = lim (An+1)/(An) as n=> infinity..

Using the summation notation, I ended up infinityinfinity over infinityinfinity. I thought its equal to 1.. ~_~

Sorry, seems like the latex codes now isn't the same as the latex codes before. I don't know how to use the new latex codes..

#### Attached Files:

• ###### Untitled.png
File size:
991 bytes
Views:
91
Last edited: Jul 17, 2011
2. Jul 17, 2011

### HallsofIvy

If n is odd, $(-1)^n= -1$ and if n is even, $(-1)^n= 1$. That means that if n is odd $(1+ (-1)^n)/2= 0$ and if n is even, $(1+ (-1)^n)/2= 1$. Of course, if whether n is even or odd, n+ 1 is the opposite.

So for any odd n, $5^{(1+(-1)^n)/2}= 5^0= 1$ and $x^{(1+ (-1)^{n+1})/2}= x^1= x$ while for n even, $5^{(1+(-1)^n)/2}= 5^1= 5$ and $x^{(1+ (-1)^{n+1})/2}= x^0= 1$. That is, $5^{(1+(-1)^n)/2}x^{(1+(-1)^n)/2}$ just alternates 5 and x as your sequence does.

As for finding the "radius of convergence", it should be obvious that this is NOT a power series and so does not have a "radius of convergence".

(The LaTeX codes are the same as before- it just has picked up a bug so you need to click on your "refresh" button everytime you use LaTeX.)

3. Jul 17, 2011

### Mastur

I know that, no need to elaborate. I'm just wondering how can I come up with that equation if you only have the values "5, x, 10, x, ...." as a given.
Uhm, I don't get it. Why is this not a power series?


text:
# What is the exterior algebra of $\textbf{R}^2$

Let $V$ be an $n$-dimensional vector space.

The exterior algebra $\Lambda V$ of $V$ is the direct sum of the exterior powers $\Lambda^kV$. It comes with a product (called the exterior product) which is bilinear, alternating and anticommutative. The dimension of $\Lambda V$ is $2^n$.

(For physics buffs, the exterior algebra is an example of a supersymmetric and supercommutative algebra.)

The exterior algebra is a geometric algebra with trivial quadratic form (I think). It is a quotient of the tensor algebra of $V$ (by the two-sided ideal generated by set $\{v \otimes v\ |\ v\in V\}$).

The exterior algebra $\Lambda\textbf{R}^1$ of $\textbf{R}^1$ is isomorphic to the dual numbers.

What is the exterior algebra $\Lambda\textbf{R}^2$ of $\textbf{R}^2$ (as in, through which isomorphic objects can I understand it, specially for the purpose of doing explicit computations)? Is it related to $\Lambda\textbf{C}$? Does it admit a matrix representation, like $\Lambda\textbf{R}^1$?

(If this question is too low-powered please do migrate it / close it.)

## migrated from mathoverflow.netJul 6 '17 at 19:01

This question came from our site for professional mathematicians.

• Exterior algebras always admit a matrix representation. After choosing a basis of $V$, you derive from it a basis for $\Lambda V$ (which is a $2^n$ dimensional vector space). Since $\Lambda V$ acts on $\Lambda V$ by left multiplication, there is a copy of $\Lambda V$ sitting in the algebra of linear maps $\mathcal{L}(\Lambda V, \Lambda V)$, which in your bases can be identified with the set of $2^n \times 2^n$ dimensional matrices. For example, for $V = \mathbf{R}^2$, you can let your basis of $\Lambda V$ be $\{1, dx, dy, dx\wedge dy\}$. Then the corresponding matrix operations are: – Willie Wong Jul 6 '17 at 17:54
• \begin{align} 1 &\implies \begin{pmatrix} 1 \\ & 1 \\ & & 1 \\ & & & 1\end{pmatrix} \\ dx &\implies \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \\ dy & \implies \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 & -1 & 0 & 0\end{pmatrix} \\ dx \wedge dy & \implies \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 & 0 & 0 & 0\end{pmatrix} \end{align} with all omitted entries being 0. – Willie Wong Jul 6 '17 at 17:59
• It is a finite dimensional local selfinjective algebra and thus a quiver algebra. It is an easy excerse to write down quiver and relations (which is imo much better than as a matrix algebra). This is for example an excerse in the book by auslander reiten smalo. Having the algebra as a quiver algebra, one can for example easily answer when it is symmetric algebra. I dont know when it is a Hopf algebra. – Mare Jul 6 '17 at 18:10
• @Mare: it is always a Hopf algebra. – M.G. Jul 6 '17 at 18:48
• @July: It is a Hopf algebra in the category of super-vector spaces. But it is not generally a Hopf algebra "on the nose" (i.e., without the Koszul sign). For example, the exterior algebra of a $1$-dimensional vector space over a field $k$ is isomorphic to $k\left[x\right]/\left(x^2\right)$, which has no bialgebra structure unless $k$ has characteristic $2$. – darij grinberg Jul 6 '17 at 21:30

The exterior algebra $\Lambda \mathbb{R}^2$ is a real vector space of dimension 4 with basis $1, e_1, e_2, e_1 \wedge e_2$. So its every element is a unique linear combination of these basis elements, say $a_1 \cdot 1 + a_2 e_1 + a_3 e_2 + a_4 e_1 \wedge e_2$, for real numbers $a_1, a_2, a_3, a_4$, which can be chosen arbitrarily. The multiplication operation is written $\wedge$, is associative and has $1$ as identity, and has $e_1 \wedge e_1 = 0$ and $e_2 \wedge e_2=0$, $e_1 \wedge e_2$ is the basis element by that name, and $e_2 \wedge e_1=-e_1 \wedge e_2$. That gives you the complete multiplication table, by associativity. Please comment if this answer is not sufficient.
• You mean the exterior algebra $\Lambda\mathbb{R}^2$ (if you only take the second exterior power, you won't get an algebra). Also, you need to specify that $e_2\wedge e_1 = -(e_1\wedge e_2)$ to complete the multiplication table. – Tobias Kildetoft Jul 7 '17 at 13:16
• Is $\Lambda \textbf{R}^2$ isomorphic to any object one may encounter in elementary math? (Like $\Lambda \textbf{R}^2$ is isomorphic to the dual numbers, which form a unital commutative associative algebra.) What are some other properties of $\Lambda \textbf{R}^2$, as an algebra? – étale-cohomology Jul 24 '17 at 11:58
• @étale-cohomology: No, it is not isomorphic to the dual numbers. They have dimension 2. It has dimension 4. The even part of $\Lambda \mathbb{R}^2$ is the dual numbers: $\Lambda^0 \mathbb{R}^2 \oplus \Lambda^2 \mathbb{R}^2$. The algebra $\Lambda \mathbb{R}^2$ is not commutative, but is extremely close to being commutative (called "super-commutative"), since it splits (as vector space) into the direct sum of its even part, a commutative algebra, and then its odd part, $\Lambda^1 \mathbb{R}^2$, with commutativity of anything even and anything, but anti-commutativity of any two odd things. – Ben McKay Jul 24 '17 at 16:37
• Thanks for the answer! And I meant that $\Lambda \textbf{R}^1$ is isomorphic to the dual numbers. – étale-cohomology Jul 25 '17 at 17:03


text:
# OrdinalNumber

An ordinal (or ordinal number) may be defined in terms of surreal numbers as a (surreal) number of the form {L|} (ONAG (2001) p.79). The first infinite ordinal is omega = {0,1,2,3,cdots|} — and there are many, many more after that!

Ordinal numbers in general appear not to be of much importance in CGT as applied to go, so we need say little more here and now.

OrdinalNumber last edited by PJTraill on January 21, 2019 - 20:48


text:
# Punchscan

Developer(s) Richard Carback, David Chaum, Jeremy Clark, Aleks Essex, and Stefan Popoveniuc. 1.0 (November 2, 2006) [±] 1.5 (July 16, 2007) [±] Java Cross-platform English vote counting system Revised BSD license http://punchscan.org/

Punchscan is an optical scan vote counting system invented by cryptographer David Chaum. Punchscan is designed to offer integrity, privacy, and transparency. The system is voter-verifiable, provides an end-to-end (E2E) audit mechanism, and issues a ballot receipt to each voter. The system won grand prize at the 2007 University Voting Systems Competition.

The computer software which Punchscan incorporates is open source; the source code was released on 2 November 2006 under a revised BSD licence.[1] However, Punchscan is software independent; it draws its security from cryptographic functions instead of relying on software security like DRE voting machines. For this reason, Punchscan can be run on closed source operating systems, like Microsoft Windows, and still maintain unconditional integrity.

The Punchscan team, with additional contributors, has since developed Scantegrity.

## Voting procedure

A marked Punchscan ballot. Full ballot (top), separated ballot (bottom).

A Punchscan ballot has two layers of paper. On the top layer, the candidates are listed with a symbol or letter beside their name. Below the candidate list, there are a series of round holes in the top layer of the ballot. Inside the holes on the bottom layer, the corresponding symbols are printed.

To cast a vote for a candidate, the voter must locate the hole with the symbol corresponding to the symbol beside the candidate's name. This hole is marked with a Bingo-style ink dauber, which is purposely larger than the hole. The voter then separates the ballot, chooses either the top or the bottom layer to keep as a receipt, and shreds the other layer. The receipt is scanned at the polling station for tabulation.

The order of the symbols beside the candidate names is generated pseudo-randomly for each ballot, and thus differs from ballot to ballot. Likewise for the order of the symbols in the holes. For this reason, the receipt does not contain enough information to determine which candidate the vote was cast for. If the top layer is kept, the order of the symbols through the holes is unknown. If the bottom layer is kept, the order of the symbols beside the candidates name is unknown. Therefore the voter cannot prove to someone else how they voted, which prevents vote buying or voter intimidation.

## Tabulation procedure

As an example, consider a two candidate election between Coke and Pepsi, as illustrated in the preceding diagram. The order of the letters beside the candidates' names could be A and then B, or B and then A. We will call this ordering $P_1$, and let $P_1$=0 for the former ordering and $P_1$=1 for the latter. Therefore,

$P_1$: order of symbols beside candidate list,

$P_1\in\{0,1\}=\{\mbox{AB},\mbox{BA}\}\,$.

Likewise we can generalize for other parts of a ballot:

$P_2$: order of symbols through the holes,

$P_2\in\{0,1\}=\{\mbox{AB},\mbox{BA}\}\,$.

$P_3$: which hole is marked,

$P_3\in\{0,1\}=\{\mbox{1st},\mbox{2nd}\}\,$.

$R$: result of the ballot,

$R\in\{0,1\}=\{\mbox{Coke},\mbox{Pepsi}\}\,$.

Note that the order of the candidates' names are fixed across all ballots. The result of a ballot can be calculated directly as,

$R = P_1 + P_2 + P_3\bmod 2\,$ (Equation 1)

However when one layer of the ballot is shredded, either $P_1$ or $P_2$ is destroyed. Therefore there is insufficient information to calculate $R$ from the receipt (which is scanned). In order to calculate the election results, an electronic database is used.

Before the election, the database is created with a series of columns as such. Each row in the database represents a ballot, and the order that the ballots are stored in the database is shuffled (using a cryptographic key that each candidate can contribute to). The first column, $D_1$, has the shuffled order of the serial numbers. $D_2$ contains a pseudorandom bitstream generated from the key, and it will act as a stream cipher. $D_3$ will store an intermediate result. $D_4$ contains a bit such that:

$D_2 + D_4 = P_1 + P_2 \bmod 2\,$

The result of each ballot will be stored in a separate column, $R$, where the order of the ballots will be reshuffled again. Thus $D_5$ contains the row number in the $R$ column where the result will be placed.

After the election is run and the $P_3$ values have been scanned in, $D_3$ is calculated as:

$D_3 = P_3 + D_2 \bmod 2\,$

And the result is calculated as,

$R = D_3 + D_4 \bmod 2\,$

This is equivalent to equation 1,

\begin{align} R &= (D_3) + D_4 \bmod 2\\ &= (P_3 + D_2) + D_4 \bmod 2\\ &= P_3 + (D_2 + D_4) \bmod 2\\ &= P_3 + (P_1 + P_2) \bmod 2 \end{align}

The result column is published and given the ballots have been shuffled (twice), the order of the results column does not indicate which result is from which ballot number. Thus the election authority cannot trace votes to serial numbers.

### Generalized form

For an election with $n$ candidates, the above procedure is followed using modulo-n equations.

## Basic auditing procedures

The voter's ballot receipt does not indicate which candidate the voter cast their ballot for, and therefore it is not secret information. After an election, the election authority will post an image of each receipt online. The voter can look up her ballot by typing in the serial number and she can check that information held by the election authority matches her ballot. This way, the voter can be confident that her ballot was cast as intended.

Any voter or interested party can also inspect part of the database to ensure the results were calculated correctly. They cannot inspect the whole database, otherwise they could link votes to ballot serial numbers. However, half of the database can be safely inspected without breaking privacy. A random choice is made between opening $\{D_1,D_2,D_3\}$ or $\{D_3,D_4,D_5\}$ (this choice can be derived from the secret key or from a true random source, such as dice[2] or the stock market[3]). This procedure allows the voter to be confident that the set of all ballots were counted as cast.

If all ballots are counted as cast and cast as intended, then all ballots are counted as intended. Therefore the integrity of the election can be proven to a very high probability.

To further increase the integrity of a Punchscan election, several further steps can be taken to protect against a completely corrupt election authority.

### Multiple databases

Since $D_1$, $D_2$, and $D_5$ in the database are all generated pseudorandomly, multiple databases can be created with different random values for these columns. Each database is independent of the others, allowing the first half of some of the databases to be opened and inspected and the second half of others. Each database must produce the same final tally. Thus if an election authority were to tamper with the database to skew the final tally, they would have to tamper with each of the databases. The probability of the tampering being uncovered in the audit increases exponentially with the number of independent databases. With even a modest number of databases, the integrity of the election is probabilistically certain.

### Commitments

Prior to an election, the election authority prints the ballots and creates the database(s). Part of this creation process involves committing to the unique information contained on each ballot and in the databases. This is accomplished by applying a cryptographic one-way function to the information. Though the result of this function, the commitment, is made public, the actual information being committed to remains sealed. Because the function is one-way, it is computationally infeasible to determine the information on the sealed ballot given only its publicly posted commitment.

### Ballot inspection

Prior to an election, twice as many ballots are produced as the number intended to use in the election. Half of these ballots are selected randomly (or each candidate could choose a fraction of the ballots) and opened. The rows in the database corresponding to these selected ballots can be checked to ensure the calculations are correct and not tampered with. Since the election authority does not know a priori which ballots will be selected, passing this audit means the database is well formed with a very high probability. Furthermore, the ballots can be checked against their commitments to ensure with high probability that the ballot commitments are correct.


text:
September 29: Sunil Simon: Structured specification of strategies in games on graphs
16.00--17.00
Abstract:
In much of game theory, strategies (which are the core of game playing) are mostly treated as being atomic (unstructured). While this is adequate for reasoning "from above", where one is interested in the logical structure of the game itself, or that of removing dominated strategies, or existence of equilibria, it offers little help for how to play. When it comes to reasoning within the game, a player's choice of strategy depends not only on her knowledge of the game position but also her expectation of the strategies employed by other players of which she can only have partial knowledge. Moreover, strategies are completely known to players only in small games where a strategy amounts to picking a small number of moves; in games with rich structure, intricate reasoning about strategies can be called for. We discuss examples of strategies as they arise, say in Axelrod tournaments, their logical formalization, and some decidability results.

This is joint work with R. Ramanujam (IMSc., Chennai)

To main page

October 5: Shingo Saito: Knot points of typical continuous functions
16.00--17.00
Abstract:
Let $C([0,1])$ denote the Banach space of all real-valued continuous functions defined on the unit interval $[0,1]$. We say that a typical function $f\in C([0,1])$ has a property P if the set of all f with the property P is residual, i.e. contains a countable intersection of open dense sets. It is well known that a typical function $f\in C([0,1])$ is nowhere differentiable. Moreover, it turns out that a typical function $f\in C([0,1])$ has the property that at almost every point in $[0,1]$ the function f is the least differentiable from the viewpoint of Dini derivatives; such a point is called a knot point and the set of all knot points is denoted by K(f).

In this talk, we give a complete characterisation for a family S of subsets of $[0,1]$ to have the property that $K(f)\in S$ for a typical function $f\in C([0,1])$. The proof exploits the Banach-Mazur game and some results in descriptive set theory.

I will try to make the talk accessible to as many people as possible, so that people who know first-year analysis' and the rudiments of topological spaces will be able to understand the statement of the main theorem.
To main page

October 12: Valery Plisko: Primitive recursive realizabilities
16.00--17.00
Abstract:
The notions of primitive recursive realizability introduced by Z.Damnjanovics (1994) and S.Salehi (2000) are considered. The main results:
1) these two notions are essentially different;
2) intuitionistic predicate logic is not correct relative to the Damnjanovics realizability.
To main page

November 2: Denis Bonnay: Invariance, Definability and Monoids
16.00--17.00
Abstract:
I will present a generalization of an (old) result by Marc Krasner on definability in infinitary logic and groups of automorphisms. Krasner showed that, given a set M, there is a one-one correspondence between sets of operations on M which are closed under definability in $L_{\infty,\infty}$ and groups of permutations on M. Independently, Solomon Feferman recently asked in which logical language operations invariants under strong homomorphisms were definable (I will define precisely what a strong homomorphism is). I will show that Feferman's question can be answered by generalizing Krasner's theorem, so as to get a one-one correspondence between sets of operations closed under definability in $L_{\infty,\infty}$ without equality and monoids of homomorphisms.
To main page

November 16: Tatiana Yavorskaya: Interacting explicit evidence systems
16.00--17.00
Abstract:
The logic of proofs LP, introduced by S. Artemov, originally designed for describing properties of formal proofs, became a basis for the theory of knowledge with justification (an agent knows F for the reason t). So far, in epistemic systems with justification the corresponding evidence part, even for multi-agent systems, consisted of a single explicit evidence logic.
In this talk I will speak about logics describing two interacting explicit evidence systems. These results are contained in:
Tatiana Yavorskaya (Sidon), Multi-agent Explicit Knowledge, Lecture Notes in Computer Science 3967 (2006), pp. 369-380.
To main page

November 23: Valentin Shehtman: More on completeness in first-order modal and intuitionistic logic
16.00--17.00
Abstract:
This is a continuation of the talk at this seminar in 2006. The situation in this field is quite complicated, because many simply formulated logics are incomplete in standard semantics. We shall recall the main definitions of Kripke-type and algebraic-type semantics and then concentrate on the recent advance in their investigation.
To main page

November 30: Sonja Smets: An Abstract Dynamic-Logical Setting for Quantum Mechanics
16.00--17.00
Abstract:
I present two (equivalent) abstract qualitative axiomatic settings for a dynamic logic of quantum actions: one in terms of Quantum Transition Systems, and the other in terms of Quantum Dynamic Algebras. I give a Representation Theorem showing that these axiomatizations are complete with respect to the concrete semantics given by (infinite-dimensional) Hilbert spaces. This means that they capture all the essential features of Quantum Mechanics. The proof uses known Representation results for standard quantum logic, due to Soler, Mayet and others.
However, I argue that the dynamic-logic setting gives a new view of quantum structures in terms of their underlying logical dynamics. This setting has a number of important advantages: 1) it provides a clear and intuitive dynamic-operational meaning to the usual quantum logic connectives (e.g. quantum negation, quantum implication etc) and to key quantum-logic postulates (e.g. Orthomodularity, Covering Law); 2) it reduces the complexity of the Soler-Mayet axiomatization by replacing key higher-order concepts (e.g. "automorphisms of the ortholattice") by first-order objects ("actions"); 3) it provides a link between traditional quantum logic and the needs of quantum computation.
This talk is based on my joint work with A. Baltag.
To main page

January 11: Ali Enayat: Nonstandard Omega-standard Models of Finite Set Theory
10.00--11.00
Abstract:
Finite set theory, here denoted FST, is the theory obtained by replacing the axiom of infinity by its negation in the usual axiomatization of Zermelo-Fraenkel set theory. An omega -model of FST is a model in which every set has at most finitely many elements (as viewed externally). Mancini and Zambella (2001) employed the Rieger-Bernays method of permutations to construct a recursive omega-model of ZF that is nonstandard ( i.e., not isomorphic to the hereditarily finite sets ). In this talk we focus on the metamathematical investigation of omega-model of FST. In particular, we (a) present a perspicuous construction of a recursive nonstandard omega-model of FST without the use of permutations; (b) use forcing to show that for each cardinal kappa between aleph_0 and the continuum (inclusive) there are 2^kappa nonisomorphic omega-models of FST of cardinality kappa; and (c) establish a completeness theorem for uncountable models by showing that there is a scheme S in the usual language of set theory such that the omega -models of FST + S are precisely those that are elementarily equivalent to an uncountable omega-model of FST.
This is joint work with Albert Visser.
To main page

February 15: Samson Abramsky: Full Completeness
16.00--17.00
Abstract:
Full Completeness results aim to characterize the space of proofs' of a logical system, as a mathematical structure in its own right. Two styles of such characterization have been prominent: geometric, closely aligned with giving a diagrammatic notion of proof (e.g. proof-nets); and interactive, aligned with game semantics and geometry of interaction'. One then seeks to show that the two kinds of characterization coincide. There are also interesting connections with various notions of uniformity', such as (di)naturality, or invariance under logical relations.
We shall give an introduction to these ideas, and describe full completeness results for the multiplicative and multiplicative- additive fragments of linear logic.
To main page

February 22: Dag Westerstahl: Quantifiers, Freezing, Possessives, and Compositionality
16.00--17.00
Abstract:
Noun phrases in general denote type (1) (generalized) quantifiers (sets of sets). These are often, but not always, obtained from type (1,1) quantifiers (binary relations between sets) by freezing the first argument: the restriction. I discuss some questions related to decomposability (expressibility as frozen type (1,1) quantifiers) of type (1) quantifiers. Answers to these questions are relevant to certain semantic issues, notably the semantics of possessives. In particular, they point to a problem for the compositionality of possessive constructions.
To main page

March 28: Michael Rathjen: "Models" for intuitionistic set theories
14.00--15.00
Abstract:
There are central questions that have shaped the research activities in classical Cantorian set theory over the last 120 years.
Roughly speaking, these are questions addressing the independence of set-theoretic principles (e.g. via Gödel's L and forcing), the role of large set axioms, and the impact of the set-theoretic universe at large on the lower levels of the cumulative hierarchy (e.g. the real line).
Similar questions can be asked for set theories were the underlying logic is intuitionistic rather than classical. There is a widespread impression that the prize for relinquishing classical logic is high. However, the loss of certain comforting theorems of classical mathematics can also bring forth profits. Intuitionistic logic allows for axiomatic freedom in that one can adopt new axioms that are true in certain models (e.g. realizability models) but outrageously false classically.
The talk will survey some model constructions for intuitionistic set theories with an eye towards determining the proof-theoretic strengths of various systems.
To main page

April 4: Michiel van Lambalgen: Lawlessness, randomness and the axiom of choice
16.00--17.00
Abstract:
In the early 20th century two mathematicians coming from very different backgrounds proposed to allow infinite but incomplete objects in mathematics.
L.E.J. Brouwer allowed free choice sequences', sequences of natural numbers which are constructed by freely choosing the next item in the sequence; and he proposed reasoning principles governing these objects. These principles entail that classical logic does not hold for freely chosen sequences.
The mathematician R. von Mises introduced very similar objects for a very different purpose: the foundations of probability. He claimed that a frequency interpretation of probability required so called random sequences', an intuitive model of which is provided by the sequence of outcomes of tosses of a coin, and hwich von Mises thought were related to choice sequences.
Von Mises gave axioms for this notion and proceeded to develop probability theory on this basis. The axioms were soon criticised as being inconsistent, and von Mises' foundation for probability theory was abandoned in favour of Kolmogorov's axiomatisation in terms of measure theory.
However, it is possible to reformulate von Mises' axioms consistently as expressing the determinacy of a game, in which player I attempts to generate a random infinite binary sequence x and player II attempts to select an infinite subsequence of x whose statistical properties are different from x. Consistency of this form of determinacy is proven via a forcing argument; the earlier suspicion that the setup is inconsistent is actually due to inconsistency with the axiom of choice. Von Mises' observation that random sequences are related to choice sequences turns out to be correct, via an application of the double negation translation.
To main page

April 18: Patrick Dehornoy: RECENT PROGRESS ON THE CONTINUUM HYPOTHESIS, AFTER H.WOODIN
16.00--17.00
Abstract:
The recent work of H. Woodin significantly renewed Set Theory by restoring its global unity and making it more understandable. For the first time, there exists a reasonable hope of solving the Continuum Problem, and it is very interesting to discuss what this means in view of the classical undecidability results by Gödel and Cohen. At the very least, the results by Woodin show that the Continuum Problem is not just a meaningless scholastic question.
To main page

May 23: Mirna Dzamonja: Combinatorics of trees
16.00--17.00
Abstract:
We are interested in trees of size $\kappa$ with no $\kappa$ branches, and especially in their behaviour under the notion of tree embedding. A tree embedding is function between trees which preserves the strict tree order. This type of research has a long history, especially when $\kappa=\aleph_1$. We shall review some of the known results and then show some newer results with Väänänen in which we study the situation when $\kappa$ is singular of countable cofinality. At the end we shall show some of the insights we obtained with Thompson on the problem of finding a tree of size $\aleph_1$ with no uncountable branches into which all such trees tree-embed.
To main page

May 29: Sakaé Fuchino: Axiomatization of generic extensions by homogeneous partial orderings
16.00--17.00
Abstract:
In this talk we review some results on combinatorial principles introduced in [1] and [3]. These principles hold in the models of ZFC obtained e.g. as the generic extension of a ground model of CH by a ccc partial ordering which is a finite product of the copies of a partial ordering which is small enough compared to the size of the index set of the product. The principles seem to capture many properties of the generic extensions by partial orderings as above and thus can be seen as axiomatization of (some/many features of) such generic extensions.
The (measure theoretic) side by side'' product of (copies of) random algebra also has the homogeneity similar to the partial orderings as above in the sense that a bijection on the support of the product induces an automorphism of the partial ordering. Nevertheless, by a result of Kunen, we can show that the principles introduced in [1] do not hold in the generic extension by side by side product of random algebra (the random model). In contrast, the Fremlin-Miller Covering Property in [2] and its generalization considered in [3] can be shown to hold in a random model for adding more than aleph 3 random reals over a model of CH.

[1] Jörg Brendle and Sakaé Fuchino: Coloring ordinals by reals, Fundamenta Mathematicae, 196, No.2 (2007), 151-195.
[2] Arnold Miller, Infinite Combinatorics and Definability, Annals of Pure and Applied Logic, 41 (1989), 179-203.
[3] Sakaé Fuchino: A generalization of a problem of Fremlin, RIMS Kôkyûroku, No.1595 (2008), 6-13.
To main page

May 30: Kohei Kishida: Topological Completeness of First-Order Modal Logic
14.45--15.45
Abstract:
As McKinsey and Tarski [1] showed, the Stone representation theorem for Boolean algebras extends to algebras with operators (topo-Boolean algebras). This result gives topological semantics for (classical) propositional modal logic, in which the necessity'' operation is modeled by taking the interior of an arbitrary subset of a topological space. The topological interpretation was extended by Awodey and Kishida [2] in a natural way to full first-order logic (i.e., with function and constant symbols). This paper proves the resulting system of first-order S4 modal logic to be complete with respect to such topological semantics.
Joint work with Steve Awodey.

[1] J. C. C. McKinsey and A. Tarski, The Algebra of Topology,'' Annals of Mathematics 45 (1944), 141-91.
[2] S. Awodey and K. Kishida, Topology and Modality: The Topological Interpretation of First-Order Modal Logic,'' forthcoming in Review of Symbolic Logic.

To main page

June 13: Bart Kastermans: Stability and Posets
14.45--15.45
Abstract:
I'll talk about a paper (with Jockusch, Lempp, Lerman, and Solomon) about reverse math and recursion theoretic results related to the principle CAC: every infinite poset has an infinite chain or an infinite antichain.
To main page

To main page


text:
# All Questions

262 views

### Can a neutrino act as a virtual particle between two electrons to mediate an electron-electron fermonic interaction?

Can a neutrino act as a virtual particle between two electrons to mediate electron-electron fermonic interaction analogous to how a photon acts as a virtual particle between two electrons to mediate a ...
77 views

### Attraction & Lorentz force, at the same time?

If a conductor carrying current is placed inside a magnetic field, we know that there is the Lorentz force pushing the wire. But what about the attraction force between the wire's field and the magnet/...
257 views

### help with absolute pressure to gauge pressure derivation steps

I would like some help with the explicit math steps to go from equation 2 to 3. These equations are presented in a paper that I am reading. I will show where these equations came from and my attempt ...
533 views

### When Fire meets Water

To preface, I am not a scientific mind, but a writer looking for some validity to a possible scene. That being said, please forgive me! In my scene, huge masses of fire are raining from the sky and ...
292 views

### How powerful would an explosion have to be for its effects to be felt worldwide?

If an explosion were to occur at any point on earth, how powerful would that explosion have to be for it to be audible or otherwise detectable by every person on the planet? Detection could mean ...
134 views

### Lagrangian Systems

Given a manifold $M$, Arnold's "Mathematical Methods of Classical Mechanics" defines a Lagrangian system as a pair $(M,L)$ where $L$ is some smooth function on the tangent bundle $TM$. The function $L$...
526 views

### Has anyone developed tunable notch filters in the visible RGB wavelengths which have very fast response times?

I am interested in whether the combination of a spectrometer and a tunable notch filter with notch frequencies at the visible red, green and blue wavelengths which have very fast response times could ...
285 views

### What algorithms can be used to compute the binodal in a ternary Flory-Huggins theory?

What are the most popular algorithms used to obtain a binodal curve for the ternary mixture (starting from Flory-Huggins theory)? I would like to obtain a plot similar to the one calculated here http:...
111 views

### Electromagnetic waves and boundaries

I am reading about dielectric boundaries and electromagnetic plane waves following griffiths ch7. When considering a boundary at z=0 with electric fields perpendicular to the plane of incidence it ...
367 views

### Quantum symmetries that are not classical symmetries

An anomaly is a symmetry of the classical action that fails to be a symmetry of the path integral, due to non-invariance of the path integral measure. Does it ever occur that the opposite thing ...
498 views

### How does angular momentum transfer between a planet and its moon?

Could you explain how a moon draws angular momentum from a planet? I know that the gravitational force transfers momentum, but I don't understand the mechanics behind it.
331 views

### Proof of Connected Diagrams

If $Z[J]$ is the generating functional for the path-integral, could any prove (or more reasonably, refer me to a proof) that $$W[J]\equiv\frac{\hbar}{i}\log\left(Z[J]\right)$$ "generates" only ...
107 views

### Is Gravitational Red shift equal to $mgh$

Is gravitational shift - $\frac{gh}{c^2}$ (according to pound-rebka experiment) always equal to $PE=mgh$? because assume the gravitational pull, $g$, is equal to $1$ then we can say $g = 1$ similarly ...
199 views

### How did the universe get so big so fast? [duplicate]

The universe started at the big bang around 15 billion years ago. The universe is now at least 92 billion light-years in diameter. Together, don't these mean that the universe, at some time in the ...
60 views

### How can momentum changes from individual collisions be considered as a whole?

I have a question about deriving the equation of kinetic theory of ideal gas $$PV=\frac{1}{3} Nmc_r^2$$ where $N$ is number of atoms, $c_r$ is root mean square of atom speed and $m$ is mass of one ...
301 views

58 views

### Is this “cloaking in time” serious and what is really meant?

I just found this news article: http://www.nature.com/nature/journal/v481/n7379/full/nature10695.html What did those researchers actually do? The article itself doesn't sound to me like it can be ...
28 views

### Optics - Derivation of Linear Magnification of Lens without Sign Convention [duplicate]

In some posts in this forum I've read that sign convention in optics is useful for making formula memorizing easier, and that we have to use sign convention again while applying the formulae to ...
89 views

### Maximum density that we can store information

I was informed that: There is a maximum density at which we can store information. For a sphere with surface area A, the maximum information that can be contained within is equivalent to the ...
31 views

### Is gravitational acceleration less affected by relativistic mass increase? [duplicate]

Acceleration due to mechanical force will lessen due to relativistic mass increase as kinetic energy becomes significant near c. But if acceleration is gravitational, the gain in relativistic mass ...
998 views

### Do we hear sounds differently on the highest mountains?

Some searching gives that above 6,000 meter altitude the air density is less than half of that at sea level. Speed of sound is about 15-20% slower and "acoustic impedance" seems to change too. Do ...
207 views

### Why does absorption cause seismic pulses to increase in length over distance?

The specific question I'm trying to answer is "How does the progressive loss of higher frequencies in a propagating seismic pulse lead to an increase in pulse length?" I understand how the higher ...
53 views

### Gravitational lens to illuminate a planet?

I've been involved in a Internet debate: Is it possible to have a special cosmic configuration consisted of multiple bodies such that a planet's surface can be lit up by light focused by ...
72 views

### How should two particles accelerate to have their separation Lorentz-contract?

Suppose we have two particles with initial separation of $|x_2^\text{init}-x_1^\text{init}|=d$. At time $t=0$ they start accelerating with proper acceleration of $w$. Then position of the $i$th ...
186 views

### Could the singularity that gave rise to our universe be past-eternal?

Are there any compelling models that include a past eternal singularity that ultimately gave rise to our universe? Does the "no-boundary" hypothesis that utilizes imaginary time have past eternal ...
50 views

### Long string model of black hole

I wonder if anyone can advise me literature about "long string model" of black hole. I've tried Google, and of course arXiv.org. Still I couldn't find anything about this theme. I would be also very ...
3k views

### What is the difference between negative acceleration and decreasing acceleration?

According to Reisnick and Halliday, retardation is the acceleration in the negative direction of time axis ie. opposite to the motion. Decreasing accleretion is the decrease in the magnitude of time ...
104 views

### What is the linear and rotational motions generated by a force not on the CG?

Given a force that is applied to a free body, not directly towards, or away from the centre of gravity, how would you calculate the amount of linear and rotational velocities generated, as the farther ...
506 views

### If virtual particles have negative mass why do they contribute positive mass to atoms?

According to Lawrence Krauss, atoms containing in our body consists of merely 10% (if I remember correctly) of our total mass. The rest come from virtual particles popping in and out of existence from ...
147 views

### Reflection from multiple thin films: accounting for lost light due to small surface area

I have a problem similar to reflection of multiple thin films. I have light coming in from medium 1 and I want to find the total reflected intensity after being reflected inside 2 layers. However, I ...
399 views

### Is it possible to design a large permanent magnet that creates a multi-Tesla field?

Is it ever possible to create a LARGE magnet (in meters wide/long) that could potentially create a powerful magnetic field?
18k views

### Supersymmetry vs multiverse

I'm a complete noobe in physics and quite honestly need help. My question is simple, based on CERN's tentative findings stating the Higgs boson at a mass of ~125 GeV: Is the physics community leaning ...
177 views

### How can I actually use the BB84 protocol?

I have read how the BB84 protocol could work. However, I couldn't see a way to implement it in the laboratory, so that I could make a demonstration in the university's quantum optics laboratory. ...
1k views

### Efficiency of reversible engines

I'm a little confused about something. All reversible engines have the same efficiency, or one could drive the other to move more heat in the reverse direction. Also, no engine has an efficiency ...
559 views

### Suggested reading for classical field theory [duplicate]

I am reading a marvelous book Classical Field Theory by E Soper, but it is mathematically too compact and sometimes I am unable to follow the equations. Can anyone suggest a side book for solution of ...
177 views

### How to define the thermodynamic temperature

I've been reading derivations of the thermodynamic temperature scale. I'm assuming these are using Kelvin's method. I follow the math and the conclusion of the argument, but I don't understand how it ...
40 views

### Canonical transformation that contains the time as an explicit parameter

On the Page 385 of Goldstein's Classical Mechanics book (third edition), it starts to talk a bout the canonical transformation with time as an explicit parameter. But I don't quite under understand ...