Wikipedia:Reference desk/Archives/Mathematics/2008 November 22

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 22

Set theory questions

1) Let T = ZFC - Infinity + (not Infinity). Is T finitely axiomatizable?

2) We write PA for Peano's arithmetic. Can it be proved in PA (or, if possible, even in some nice, weaker version of arithmetic) that Con(PA) and Con(T) are equivalent? 67.150.245.161 (talk) 02:04, 22 November 2008 (UTC)

Looks like:

"If your question is homework, show that you have attempted an answer first, and we will try to help you past the stuck point. If you don't show an effort, you probably won't get help. The reference desk will not do your homework for you."

If I'm wrong, please make an effort to say so. -- Aeluwas (talk) 10:56, 22 November 2008 (UTC)

This is not in any way homework. I assumed that to people familiar with set theory, this would be obvious.

I became curious about the second because it's clear that Con(T) implies Con(PA). For the other direction, I was wondering if you could somehow model V_ω within a model of PA. The first question arises because it would be interesting if T were finitely axiomatizable, yet its consistency were equivalent to that of PA, which isn't (I think). I'm not specialized in this area, and I was wondering if somebody familiar with the relation between "weak" set theories and arithmetic could clarify things a bit for me. 67.150.255.24 (talk) 11:35, 22 November 2008 (UTC)

Come on. Can this be homework (no in case you were wondering)? One thing that User:Aeluwas said was correct. Namely, have a go at the problem; you might surprise yourself and find an answer. Have you thought about it yet (thought hard)?

Topology Expert (talk) 11:56, 22 November 2008 (UTC)

Yes, I've thought about it, but it's the kind of thing that I imagine takes tons of technical lemmas to get anywhere on, especially on the issue of turning consistency of a theory into a specific arithmetic statement. One of the parts would be that even to make sense of the question, you'd first have to encode into a single integer the entire algorithm used to determine whether a sentence is one of the axioms or not. Since this isn't the kind of thing I think about a lot, I wouldn't trust myself cutting corners about this formalization. I was really hoping somebody might already know the answer.67.150.255.24 (talk) 12:20, 22 November 2008 (UTC)

Actually, I'll admit I did cut corners like that when I said that "clearly" Con(T) implies Con(PA). I see an algorithm for converting a proof of a contradiction from PA into a proof of a contradiction from T. I'm cheating in asserting so confidently that this fact can be formalized in PA. 67.150.255.24 (talk) 12:24, 22 November 2008 (UTC)

Any model of PA can (I think; not all details checked. It certainly works on the standard model) be turned into a model of T by defining $n\in m$ to mean that the nth digit (counting from the right, starting at 0) of the binary expansion of m is 1. I'm not happy enough with the technicalities myself to guess whether this idea can be formalized in PA. Algebraist 12:34, 22 November 2008 (UTC)

That's a very elegant model. I thought some complicated definition by induction would be required, but that's very simple. Thanks. And I agree that it works for N. Do you have any ideas on the first question?67.150.244.159 (talk) 13:10, 22 November 2008 (UTC)

Here's an idea (don't know if it works): show that PA proves all the axioms of T, with membership interpreted as above. Show conversely that one can recover 0, 1, + amd * from this membership relation, and that the axioms of T prove the axioms of PA. Conclude that since PA is not finitely axiomatizable, T is not either. Algebraist 14:10, 22 November 2008 (UTC)

This strategy doesn't work in general. For example, ZFC is not finitely axiomatizable but NBG set theory is an extension that is finitely axiomatizable. In fact I believe NBG and ZFC are equiconsistent. — Carl (CBM · talk) 14:21, 22 November 2008 (UTC)

The answer to question 2 is certainly yes. ZF with infinity replaced by its negation is equiconsistent with PA, and the syntactic interpretations are very concrete. I'd expect that the equiconsistency is provable in PRA.

I don't know the answer to question 1 after a couple minutes' thought. — Carl (CBM · talk) 14:16, 22 November 2008 (UTC)

Have a look at this.

Topology Expert (talk) 05:44, 23 November 2008 (UTC)

Despite what Carl says, I think that Algebraist's program, if carried out, would prove that T is not finitely axiomatizable. The comparison with Bernays-Gödel is an interesting one, but I think the analogy is not perfect. When you prove equiconsistency of BG and ZF, you start with a model M of ZF, and add a point for each class, where classes are defined by formulas (as seen in our own universe, to which M belongs). The model of BG defined this way does not appear to be describable within M. On the other hand, the model of T obtained from the model of PA by Algebraist's method not only has the same underlying set, but its version of ∈ is definable within the model of PA.

I haven't checked the details yet, but my feeling is Algebraist's approach would work. Thanks to all of you.

Topology Expert, were you referring me to that article generally or to something specific? 67.150.255.85 (talk) 06:42, 23 November 2008 (UTC)

First, what you call "Algebraist's program" has been actually well-known for decades. It works, and it indeed implies that T is not finitely axiomatizable, because it amounts to a mutual interpretation of T and PA. GB is not interpretable in ZF, which is why it can be finitely axiomatizable even if ZF is not. Finally, you do not really have to construct the interpretation of T in PA. It is a general theorem that any theory capable of minimal sequence encoding which proves full induction (for its natural numbers) is uniformly essentially reflexive, hence it cannot be finitely axiomatizable unless inconsistent. — Emil J. 11:31, 24 November 2008 (UTC)

