Search Results

Freiling's axiom of symmetry states that if you assign to each real number $x$ a countable set $A_x\subset\mathbb{R}$, then there should be two reals $x,y$ for which $x\notin A_y$ and $y\notin A_x$. …

The properties are not equivalent. Let $S$ consist of (at least two) subsets of $X$, which have one point entirely in common, but which are otherwise disjoint (and which have other points than that co …

It's a great problem! Theorem. The mathematicians have a winning strategy in the game for every ordinal $\alpha$. Proof. Let's prove the theorem by transfinite induction. Suppose that the mathematic …

In order to make some concrete progress, let me make a definite upper bound, based on the idea of my earlier comment. What I claim is that at most $3612/4032\approx 89.6\%$ of the positions using a l …

Theorem. There is $P$ for which the reachability problem in your first question is NP hard. Proof. Suppose we have any NP decision problem $A$, where for any string $a$, we have $a\in A$ if and only …

The answer is Yes. Furthermore, such a family can be found of size at most the cardinality of A, even when S is much larger. The key to the solution is to realize that every such family S arises as …

I think the entire subject of computational complexity theory, with the concepts of P, NP, PSPACE, EXPTIME and so on, is fundamentally about exploring various precise senses of what "better than brute …

The longest path in the game tree very likely arises from the two players cooperating merely to make a very long game, rather than trying to win, and therefore seems little related to finding a winnin …

The answer is yes, because from $A$ and $A-B$ and $B-A$, you can reconstruct $B$ via $$B=(B-A)\cup(A-(A-B)).$$ So if we fix $A$, we get a map from $(\mathscr{A}\setminus\mathscr{A})^2$ onto $\mathscr{ …

This is too long for a comment, so I am placing it here. In this article of the Notices of the AMS, Gonthier describes a full formal proof of the four-color theorem, which makes explicit every logica …

Update. I've improved the argument to use only the consistency of $T$. (2/7/12): I corrected some over-statements previously made about Robinson's Q. I claim that for every statement $\varphi$, the …

It has been pointed out in the comments that Ewan's insightful solution shows that a negative answer to the question is consistent with ZF, since a positive answer implies AC. But let me go one furt …

Apart from your specific example, the idea of truth-by-accident has been studied in the context of formal first-order languages, which includes the language of graph theory, and in his dissertation, K …

Complementing Andres's excellent answer, let me simply try to help build your intuition for elementary submodels. The basic situation is just like the familiar fact that if you have finitely many grou …

Many chess positions that one may easily set up on a chess board are impossible to achieve in a game of legal moves. For example, among the impossible situations would be: A position in which both k …