Math Help Forum - Discrete Mathematics, Set Theory and Logic http://www.mathhelpforum.com/math-help en Fri, 20 Nov 2009 22:48:01 GMT vBulletin 60 http://www.mathhelpforum.com/math-help/images/MHF/misc/rss.jpg Math Help Forum - Discrete Mathematics, Set Theory and Logic http://www.mathhelpforum.com/math-help Find the last digit http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115788-find-last-digit.html Fri, 20 Nov 2009 20:51:08 GMT Find the last digit of 541^(341). Clearly, the last digit would be one, but I don't know how to go about showing that it would be one. Can someone help please? ]]> Discrete Mathematics, Set Theory and Logic steph3824 http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115788-find-last-digit.html Delta-System Lemma counterexample http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115751-delta-system-lemma-counterexample.html Fri, 20 Nov 2009 16:42:54 GMT \kappa be a regular cardinal such that \forall \alpha < \theta \ (|\alpha^{< \kappa}| < \theta); given A such that |A| \geq \theta and \forall x \in A \ (|x| < \kappa), then there is a B \subset A which...]]> The \Delta-system lemma states the following: given an infinite cardinal \kappa, let \theta > \kappa be a regular cardinal such that \forall \alpha < \theta \ (|\alpha^{< \kappa}| < \theta); given A such that |A| \geq \theta and \forall x \in A \ (|x| < \kappa), then there is a B \subset A which forms a \Delta-system, such that |B| = \theta.

I wish to find a counterexample if \kappa is not regular. For example, I wish to prove that there is a family A with |A| = \omega_\omega and \forall x \in A \ (|x| < \omega) such that no B \subset A (with |B| = \omega_\omega) is a \Delta-system.

Every help is appreciated. Thanks. ]]> Discrete Mathematics, Set Theory and Logic eurialo http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115751-delta-system-lemma-counterexample.html quick question http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115741-quick-question.html Fri, 20 Nov 2009 15:05:54 GMT how could this one (-3)(2)^{n-1} + 2^n(-1) simplify to -2^{n+2}+3? how could this one (-3)(2)^{n-1} + 2^n(-1) simplify to -2^{n+2}+3? ]]> Discrete Mathematics, Set Theory and Logic zpwnchen http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115741-quick-question.html Troubles with Quantificational Logic http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115715-troubles-quantificational-logic.html Fri, 20 Nov 2009 10:43:45 GMT I am having troubles converting some natural language sentences into quantificational statements. Any help would be greatly appreciated. 1) The best is better than the worst (Fxy - x is better than y) 2) Everyone loves a lover (Fx - x is a person, Gxy - x loves y) 3) The God who begat... I am having troubles converting some natural language sentences into quantificational statements. Any help would be greatly appreciated.

1) The best is better than the worst (Fxy - x is better than y)

2) Everyone loves a lover (Fx - x is a person, Gxy - x loves y)

3) The God who begat Polyphemus begets only cyclopes. (Bxy - x begets y, Gx - x is a God, Cx - x is a cyclops, m - Polyphemus

4) No two crooks are equally rich (Cx - x is a crook, Rxy - x is richer than y) ]]> Discrete Mathematics, Set Theory and Logic Haven http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115715-troubles-quantificational-logic.html problem to prove based on mathematical induction http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115705-problem-prove-based-mathematical-induction.html Fri, 20 Nov 2009 08:30:05 GMT Please give me the answer for the below question. prove that (2 pow n . 2 pow n) - 1 is divisible by 3 by mathematical induction. Please give me the answer for the below question.

