Mathematics desk
< October 31	<< Oct \| November \| Dec >>	November 2 >

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.

November 1

Descriptive Complexity and FMT- a really simple question

Hi:-) This question is, probably, borderline stupid, but I can't reason it out now that I'm thinking about it. For a logic L (F0, LFP, whatever), define the set of L-expressible problems as {Finite_Models(u): there is a vocabulary t and u is in the L-language of t}. I've frequently seen it mentioned that you can get away with just considering the vocabulary that amounts to binary strings, so my question is: if I restricted the definition of L-expressible to the case where t has a 1-place relation and a linear order, then if I showed (in the this restriction) that L-expressible = L'-expressible, does that mean that the general case would follow? More generally, can we just fix t to be any vocabulary?Phoenixia1177 (talk) 06:46, 1 November 2013 (UTC)[reply]

Im guessing that in the case of strings it's because you encode models to strings, but whqt about the general case? Could you just consoder graphs with a single binary relation? Essentially, can you represent all strings in any other vocabulary or are they special?Phoenixia1177 (talk) 11:07, 1 November 2013 (UTC)[reply]

There's a standard folklore result in model theory that every structure can be represented by a graph (directed or undirected). Obviously every graph can be coded by a binary string, but I don't see that they have the same logical content. For example, it's easy to say in the language of graphs "there is a 5-clique". How would you say "the graph encoded by this string has a 5-clique" in first-order logic? — Preceding unsigned comment added by 80.109.80.78 (talk) 11:34, 1 November 2013 (UTC)[reply]

As long as you could state something equivalent to E (the edge relation) in FO, you can do the rest. (In DC it is assumed we have the natural order and the ability to check bits) To encode our string, starting at (0, 0) and working lexicographically, if E(x, y) then write 00BINN(x)11BINN(y) where BINN(z) is z encoded in binary using 10 and 01 instead of 1 and 0. There are FO relations L and R so that L(x) iff x is a position immediately after two 0's, and R(x) iff x is a position immediately after two 1's. Then, using those you can get E(x, y) that holds iff L(x) and R(y) and there is exactly one instance of 11 between x and y. While tedious, any statement about the graph translates into a statement in the string. You can probably do this more simply; especially if you step beyond FO to anything including FO(TC).Phoenixia1177 (talk) 06:04, 2 November 2013 (UTC)[reply]

I'm a little off in the above, there's goofiness checking parity in FO and you can get 00 in the BINN strings; so you might need to do something like 001BIN(x)0001BIN(y) and use 011 and 01 in place of 10 and 01 (or some such), then you can be sure that you're grabbing the right bits.Phoenixia1177 (talk) 06:15, 2 November 2013 (UTC)[reply]

The issue I see here is defining equality. Sure, I can make a first order predicate that recognizes when I'm at the beginning of a code (L and R in the above). But how can I make a predicate to recognize when x and y are the beginning of the same code (in different locations)? It seems you would need this to translate a statement about graphs. For example, how would you translate the statement "there is a 3-cycle", i.e.

\exists x\exists y\exists zE(x,y)\wedge E(y,z)\wedge E(z,x)

.--80.109.80.78 (talk) 10:46, 2 November 2013 (UTC)[reply]

You can do this using the ordering: even if you don't know the length of strings encoding vertices, you can write a predicate that holds iff both are equal at each position between 001 and 0001. Again, it's a horrible pain- and I don't know the math tags to write it out- but it can be done.Phoenixia1177 (talk) 10:57, 2 November 2013 (UTC)[reply]

I'm going to remain skeptical without a little more detail. The issue seems to be that a first order sentence should only be able to examine boundedly many bits at once. Whatever the bound, I can make two distinct strings that look the same up to that bound: any interval in one of length that bound occurs as an interval of the other.--80.109.80.78 (talk) 12:34, 2 November 2013 (UTC)[reply]

