1,172 reputation
511
bio website
location
age
visits member for 1 year
seen 9 mins ago

1d
comment Does Nelson try to prove PA inconsistent directly?
If PA proves the statement "PA is consistent", that would for sure establish the inconsistency of PA. If PA proves "PA is inconsistent", that only proves the inconsistence of PA + Con(PA) or stronger theories such as ZF.
1d
awarded  Yearling
Nov
24
comment Is it possible to define higher cardinal arithmetics
"Hyperoperations" on ordinal numbers have been treated e.g. by Doner & Tarski, but of course you are aware of that.
Nov
22
comment Coloring algorithm maximising color difference between neighbors
This is a specialization of the graph T-coloring problem, which is said to have application to [frequency assignment](www.inets.rwth-aachen.de/pub/Frequency_allocation_for_WLAN.pdf) problems.
Nov
21
comment when a given graph is 3-colorable?
The condition "doesn't have any node connected to all 3 vertices of a triangle" (in other words, "doesn't have any vertex connected to all 3 nodes of a triangle") is a necessary condition for 3-colorability, but not sufficient: for example, consider a wheel with 5 spokes. As far as I know, there is no nice characterization of 3-colorable graphs.
Nov
20
comment Minimal hypergraphs with respect to separation
@AlexDegtyarev, I see. I don't think that by "minimal" the OP means a $T_1$ structure $E$ which is a subset of every $T_1$ structure; I think he means a $T_1$ structure $E$ such that no proper subset of $E$ is a $T_1$ structure. This is the usual meaning of "minimal element" in English; the other would be called "minimum" or "least element".
Nov
20
revised Minimal hypergraphs with respect to separation
added 7 characters in body
Nov
20
answered Minimal hypergraphs with respect to separation
Nov
16
answered Are there any books that take a 'theorems as problems' approach?
Nov
14
answered Graph automorphism that swaps two pairs of nodes
Nov
8
comment Is PA consistent? do we know it?
What I don't understand is, if someone doubts that integers exist, then what does "PA is consistent" mean to him? Does it make sense to imagine that integers don't exist, but formal proofs do exist? Does anybody think that "there is no proof of 0 = 1 in PA" is a meaningful assertion which must be either true or false, but "there are no odd perfect numbers" is meaningless formalism?
Nov
7
comment Expected number of distinct nodes visited in a directed bipartite graph
This question belongs on Mathematics Stack Exchange, not Math Overflow. The expected number of marked vertices in $O$ is just the sum, over all vertices $v\in O$, of the probability that $v$ is marked. The vertices in $I$ are sampled with replacement, right?
Nov
4
comment Order dimension vs topological dimension of a poset
For a finite poset the topology is discrete, isn't it? So the topological dimension is zero, but the order dimension can be any natural number. So your question is whether the topological dimension can ever exceed the order dimension.
Oct
29
comment Find all faces in a graph from list of edges
What if the neighbors of each vertex are listed in counterclockwise order, i.e., the neighbors of 1 are 2,5,4,3 on the left, and 2,5,3,4 on the right? I guess that's enough to determine the embedding, isn't it?
Oct
26
comment Counterexamples in Algebra?
@darijgrinberg Of course you only have to add the axiom $0\cdot0=0$ to Kelley's axioms to get a correct definition of a ring.
Oct
26
comment Counterexamples in Algebra?
@darijgrinberg $0a=a0=0$ is not usually included among the axioms for a ring, since it is a consequence of the usual distributive laws together with the additive group properties.
Oct
26
comment Counterexamples in Algebra?
@darijgrinberg Kelley's General Topology, first printing, p. 18: "A ring is a triple $(R,+,\cdot)$ such that $(R,+)$ is an abelian group and $\cdot$ is a function on $R\times R$ to $R$ such that: the operation is associative, and the distributive law $(u+v)\cdot(x+y)=u\cdot x+u\cdot y+v\cdot x+v\cdot y$ holds for all members $x$, $y$, $u$, and $v$ of $R$."
Oct
24
comment Name for (function, set) pairs?
@NoahS What is "partial" about $f:X\to X$?
Oct
23
revised Obscure Names in Mathematics
deleted 35 characters in body
Oct
23
comment Obscure Names in Mathematics
@GerryMyerson Dagnabbit! I searched the page for "Byzantine" but I forgot to click on "show more comments". I will delete the generals from my answer.