Wikipedia:Reference desk/Archives/Mathematics/2010 May 29

Mathematics desk
< May 28	<< Apr | May | Jun >>	May 30 >

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.

May 29

Is Axiom of Extensionality Converse true (special formulation)?

This is the typical form of the axiom of extensionality in ZF: $\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]$. The converse of this form is clearly true, and in fact this is explained on the ZF page.

However, a second formulation is also given on that page: $\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)]$.

The converse of that formulation is $\forall x\forall y[\forall z(x\in z\Leftrightarrow y\in z)\Rightarrow \forall z(z\in x\Leftrightarrow z\in y)]$. How would one go about proving this? Is it usually taken as an additional converse axiom in this formulation? I am a beginner at set theory so I am curious about this alternative formulation of this axiom. —Preceding unsigned comment added by JamesMazur22 (talk • contribs) 00:40, 29 May 2010 (UTC)

Suppose x and y are such that your hypothesis holds, $\forall z(x\in z\Leftrightarrow y\in z)$. Can you show that x and y must in fact be equal? Hint: try substituting {x} for z. --Trovatore (talk) 00:44, 29 May 2010 (UTC)

(With that said, the "second formulation of extensionality" strikes me as a fairly silly way of phrasing the axiom. Unless it appears in that form in some standard reference, I'd go ahead and remove it from the page.) --Trovatore (talk) 00:54, 29 May 2010 (UTC)

Why should it be removed? The proof that the converse is true is quite simple. Assuming the hypothesis, as suggested by Trovatore, there is a set A of which x is a member by the axiom of pairing. Using the axiom schema of specification, there is a set B, such that $p\in B\Leftrightarrow p\in A\land \forall z[z\in p\Leftrightarrow z\in x]$. x is clearly a member of B (the double implication operator is reflexive). Under our hypothesis, y must be a member of B as well. Therefore, $y\in A\land \forall z[z\in y\Leftrightarrow z\in x]$. Using conjunction elimination we come to our final conclusion, $\forall z[z\in y\Leftrightarrow z\in x]$. Q.E.D. JamesMazur22 (talk) 13:49, 29 May 2010 (UTC)

I certainly had no mathematical objection to it. The proofs are trivial and there's no particular need to rehash them. My objection is that it looks like an overly clever attempt to make the axiom into a cute formal expression, with no real connection to its usage or meaning. Kind of thing just gets on my nerves a little bit. But I haven't looked up the rationale Algebraist mentions. Maybe I'll get around to it. --Trovatore (talk) 18:41, 29 May 2010 (UTC)

The article Zermelo–Fraenkel set theory gives some references for this version, as well as a reason for using such a perverse thing. Axiom of extensionality gives a bit more detail, without references. Algebraist 14:14, 29 May 2010 (UTC)

Maple 13

What is the output of "int(sin(cos(x)),x);" on your Maple 13 for Windows? The output on my Maple 13 for Windows is $\int sin(cos(x))\,dx$ without calculating. I also tried Maple 13 for Mac, and the output was a calculated result. Anything wrong on my computer?--百楽兎 (talk) 13:59, 29 May 2010 (UTC)

What that means is that Maple cannot find a simpler form for the indefinite integral than the integral itself. My own conclusion is the same, that there is no simpler expression in terms of standard functions. Dmcq (talk) 15:11, 29 May 2010 (UTC)

Perhaps your original problem was sin^-1(cos(x)) or sin(cos^-1(x))? Dmcq (talk) 15:20, 29 May 2010 (UTC)

Mathematica can't find a simpler expression either. Robinh (talk) 19:15, 29 May 2010 (UTC)

But Maple 13 for MAC can. That's why I confused. --百楽兎 01:18, 30 May 2010 (UTC)

What exactly did Maple 13 for Mac output? -- Meni Rosenfeld (talk) 08:07, 30 May 2010 (UTC)

Also, what does Mac13 do with Int( -sin(y) / sqrt(1-y^2), y ) ? - DVdm (talk) 10:06, 30 May 2010 (UTC)

What does this have to do with anything? You should wait for the OP to confirm that Maple receives magical integration powers from the Mac (rather than just having a mistake in the input) before hijacking the thread to solve your integral. -- Meni Rosenfeld (talk) 10:37, 30 May 2010 (UTC)

_{But I have to turn in my homework tomorrow morning! - DVdm (talk) 12:00, 30 May 2010 (UTC)}

He was just substituting y=cos(x) in the integral. Not that I think it'll do much good. Dmcq (talk) 12:11, 30 May 2010 (UTC)

Oh, I see. Sorry for the unfounded allegations. I obviously didn't suspect it was "homework", rather something you needed for some personal investigation. They don't give non-elementary integrals as homework.

I still don't understand why this query was important, though. -- Meni Rosenfeld (talk) 12:38, 30 May 2010 (UTC)

Forgive me for asking, but you are joking, right? DVdm (talk) 12:59, 30 May 2010 (UTC)

No. Which part? -- Meni Rosenfeld (talk) 13:20, 30 May 2010 (UTC)

I asked the OP what the output was for debugging purposes. You then asked about a seemingly unrelated integral (it didn't occur to me spontaneously that it's the same integral, substituted). I currently don't know why you asked that, but at the time I wrongly assumed that you were hoping that Maple has some unknown tricks and wanted to leverage it for your own purposes. The "magical powers" bit was humor of sorts, meant to show that this hope was unjustified. Then I saw Dmcq's explanation and your own reply, which I thought meant to use sarcasm to show why my assumption was absurd. -- Meni Rosenfeld (talk) 13:33, 30 May 2010 (UTC)

Ok, you are getting close. I'll leave it to you to figure out my real, deeper intensions. Cheers :-) - DVdm (talk) 13:42, 30 May 2010 (UTC)

I cleaned up the indentation of this nice dialogue for clarity. Bo Jacoby (talk) 06:56, 1 June 2010 (UTC).

Huh? You messed it up. Replies should be one level deeper than what they're replying to. See Wikipedia:Indentation. I've restored it to the original correct form. -- Meni Rosenfeld (talk) 07:05, 1 June 2010 (UTC)

I like the little bit of outdenting, it reminds me of the Mouse's Tale. Dmcq (talk) 09:15, 1 June 2010 (UTC)

What does F(x|theta) mean?

What does this mean; $F(x\mid \theta )\,\!$ ;in the article Admissible decision rule?--Wikinv (talk) 14:46, 29 May 2010 (UTC)

See Conditional probability density function and Conditional probability. DVdm (talk) 14:51, 29 May 2010 (UTC)

why cant we integrate (sinx)^2 and (cosx)^2 without using cos2x

why cant we integrate (sinx)^2 and (cosx)^2 without using cos2x identity and does this extend to (tanx)^2 with another identity? —Preceding unsigned comment added by Jenny1004 (talk • contribs) 15:42, 29 May 2010 (UTC)

Certainly one can integrate sin²x dx without using any double-angle formula:

$\int \sin ^{2}x\,dx=\int (\sin x)(\sin x\,dx),$

so let

$u=\sin x\,$

$dv=\sin x\,dx$

and then we get

$du=\cos x\,dx$

$v=-\cos x\,$

Now integrate by parts:

${\begin{aligned}\int u\,dv=uv-\int v\,du&=-\sin x\cos x+\int \cos ^{2}x\,dx\\&=-\sin x\cos x+\int 1-\sin ^{2}x\,dx\\&=-\sin x\cos x+x-\int \sin ^{2}x\,dx\end{aligned}}$

Next, add the integral to both sides:

$2\int \sin ^{2}x\,dx=-\sin x\cos x+x+{\text{constant}},$

and finally

$\int \sin ^{2}x\,dx={\frac {-\sin x\cos x+x}{2}}+{\text{constant}}.$

Michael Hardy (talk) 16:46, 29 May 2010 (UTC)

Differentiating a power of tan gives a next higher order polynomial in tan which is quite interesting. You can use that together with the integral of tan to get the integral of any power. No tan(2x) is needed. Dmcq (talk) 17:17, 29 May 2010 (UTC)

Hey,no way.....int\sin^2x is x/2-sin2x/4 So the above method wont hold good!!Rohit.bastian (talk) 11:22, 1 June 2010 (UTC)

But $\sin 2x/4=\sin x\cos x/2$, so they're the same. Staecker (talk) 11:55, 1 June 2010 (UTC)

OK, let me put the bottom line this way:

${\begin{aligned}\int \sin ^{2}x\,dx&={\frac {-\sin x\cos x+x}{2}}+{\text{constant}}\\[12pt]&={\frac {x}{2}}-{\frac {\sin(2x)}{4}}+{\text{constant}}.\end{aligned}}$

They're both the same thing. See trigonometric identity. Michael Hardy (talk) 13:42, 1 June 2010 (UTC) Exactly... I need to refine my integration skills i guess!!Rohit.bastian (talk) 11:45, 6 June 2010 (UTC)

Making 2+2=5

It was cited as one of the dumbest Yahoo! Answers questions of all time. Now I ask it here. Keeping as close to definitions in the usual fields as possible, is there an algebra or can we redefine Z such that 2+2=5? SamuelRiv (talk) 17:30, 29 May 2010 (UTC)

2 + 2 = 5, heh. --MZMcBride (talk) 17:48, 29 May 2010 (UTC)

That's it! Screw you guys - I'm leaving the project! ;) SamuelRiv (talk) 18:05, 29 May 2010 (UTC)