prove that (2 pow n . 2 pow n) - 1 is divisible by 3 by mathematical induction. ]]> Discrete Mathematics, Set Theory and Logic sudeepmansh http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115705-problem-prove-based-mathematical-induction.html permutation question http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115689-permutation-question.html Fri, 20 Nov 2009 04:13:21 GMT In how many ways can 5 different trees be planted in a circle. The answer is 24. I would think that it should be 5! but instead it is 4!? Does anyone understand this problem? In how many ways can 5 different trees be planted in a circle.
The answer is 24. I would think that it should be 5! but instead it is 4!? Does anyone understand this problem? ]]> Discrete Mathematics, Set Theory and Logic modeselect http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115689-permutation-question.html Stuck on Simple Inductive Proof http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115667-stuck-simple-inductive-proof.html Fri, 20 Nov 2009 02:24:08 GMT Show that for all n \geq 0, 3^{2n}+4^{n+1} is a mulitple of 5 using an inductive proof. I think that I have started this right but I am not sure if it is complete or correct. 1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5 2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5, p(n+1) =... Show that for all n \geq 0,
3^{2n}+4^{n+1} is a mulitple of 5 using an inductive proof.

I think that I have started this right but I am not sure if it is complete or correct.

1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5
2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5,
p(n+1) = p(n)+3^{2(n+1)}+4^{(n+1)+1}
= 3^{2n}+4^{n+1}+3^{2n+2}+4^{n+2}
= 3^{2n}+4^{n+1}+3^{2n}(9)+4^{n+1}(4)
= 3^{2n}(1+9)+4^{n+1}(1+4) \ by \ factoring
= 3^{2n}(10)+4^{n+1}(5)

So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated. ]]> Discrete Mathematics, Set Theory and Logic b.rad http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115667-stuck-simple-inductive-proof.html sentential logic derivations? http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115618-sentential-logic-derivations.html Thu, 19 Nov 2009 20:06:04 GMT B)->A]->A ... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck :( and also: Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism...]]> how do i prove the following is a theorem in SD
[(A -> B)->A]->A
... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck :(

and also:

Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
you can derive the SD rule for vE in SD.

I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks! :D ]]> Discrete Mathematics, Set Theory and Logic cosmopolitanx http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115618-sentential-logic-derivations.html Chinese remainder theorem 2 http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115585-chinese-remainder-theorem-2-a.html Thu, 19 Nov 2009 16:35:42 GMT Find all solutions, if any, to the system of congruences x \equiv 7 (mod 9) x \equiv 4 (mod 12) x \equiv 16 (mod 21) Solution manual states: We cannot apply the CRT directly, since the moduli are not pairwise relatively prime. (Got that on my own.) However, we can, using the CRT, translate... Find all solutions, if any, to the system of congruences
x \equiv 7 (mod 9)
x \equiv 4 (mod 12)
x \equiv 16 (mod 21)

Solution manual states: We cannot apply the CRT directly, since the moduli are not pairwise relatively prime. (Got that on my own.) However, we can, using the CRT, translate these congruences into a set of congruences that together are equivalent to the given congruence. Since, we want x \equiv 4 (mod 12), we must have x \equiv 4 \equiv 1 (mod 3) and x \equiv 4 \equiv 0 (mod 4).

First question, how do we convert congruences? I can see that dividing the 4 and 12 by 4 could give 1 (mod 3), is that the correct procedure? But I don't see how that equates to 0 (mod 4), could you help me there?

Similarly, from the third congruence we must have x \equiv 1 (mod 3) and x \equiv 2 (mod 7). Why?

From here I think I can solve the following system with the excellent help I've received previously.

x \equiv 7 (mod 9)
x \equiv 0 (mod 4)
x \equiv 2 (mod 7).

Thanks for any explanations. ]]> Discrete Mathematics, Set Theory and Logic oldguynewstudent http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115585-chinese-remainder-theorem-2-a.html Need help with a proof dealing with functions http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115583-need-help-proof-dealing-functions.html Thu, 19 Nov 2009 16:10:05 GMT B be a function. Prove that f is surjective if and only if f^(-1)(W) does not equal the empty set for all nonempty sets W of B. I really do not know what to do with this. Thanks for your help everyone]]> Let f:A--->B be a function. Prove that f is surjective if and only if f^(-1)(W) does not equal the empty set for all nonempty sets W of B.