My axiomatic set theory knowledge is not very good but perhaps the section 'axiomatic set theory' in that article may provide some useful information (if not, I can attempt the first question (but don't expect an answer!)).

Topology Expert (talk) 07:13, 23 November 2008 (UTC)

Nope. I will have to learn this!

Topology Expert (talk) 07:16, 23 November 2008 (UTC)

Thanks, Emil J, for confirming what's been said. I'd be interested in having a reference

for the theorem you mentioned. 67.150.255.218 (talk) 13:01, 26 November 2008 (UTC)

Category Theory

I only have a very basic understanding of category theory, but I was wondering about the generalizations (2-category theory etc.). How "far" do they go? If I repeat the process ω times, will I still be able to create a new kind of structure by doing it the ω+1^st time, or will I get the same kind again? What about ω₁? Thanks, *Max* (talk) 03:12, 22 November 2008 (UTC).

OK. First of all the intuitive idea of a 2-category is simple defining some sort of 'equivalence' between morphisms. For instance, in topology, two maps from X to Y (X and Y are topological spaces), may be homotopic (so morphisms between morphisms are simply homotopies) but a stronger condition (more like isomorphic) would be to say that they are isotopic. Now a three-category starts to get a litte silly (very interesting though). How can you define some sort of equivalence between equivalences of maps; i.e how can you define whether two homotopies between maps f and g may be equivalent? This is very easy to develop in a concrete situation such as in topology where we can speak of homotopies between homotopies (of course there exists such a thing because homotopies are mappings). They are also (of course) easy to develop in category theory but thinking it with respect to one field may help you to understand this notion intuitively.

There is actually something called an omega-category (this is a good question) but you can't define categories for uncountable ordinals (in this case, induction does not work). Since explaining this may take some time, I recommend reading this (page 109). It discusses these categories. If you are really interested, I would recommend reading a proper book on category (unfortunately category theory-articles in Wikipedia are under-developed but hopefully they will expand).

Hope this helps.

Topology Expert (talk) 03:39, 22 November 2008 (UTC)

Thanks for you answer. Just to be sure, there are ω+1 categories, right? *Max* (talk) 15:32, 23 November 2008 (UTC).

geometry(shape and size,undefined terms)

tell whether each of the following represents a point, a line or a plane.

1.top of a box-plane 2.four corners of a room-plane 3.side of a blackboard-line 4.curtain rod-line 5.star in the sky-point 6.edge of a table-point 7.cover of a book-plane 8.tip of a pen-line 9.a clothesline-line 10.a grain of rice-plane

Illustrate each of the following and label the diagram.

11.B lies on M 12.l and m intersect at E. 13.A contains CD 14.A<B and C lie on l 15.A and B intersects B at E.

• File:A cross linen2

a cross limne

I take it you're asking us to check your work on 1-10. I agree with all but these three: 6, 8, 10. StuRat (talk) 07:35, 22 November 2008 (UTC)

I believe there's one more that needs review, but rather than just tell you which one, I'll suggest you review 1-5 and see if you can pick it out. -- Tcncv (talk) 19:52, 22 November 2008 (UTC)

Linear feedback shift register

Is there a cyclic binary sequence that can be generated by a linear feedback shift register, but whose reverse sequence cannot? (If so, what would be a simple (counter-)example?)

Never mind. Found the answer in LFSR#Output-stream_properties. --98.114.98.155 (talk) 17:08, 22 November 2008 (UTC)

RPN

I am trying to use an RPN (reverse Polish notation) calculator to evaluate the following expression:
${\frac {2.37}{-59.3}}-{\frac {91.2}{(-86.1)^{2}}}\,\ln \left[{\frac {(-.0662)^{2}+.00143}{-47.2+{\sqrt {2590}}}}\right]$

The key says the answer is 3.94x10^-2 but I keep getting 3.37x10^-1. Here is the way in which I am entering the expression:
2.37, enter, 59.3, +/-, {divide}, 91.2, enter, 86.1, +/-, x^2, {divide}, {minus}, .0662, +/-, x^2, enter, .00143, {plus}, 47.2, +/-, 2590, {squareroot}, {plus}, {divide}, {natural logarithm}, {times}. So where is my error? TIA, Ζρς ι'β' ^¡hábleme! 23:53, 22 November 2008 (UTC)

You've made at least two errors. It should be 86.1, x^2, +/-, not the other way around, and the minus should be last of all. Algebraist 23:57, 22 November 2008 (UTC)

Oops, that's in parentheses sorry. It's fixed now. Ζρς ι'β' ^¡hábleme! 00:13, 23 November 2008 (UTC)

In that case the only mistake is that the minus should be last. That should give the correct answer. As a matter of interest, why in the name of the compassionating are you using an RPN calculator? Algebraist 00:08, 23 November 2008 (UTC)

Well, I am in U.I.L. mathematics and science. I participate in, among others, the calculator applications event. It is faster to do calculations with an RPN calculator than with an algebraic notation calculator because there are fewer things one must hit in order to correctly enter the expression. This is evident, also, because the people who consistenly rank highly in this event all use HPs and are good with them. I am trying to improve my RPN to improve my score. (By the way, thanks for the help.) Ζρς ι'β' ^¡hábleme! 00:13, 23 November 2008 (UTC)

What a silly event. I'd never heard of such a thing before. Algebraist 00:21, 23 November 2008 (UTC)

I was just about to say that. Who in their right mind would compete to see who can plug numbers into calculators the fastest? Then again, I guess it's no sillier than plenty of other competitions... --Tango (talk) 00:23, 23 November 2008 (UTC)

I saw a report saying when people gesture what they mean they naturally use subject object verb order whatever their own language is. So I for one him all the luck when he in this event competes wish and he does well hope :) Dmcq (talk)

I'd never thought about that, but you're right, people do gesture like that... --Tango (talk) 13:10, 23 November 2008 (UTC)