See Modular arithmetic. Compute modulo one. $\scriptstyle e^{2\pi i(2+2)}=e^{2\pi i\cdot 5}.$ Bo Jacoby (talk) 18:35, 29 May 2010 (UTC).

Depends on what you mean by "5". If you are willing to define 3 + 1 = 5, then, yes, you can have 2 + 2 = 5. (But note that then 5 + 1 ≠ 3 + 3, but rather 5 + 1 = 2 + 3, and you'll have to come up with a new symbol for "2+3".) However, if you want 1+1=2, 2+1=3, 3+1≠5 and 2+2=5, there's no way of doing it without breaking associativity of addition: 2+2 => 2+(1+1) => (2+1)+1 => 3+1, so if 2+2=5, that implies 3+1=5. -- 174.24.200.38 (talk) 21:18, 29 May 2010 (UTC)

If you round all the terms of 2.4+2.4=4.8 to the nearest integer, you get 2+2=5. That's the least convoluted way of doing it, I think. --Tango (talk) 21:25, 29 May 2010 (UTC)

Bo's response sets all integers = 1, effectively (mod 1), but it's a neat illustration. IP's is just symbolic, and I'm looking for a modification of Z (or Q or R or whatever) that doesn't necessarily have to preserve any of the field or group axioms. Tango - that's a pretty neat idea - it looks like you could make an algebra like ZxZ and have a function taking it to Z that looks to human eyes like a neat trick. But of course, it's still a trick where the actual math is done in the second dimension - the decimal place.

Maybe I'm more interested in a different question: can we *construct* a general closed algebra over something looking like addition that makes it such that 2+2=5 without 5=4. Upon thinking about it: I want a+a=b but b!=2a. Ugh, that's bad. The answer, if I want this structure to be at least homomorphic to one of the usual fields, is to introduce another operator * such that a+a = b != a*a, or in other words, 2+2 != 2*2. I guess in such a case * is arbitrary, though it has to be closed and probably distributive-associative, and it can only work over this "scalar" magma (so let's say we can't select elements arbitrarily from R - actually, that should be a rule in general, because R lets us do anything). SamuelRiv (talk) 18:39, 30 May 2010 (UTC)

Consider a random variable a, say, the outcome of flipping a coin. (Number of heads = 0 or 1). Then a+a may be the outcome (0 or 1 or 1 or 2) of flipping two coins, while 2a is twice the outcome (0 or 2) of flipping one coin. Then a+a is not equal to 2a. So

(0.5±0.5)+(0.5±0.5)=1±0.7

while

2·(0.5±0.5)=1±1 .

Bo Jacoby (talk) 07:20, 1 June 2010 (UTC).

Niiiiiiiice. Can even work that into automata theory and quantum algebra. SamuelRiv (talk) 02:47, 3 June 2010 (UTC)

Thanks. But how do you do that? Bo Jacoby (talk) 05:25, 3 June 2010 (UTC).

I made a wonderous proof of this statement (actually 1+1=π, but there's plenty of customization) tonight at the coffee shop, which I'm too tired to fit within the margins of this page. You'll have to wait until I feel up to it, and I'm starting to get really sick, so it might be a while. Meanwhile, I need to know the span of functions for which f*f~f, that is, the convolution of the function f with itself looks like f. SamuelRiv (talk) 04:36, 4 June 2010 (UTC)

Question about 3SAT and NP-Complete

When determining the complexity class of an algorithm solving 3SAT, would you consider the input size to be the number of literals or the number of variables? I ask since given n variables the max number of literals is a cubic polynomial in n. 67.163.183.146 (talk) 19:32, 29 May 2010 (UTC)

A power of 3 difference in the size makes no difference as far as being NP complete is concerned. Dmcq (talk) 19:58, 29 May 2010 (UTC)

I'm aware of that, though, I suppose putting NP Complete in the title was a tad unclear; I'm just curious which you would use for input size; sorry about the confusion:) Thanks:) 67.163.183.146 (talk) 20:23, 29 May 2010 (UTC)

I'd use the number of clauses rather than the number of variables as that seems to be what matters most in transforming it into other problems. Dmcq (talk) 22:43, 29 May 2010 (UTC)

I'd use number of literals, since that carries over even when you lack a normal form. But number of variables will be bad because it generalizes badly to similar problems. Taemyr (talk) 10:56, 2 June 2010 (UTC)