I'll need to think on this- I've seen things that suggest otherwise, but I have yet to see the logic spelled out (I just checked a few references). Would it suffice to consider the case of a finite bit string with a constant indicating where the second substring beings; that is, would it work to show there is a relation that is true iff the part before the constant and the part after, and including, the constant are equal? You can easily constrain variables in the above case of encoding a graph to whittle it down to such.Phoenixia1177 (talk) 15:52, 2 November 2013 (UTC)[reply]

I don't understand what you're asking here. It's easy to come up with formulae that describe the beginning and end of a code for a point. The task is given BIN(x) and BIN(y), you need to find a formulae that holds if and only if they are equal. Where are you suggesting placing the constant?--80.109.80.78 (talk) 16:09, 2 November 2013 (UTC)[reply]

I was looking at them as part of one string Bin(x)Bin(y) with the constant marking where Bin(y) starts, since we were working with one big string above. I wasn't separating them, essentially. I'm sleepy, so I probably garbled what I was saying.Phoenixia1177 (talk) 16:47, 2 November 2013 (UTC)[reply]

In DC terms, you can do plus(x, y, z) is true iff x + y = z in FO. So, going with the one string above and Bin(x) starting at 0, Bin(y) at a: you could check that for all positions u and v that if plus(u, a, v), then they stored the same bit; and also that for the maximal position max that plus(a, a, max) so that you know both were the same length.Phoenixia1177 (talk) 16:57, 2 November 2013 (UTC)[reply]

I'm not sure what DC is, but you were asking about First Order logic earlier, and addition is definitely not FO-definable in finite linear orders. So this won't do it for FO-logic.--80.109.80.78 (talk) 18:03, 2 November 2013 (UTC)[reply]

Descriptive Complexity, that's the main motivation for the question.Phoenixia1177 (talk) 18:19, 2 November 2013 (UTC)[reply]

Number lines

Why are number lines virtually always horizontal? I never thought of this until I looked at our article and saw "The number line is usually represented as being horizontal", but thinking about it, I can't remember ever seeing a simple number line that was vertical. Nyttend (talk) 22:34, 1 November 2013 (UTC)[reply]

Might have to do with it being a teaching tool and blackboards being longer in the horizontal direction, and kids being able to reach the entire number line to show an answer on the board. StuRat (talk) 22:45, 1 November 2013 (UTC)[reply]

That makes sense. Another possibility is that when drawing the X-Yplane, X is normally horizontal. Bubba73 ^{You talkin' to me?} 01:43, 2 November 2013 (UTC)[reply]

I think that's backwards. X is horizontal because we make the plane adding the Y-axis to the standard number line.--80.109.80.78 (talk) 03:33, 2 November 2013 (UTC)[reply]

If I had to guess (and I absolutely am), I'd say it's because we read right to left.Phoenixia1177 (talk) 06:18, 2 November 2013 (UTC)[reply]

.elbisualp sdnuos tahT PrimeHunter (talk) 12:26, 2 November 2013 (UTC)[reply]

Now that's interesting. In the old days of Arabic contributions to mathematics, given that Arabic is written right to left, was there ever a convention of having the number line with numbers rising as we go right to left? Duoduoduo (talk) 14:21, 2 November 2013 (UTC)[reply]

Everything I could find, which is little, seems to indicate that the number line came about in relation to understanding negative numbers and is a fairly modern western invention (modern meaning the last 3-4 centuries, in this case). That could, just as well, be utterly false, the few mentions were not high quality and were focused in other directions (ha!). I did come across a suggestion that it had some relation to lines used in construction by Egyptians- there was also an implication in some random forum that depending on how it is written, Hebrew number lines can run right to left (I don't know how to check that, though.)Phoenixia1177 (talk) 16:02, 2 November 2013 (UTC)[reply]

Did ancient Chinese and Japanese have number lines, and if so, did they run vertically (as their texts did)?Ballchef (talk) 08:19, 5 November 2013 (UTC)[reply]