Wikipedia:Reference desk/Archives/Mathematics/2008 February 13

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.

February 13

THE PHYSICS MAGAZINE GUY,WITH AN ALGEBRA QUESTION FROM AN ALGEBRA MAGAZINE

Hey,guys I`ve got a sequence question the sequence for the first problem is 1,1 over two,one over three,one over four. I need the sequence completed.I also have a problem involving The Fibanocci Sequence. the numbers are 1,2,3,5,8,13.I also have to draw the next three figures in a sequence in which there are oval with one side,shaded black.Another,one with the top side shaded black.And,one last one with the right side black. Also,another one with a line through the circle.Another,with a cross in it,Another with several spokes. There,is a triangle with no lines One with a triangle going through it. And a last one with three across from the left. —Preceding unsigned comment added by Yeats30 (talk • contribs) 00:10, 13 February 2008 (UTC)

You want to know what comes next in the sequence $1,{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}}$? I think you can work that out for yourself... You haven't actually said what the second question is. And picture questions aren't really going to work unless you can reproduce the picture, however they aren't usually that difficult - some general advice: try to break the sequence down into different things that are changing (the shape, the colour, the orientation, etc.) and consider each separately. --Tango (talk) 00:16, 13 February 2008 (UTC)

Bullshit this is from an algebra magazine. If you read an algebra magazine, you are capable of working out a simple sequence like this. Stop asking wikipedia users to do your homework for you. -mattbuck (Talk) 01:56, 13 February 2008 (UTC)

Mattbuck, please try to keep civil even when dealing with someone who isn't following the rules themselves (i.e. posting homework questions). Did anybody bother to notify the user on his talk page that he'd been outed? No, so I'm going to do so now. Confusing Manifestation(Say hi!) 05:38, 13 February 2008 (UTC)

Sorry, I kind of figured he'd have read the countless people who have outed him in his questions, since if he asks them, he presumably wants answers and thus reads the responses. -mattbuck (Talk) 10:27, 13 February 2008 (UTC)

I like how he uses the winning formula of "magazines". "HI HERE'S A HOMEWORK QUESTION FROM A HOMEWORK MAGAZINE" =) --PalaceGuard008 (Talk) 11:06, 13 February 2008 (UTC)

I particularly liked his question about how much someone weighs in a lift which climbs five floors. The carpet was made of broccoli. -mattbuck (Talk) 11:28, 13 February 2008 (UTC)

Predicate logic

I'm not 100% of the "rules" of manipulating predicates but I have this problem and I want to see if I've manipulated it correctly:

R, P, Q are all in the same domain. Use rules of inference and logical equivalence to prove that these premises together lead to a contradiction.

A = $\forall x[(R(x)\lor (\exists yP(y)))\to (\neg Q(x))]$

B = $\exists x[(Q(x)\land R(x))\lor (Q(x)\land \forall yP(y))]$

Starting with A:

1. $\forall x[(R(x)\lor (\exists yP(y)))\to (\neg Q(x))]$ Premise

2. $\forall x[\neg (R(x)\lor (\exists yP(y)))\lor (\neg Q(x))]$ Implication

3. $\forall x[(\neg R(x)\land \neg (\exists yP(y)))\lor (\neg Q(x))]$ Negation

4. $\forall x[(\neg R(x)\land (\forall y\neg P(y)))\lor (\neg Q(x))]$ Negation of existential quant.

Now here comes the bit I'm not sure about:

5. $\forall x[(\neg Q(x)\lor \neg R(x))\land (\neg Q(x)\lor (\forall y\neg P(y)))]$ Distribution on 4, then commutative rearrangement.

Supposing I can distribute as demonstrated in 5., I now have A looking similar to B:

A = $\forall x[(\neg Q(x)\lor \neg R(x))\land (\neg Q(x)\lor (\forall y\neg P(y)))]$

B = $\exists x[(Q(x)\land R(x))\lor (Q(x)\land \forall yP(y))]$

If I have made it thus far with no mistakes, I would like to know where to take this next. I can "see" that these two statements could contradict but I'm unsure how to prove it. If there is an error in my working so far, please let me know! Damien Karras (talk) 08:51, 13 February 2008 (UTC)

All that predicate stuff is making my head spin (I only did the tiniest bit of it), but what happens if you use the definition $\exists xS(x):=\neg \forall x\neg S(x)$ on, say, B, and then bring the second negation throughout the expression? Confusing Manifestation(Say hi!) 11:27, 13 February 2008 (UTC)

Sorry, I know it's hard to follow but I'm trying to do it step by step so that you can see how I arrived at the conclusion. I hope I am right in assuming that if I rearrange B's existential quantifier $\exists x[...]$ to $\neg \forall x\neg [...]$ I will have B as:

$\neg \forall x[(\neg Q(x)\lor \neg R(x))\land (\neg Q(x)\lor \neg (\forall yP(y)))]$

Which is almost the negation of A save for the $\neg (\forall yP(y))$ part! Damien Karras (talk) 12:57, 13 February 2008 (UTC)

I'm not sure how rigorous this is, but it seems to work intuitively, at least, so might help. A implies:

$(\forall x[R(x)\to (\neg Q(x)])\land (\forall x[(\exists yP(y))\to (\neg Q(x))])$

You can then use those implications to substitute into B, getting:

$\exists x[(Q(x)\land (\neg Q(x)))\lor ((\neg (\exists yP(y)))\land \forall yP(y))]$

Which is clearly false. I'm fairly sure that's all true, but I may have missed out a few too many steps by just using intuition... --Tango (talk) 14:43, 13 February 2008 (UTC)

The step you're asking about is correct. You're almost there. You just have to pull the "not" out all the way to the left. When you do, you'll get A as equivalent to precisely notB. Or, to shorten the proof, you could have pulled it out to begin with and rearranged the inside separately. Black Carrot (talk) 18:51, 13 February 2008 (UTC)

If you want to look up the rules, Laws_of_classical_logic has a list of them. Black Carrot (talk) 18:53, 13 February 2008 (UTC)

Yes, when I said "clearly false" I was assuming people could perform that one last manipulation themselves. It's the splitting of the implication and the substitutions that I thought might need to be done in more steps to be completely rigorous. --Tango (talk) 19:32, 13 February 2008 (UTC)

I was talking to the OP. Your solution is good too, though. Black Carrot (talk) 07:17, 14 February 2008 (UTC)

Just to check, this is in reference to the distributive step 5 further back, right? I have to try and extract all those "nots" out of A and I'll get something that looks identical to "not" B? Damien Karras (talk) 08:20, 14 February 2008 (UTC)

That's right. And by definition, the statement "B and notB" is a contradiction. Black Carrot (talk) 07:44, 15 February 2008 (UTC)

Alrighty then, going back to A and B in the equivalent forms:

A = $\forall x[(\neg Q(x)\lor \neg R(x))\land (\neg Q(x)\lor (\forall y\neg P(y)))]$

B = $\exists x[(Q(x)\land R(x))\lor (Q(x)\land \forall yP(y))]$

Now, if I extract the "nots" in A to the left, I have:

A = $\forall x\neg [(Q(x)\land R(x))\lor (Q(x)\land \neg (\forall y\neg P(y)))]$

Going back to the previous point that $\exists x[...]$ is equivalent to $\neg \forall x\neg [...]$, I can write B as:

B = $\neg \forall x\neg [(Q(x)\land R(x))\lor (Q(x)\land (\forall yP(y)))]$

The two statements are almost a contradiction aside from the fact that $\neg (\forall y\neg P(y))$ is not equivalent to $(\forall yP(y))$, correct? Damien Karras (talk) 09:47, 15 February 2008 (UTC)

You're right, sorry. The existential bit doesn't work out quite right. I was thinking of

A = $\neg \exists x[(Q(x)\land R(x))\lor (Q(x)\land \exists yP(y))]$

B = $\exists x[(Q(x)\land R(x))\lor (Q(x)\land \forall yP(y))]$,

but I thought the ends would be the same. You can get a contradiction from this, but it's not as pretty as "B and notB". Since the problem is all the way on the inside, it'll have to be pulled out. Let's do it for B, starting from where I wound up.

B = $\exists x[(Q(x)\land R(x))\lor (Q(x)\land \forall yP(y))]$

B = $\exists x[(Q(x)\land R(x))]\lor \exists x[(Q(x)\land \forall yP(y))]$

B = $\exists x[(Q(x)\land R(x))]\lor [\exists xQ(x)\land \forall yP(y)]$

Then for A,

A = $\neg \exists x[(Q(x)\land R(x))\lor (Q(x)\land \exists yP(y))]$

A = $\neg \exists x[(Q(x)\land R(x))]\land \neg \exists x[(Q(x)\land \exists yP(y))]$

A = $\neg \exists x[(Q(x)\land R(x))]\land [\neg \exists xQ(x)\lor \neg \exists yP(y)]$

A = $\neg \exists x[(Q(x)\land R(x))]\land [\neg \exists xQ(x)\lor \forall y\neg P(y)]$.

From here, I think it's easiest to combine the two. Since the original assumption is A AND B, that's not hard to do. A AND B = C,

C = $\neg \exists x[(Q(x)\land R(x))]\land [\neg \exists xQ(x)\lor \forall y\neg P(y)]\land {\bigg (}\exists x[(Q(x)\land R(x))]\lor [\exists xQ(x)\land \forall yP(y)]{\bigg )}$.

Commute and distribute, to get

C = $[\neg \exists xQ(x)\lor \forall y\neg P(y)]\land {\Bigg (}{\bigg (}\neg \exists x[(Q(x)\land R(x))]\land \exists x[(Q(x)\land R(x))]{\bigg )}\lor {\bigg (}\neg \exists x[(Q(x)\land R(x))]\land [\exists xQ(x)\land \forall yP(y)]{\bigg )}{\Bigg )}$

Since that bit towards the middle is a contradiction in its proper form, it's automatically equal to False, and since it's one side of an OR, the other side absorbs it.

C = $[\neg \exists xQ(x)\lor \forall y\neg P(y)]\land {\bigg (}\neg \exists x[(Q(x)\land R(x))]\land [\exists xQ(x)\land \forall yP(y)]{\bigg )}$

C = $[\neg \exists xQ(x)\lor \forall y\neg P(y)]\land \neg \exists x[(Q(x)\land R(x))]\land \exists xQ(x)\land \forall yP(y)$

I commute and distribute the exists-Q bit the same as the previous bit, and get

C = $\exists xQ(x)\land \forall y\neg P(y)\land \neg \exists x[(Q(x)\land R(x))]\land \forall yP(y)$

Commute,

C = ${\bigg (}\exists xQ(x)\land \neg \exists x[(Q(x)\land R(x))]{\bigg )}\land {\bigg (}\forall yP(y)\land \forall y\neg P(y){\bigg )}$

As long as there's a y in the universe to act on, the right side is false, so the entire thing is false, and equivalent to a contradiction. That's not quite the same as saying it is a contradiction, since there's nothing to stop y from ranging over an empty set, but they probably want that case excluded. Black Carrot (talk) 04:13, 16 February 2008 (UTC)

On the other hand, if the universe is empty, then the left side is false instead. So I guess it works. I can't figure out how to get an actual contradiction-type contradiction, though, and I'm not certain it's possible with formal manipulations. Black Carrot (talk) 04:56, 16 February 2008 (UTC)