I really do not know what to do with this. Thanks for your help everyone ]]> Discrete Mathematics, Set Theory and Logic steph3824 http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115583-need-help-proof-dealing-functions.html Ordinal Arithmetic http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115576-ordinal-arithmetic.html Thu, 19 Nov 2009 15:27:42 GMT I have a question here on ordinal arithmetic: Suppose \alpha + \beta = \omega (\alpha, \beta not zero). What are \alpha \beta , \alpha^\beta? Am I right in assuming that the sum of two finite ordinals cannot be an infinite ordinal? If so I figure \beta = \omega and \alpha can just be any finite... I have a question here on ordinal arithmetic: Suppose \alpha + \beta = \omega (\alpha, \beta not zero). What are \alpha \beta , \alpha^\beta?

Am I right in assuming that the sum of two finite ordinals cannot be an infinite ordinal? If so I figure \beta = \omega and \alpha can just be any finite ordinal. So \alpha \beta = \omega and \alpha^\beta = \omega (by two rules in my notes).

Alpha and beta cannot be the other way round as right cancellation does not work.

So I think this proof is sound if the first statement is true. If anyone can comment on what I've done that'd be neat. ]]> Discrete Mathematics, Set Theory and Logic whatisthisfor http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115576-ordinal-arithmetic.html my first problem http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115564-my-first-problem.html Thu, 19 Nov 2009 14:33:58 GMT let a1,a2,...........,an be n nubers such that each ai is either 1 or -1.if a1a2a3a4+a2a3a4a5+........+ana1a2a3=0, prove that 4 divides n pls give me a solution let a1,a2,...........,an be n nubers such that each ai is either 1 or -1.if a1a2a3a4+a2a3a4a5+........+ana1a2a3=0,
prove that 4 divides n


pls give me a solution ]]> Discrete Mathematics, Set Theory and Logic arjun sengupta http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115564-my-first-problem.html problem on inclusion exclusion http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115559-problem-inclusion-exclusion.html Thu, 19 Nov 2009 13:40:47 GMT Please describe the way to find the answer for the following question. This problem is based on inclusion exclusion principle 50 cars were assembled in a factory. The options available were radio, AC, power steering. It is known that 20 of the cars have radios, 12 of them have AC and 10... Please describe the way to find the answer for the following question.

This problem is based on inclusion exclusion principle

50 cars were assembled in a factory. The options available were radio, AC,
power steering. It is known that 20 of the cars have radios, 12 of them have
AC and 10 of them have power steerings. 5 of them have all three options.
Determine at least how many cars do not have any options at all. ]]> Discrete Mathematics, Set Theory and Logic sudeepmansh http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115559-problem-inclusion-exclusion.html Points in a plane. http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115512-points-plane.html Thu, 19 Nov 2009 05:14:57 GMT These are based on a similar problem on this forum
http://www.mathhelpforum.com/math-he...principal.html

1. Let there be 'some' points in a plane such that distance between any two them is < 1. What is the minimum area/shape which can inscribe all these points?

2. You grab an area by putting infinite points on a plane. Only condition - any two points you put should be <1 apart. What is the maximum area you can grab?

Any pointers? I think I know the answer but am struggling to justify it.

Thanks ]]> Discrete Mathematics, Set Theory and Logic aman_cc http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115512-points-plane.html Show that pos int divisible by 3 iff sum of digits divisible by 3 http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115509-show-pos-int-divisible-3-iff-sum-digits-divisible-3-a.html Thu, 19 Nov 2009 04:48:53 GMT Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3.

This is from Rosen but I can't follow the proof in the solutions manual (again). Section 3.6 problem 29.

Please explain the detail so I'll understand the whole process. ]]> Discrete Mathematics, Set Theory and Logic oldguynewstudent http://www.mathhelpforum.com/math-help/discrete-mathematics-set-theory-logic/115509-show-pos-int-divisible-3-iff-sum-digits-divisible-3-a.html