Wikipedia:Reference desk/Archives/Mathematics/2011 December 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 20

Marcus Hutter versus Yuri Matiyasevich

Marcus Hutter claims to have found an algorithm for all well defined problems, but such an algorithm would be able to ascertain if a given Diophantine equation is solvable, and it could do this for any Diophantine equation. Yet, as Yuri Matiyasevich showed, no such algorithm exists - see Hilbert's tenth problem. How is this contradiction resolved?

At first I thought that it was because Marcus Hutter's algorithm M could only solve problems p for which there exists another algorithm (and could only do so five times slower too, as per the link), and since there is no algorithm for ascertaining if a general Diophantine equation has solutions, M would be unable to do so too. That makes no sense though - for any particular Diophantine equation, there exists an algorithm which can determine if it has solutions - a very trivial one in fact: simply the algorithm which ignores the input and just prints out the correct answer! That would imply that not only could M solve p for any p, but it could do so in constant time (if his claim in the link is correct) but of course this still contradicts Matiyasevich's solution to Hilbert's tenth problem. Widener (talk) 06:17, 20 December 2011 (UTC)

Without reading more than the abstract, it looks like he's only considering algorithms with correctness proofs. While the algorithm for solving a Diophantine equation you describe exists, it lacks (in general) a correctness proof. This just seems to be a particularly efficient dovetailing.--121.74.123.159 (talk) 10:41, 20 December 2011 (UTC)

Statistical test for Gender, Race, and Socioeconomic status (three options) and a three-scale likert

Hi, I was wondering if there is a test for significance to see if Gender, Race, and Socioeconomic status (with 3 options of below poverty, around poverty, and above poverty) all being used a separate IVs cam be seen as having an effect on the DV being the results of a three option likert? What is the best option. Thanks. (By the way n=35 with some responses lacking, I know that isn't the best but the population was already extremely small... --109.66.119.146 (talk) 12:42, 20 December 2011 (UTC))--109.66.119.146 (talk) 12:28, 20 December 2011 (UTC)

The phrase "below poverty" seems odd. "Below the poverty line" is clearer. StuRat (talk) 20:38, 20 December 2011 (UTC)

What you appear to want to know is how correlated is gender to poverty, race to poverty, and socioeconomic status to poverty (and I think you are using socioeconomic status as the name of "poverty status" - which means you only have three variables). It doesn't matter what the values of poverty are. You just want correlation. I'd use a forest plot. It graphically represents how confident you can be that, according to your data, gender is correlated with poverty and/or race is correlated with poverty. SAS, R, and any respectable statistics program (and even Excel, I believe) can produce a forest plot. -- kainaw™ 20:50, 20 December 2011 (UTC)

OP here. Called it below poverty because it is based on an assumption of being below poverty whether one is below the poverty line or not. Also has to do with the fact the data is international and I can't give people one poverty line to work with. Would love to actually see if there is a correlation with the three scale likert (which is called 'positivity index' but I don't think an explanation is needed here). I guess still correlation would be accurate or not, this is where I am not sure.--109.66.119.146 (talk) 07:59, 21 December 2011 (UTC)

I regularly do studies which have factors of race, gender, and poverty. It is all about correlation. For example, hypertension control with medications is heavily correlated with race. When mixing multiple factors, you have to do a multivariate analysis to take all other factors (and combinations of factors) into account. That is why I use SAS. I don't have to do the work. I just supply the data and select the analysis. Even if you don't use complex analysis, you still need to calculate the correlation between each factor. -- kainaw™ 14:20, 21 December 2011 (UTC)

Going between hexagonal and parallelogram tilings

Giving any parallelogram or hexagonal tiling of the plane (where the hexagon has parallel opposite sides, of equal length), we can form a lattice, whose action on the plane produces the torus, with fundamental domain the primitive tile. An induced flat metric can be put on the torus, via the hexagon or parallelogram. However, any lattice in the plane can be uniquely determined by just two vectors, i.e. we may convert any hexagonal lattice into an equivalent parallelogram lattice (producing a torus with the same, flat metric). I can see how to get from a hexagonal tile to a parallelogram tile (by taking three mutually non-adjacent vertices in the hexagon, joining two lines between them, then cutting along these, while gluing opposite sides of the hexagon). However, when I try to pass from a parallelogram tile to a hexagon, I seem to have too many degrees of freedom, so I can't come up with a canonical (up to lattice isometries) hexagonal tile to send it to. Is this possible? It seems like it should be, when thinking about the metrics induced on the torus -- non-equivalent parallelogram (or hexagonal) lattices give rise to different metrics on the torus, so it seems like there should be a bijection between the two sets of lattices/tilings. Any help much appreciated! Icthyos (talk) 12:33, 20 December 2011 (UTC)

In a rather similar problem that I worked on long ago, to go from one lattice to another, I first went to a square grid lattice, then to the other lattice. Mapping to and from squares was much easier because the vectors are based on Euclidean space. The trick is to make the square lattice with smaller tiles (you won't be able to map to them all) so you can easily map back and forth between lattices where the borders don't line up easily. -- kainaw™ 16:09, 20 December 2011 (UTC)

(ec) I'm not sure if this is what you want, but if I got it properly it is enough to mark any point P inside a parallelogram L, join P with lines to arbitrary three vertices of L, and then copy that in all parallelograms... --CiaPan (talk) 16:18, 20 December 2011 (UTC)

That was my approach, except I require that the angles between each pair of lines meeting at P be $2\pi /3$, so my hexagons are always regular . (Edit: I fear I'm talking nonsense, I forgot I'm interested in a particular class of hexagons, which I've just realised are woefully indeterminate at this point. I will do some thinking...) I was just finding it difficult to show that the (finite?) number of points P for which this held, all produced the same hexagonal lattice/tiling (up to isometries) when regluing. I suppose if I could do it for the bog-standard equal sided regular hexagon, then I could argue using something like shear transformations (is there a unique shear transformation mapping one parallelogram to another?) Icthyos (talk) 17:29, 20 December 2011 (UTC)

I'm afraid you can not transform an arbitrary parallelogram onto another one with a shear mapping alone. However, if you compose it with scaling and rotation, then you'll get an (almost) general affine transformation which, of course, allows to map them as you need.
If you manage to transform your parallelogram into squares, then chose the point P in 1/3 of the square'a diagonal and join it to three nearest corners (and copy that over the whole tiling). Then a simple shear of the square by 1/2 of its side makes hexagons regular. HTH. --CiaPan (talk) 19:29, 20 December 2011 (UTC)

Sorry, I should've made clear - I'm really working with equivalence classes of lattices, up to rotation/scaling. It's because I'm actually interested in the (unit volume) flat metrics on the torus, so rotating/scaling are irrelevant. I think I'm getting slightly bogged down in specifics - at the end of the day, all I care is that the metric is flat. It just surprised me that taking a hexagonal lattice, there is a unique (or maybe not, is that my problem?) parallelogram lattice whose action produces the same metric torus, and yet given a parallelogram lattice, there is not a single hexagonal lattice whose action produces the same metric torus (...or is there?) Icthyos (talk) 20:27, 20 December 2011 (UTC)

For the sake of closure: it turns out, I was asking the wrong question. Taking a (fixed) parallelogram tiling, and using CiaPan's approach with the three lines meeting at point P, you get an uncountable number of different hexagonal tilings...but they all give the same hexagonal lattice (given by the two parallelogram vectors, and their sum), which is what is used (not the tiling) to produce the torus and its metric. This is a satisfying resolution. Thanks all! Icthyos (talk) 15:05, 21 December 2011 (UTC)

ZFC being consistent if a proper sub-set of ZFC is consistent

It has already been proved, that there is a proper sub-set A of ZFC, satisfying that - if A is consistent - then ZFC is consistent as well (Of course, A=ZF). Is there any other proper sub-set A of ZFC, satisfying that property? (I don't count the Axiom of Regularity) 77.127.51.217 (talk) 13:04, 20 December 2011 (UTC)

Well, you can certainly take out axioms that are actually proved by other axioms. For example, in the traditional presentation of axioms, the axiom of separation is actually redundant as it follows from the axiom of replacement. Why don't you count the axiom of foundation (btw this is the more usual name than "regularity")? --Trovatore (talk) 19:15, 20 December 2011 (UTC)

I don't count the Axiom of Foundation, because it has already been proved that if ZFC - {Axiom of Foundation} is consistent then ZFC is consistent as well. Anyways, by ZFC I mean: {Axiom of extensionality, Axiom of Union, Axiom of Power set, Axiom of Replacement, Axiom of infinity, Axiom of Choice}. 77.126.184.79 (talk) 23:41, 20 December 2011 (UTC)

The Axiom of replacement is not a single axiom, but an axiom schema. You might be able to select sub-schema from them. Aside from that, the axiom of infinity clearly is needed, as $V_{\omega }$ is a set which is a model of ZFC-infinity. A little more subtly, Power set is clearly needed. I don't know about Union or Extensionality. And, again, obviouly, some form of Replacement is needed, or $V_{\omega _{1}}$ would be a model. — Arthur Rubin (talk) 19:57, 25 December 2011 (UTC)