Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 Help Me ! » Use Extreme Value Theorem » 2010-10-02 08:07:11

cxc001
Replies: 1

Suppose f:[0,1]->R is continuous, f(0)>0, f(1)=0.
Prove that there is a X0 in (0,1] such that f(Xo)=0 & f(X) >0 for 0<=X<Xo (there is a smallest point in the interval [0,1] which f attains 0)

Since f is continuous, then there exist a sequence Xn converges to X0, and f(Xn) converges to f(Xo).
Since 0<=(Xo-1/n)<Xo
Can I just let Xn=Xo-1/n so that 0<=Xn<Xo
So when Xn->Xo, f(Xn)->f(Xo)

I wasn't convinced enough this is the right approach...

#2 Help Me ! » Prove G contains a cycle of length at least k+1 » 2010-09-29 12:29:24

cxc001
Replies: 0

This is a graph theory related question.

Let G be a simple graph with min. degree k, where k>=2. Prove that G contains a cycle of length at least k+1.

Am I suppose to use induction to prove G has a path length at least k first, then try to prove that G has a cycle of length at least k+1? Or should I go directly use induction to prove G contains a cycle of length at least k+1???

#3 Help Me ! » Graph Theory - bipartite related proof » 2010-09-15 05:16:58

cxc001
Replies: 1

How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4?

Definition of bipartite graph:  a graph whose vertex-set can be partitioned into two subsets such that every edge has one endpoint in one part and one endpoint in the other part.

I try to use induction to prove this problem.

Let n:  represents the total # of vertices in a simple bipartite graph (n in positive integer)
Let P(n) = [n^2/4]:  represents the max # of edges a simple bipartite graph can have in positive integer

Proof:

Test
n = 0, P(n) = [0^2/4] = 0 (null vertex is trivial)
n = 1, P(n) = [1^2/4] = 0 (I don’t think 1 vertex can have a simple bipartite graph)
n = 2, P(n) = [2^2/4] = 1 ok
n = 3, P(n) = [3^2/4] = 2 ok
n = 4, P(n) = [4^2/4] = 4 ok

So let n>=4
Assume that P(n-1) = [(n-1)^2/4] is true for all n >=4
Prove that P(n) = [n^2/4] is true

How to prove P(n) = [n^2/4] is true?

#5 Help Me ! » Convergence of Sequence "Does {An^2} converges => {An} converges? » 2010-09-08 08:44:36

cxc001
Replies: 2

Does sequence {An^2} converges implies to sequence {An} converges?  True or False.  How to prove it?

I kinda think it is false, but couldn’t think of any counterexample to directly proof it.  So I try to use the 1) definition of convergence and 2) the Comparison Lemma to prove it, but kinda stucked.

Proof1:  (Use definition of convergence)
Let sequence An^2 converges to a^2
Then according to the definition of convergence
For every E>0, Find N such that
|An^2-a^2|<E for all n>N
|(An-a)(An+a)|=|An-a||An+a|<E
|An-a|<E/|An+a|)

How can I go from here?

So if I can let N=E/|An+a|+1, then An converges to a.  But I can’t define N that has a sequence in it, can I?

Comparison Lemma states “Let sequence {An} converges to a, and let {Bn} be a sequence such that |Bn-b|<= C|An-a| for some C>0, then Bn converges to b”

Proof2:  (Use Comparison Lemma)
Let sequence An^2 converges to n^2
Let {An} be a sequence such that |An-a|<=C|An^2-a^2| for some C>0
Now I need to find an C>0 so that I can prove that sequence An converges to a

How can I go from here?

#7 Re: Help Me ! » Set Theory: Prove the set of complex numbers is uncountable » 2010-04-19 07:19:38

Yes, R (set of all real no.) is a subset of C (set of all complex no.)
R={a+0i: a is real no}, C={a+bi: a,b are real no}
R is uncountable, therefore C is also uncountable

#8 Help Me ! » Cardinalities of Sets: Prove |(0, 1)| = |(0, 2)| and |(0, 1)| = |(a, b » 2010-04-18 17:54:17

cxc001
Replies: 2

How to prove the open intervals (0,1) and (0,2) have the same cardinalities? |(0, 1)| = |(0, 2)|

Let a, b be real numbers, where a<b.  Prove that |(0, 1)| = |(a, b)|

-----------------------------------
|(0,1)| = |R| = c by Theorem
-----------------------------------

I know that we need to construct a function f: (0,1)->(0,2) and prove f is bijection so that |(0, 1)| = |(0, 2)|

same process of proving |(0, 1)| = |(a, b)|

but how to construct a function f: (0,1)->(0,2)
and how to construct a function g: (0,1)->(a,b) where a<b and a,b are real numbers?

I know how to construct a function f: (0,1)->R
by define a function f(x)=(1-2x)/[x(x-1)] where x cannot be 0 and 1 and when the middle domain(f)=1/2, f(1/2)=0

How can I expand this knowledge and to define a function that the domain(f) is within (0,1) and the range(f) falls into (0,2) or any close interval (a,b)?

#9 Help Me ! » Set Theory: Prove the set of complex numbers is uncountable » 2010-04-18 17:52:38

cxc001
Replies: 2

How to prove the set of complex numbers is uncountable?

Let C be the set of all complex numbers,
So C={a+bi: a,b belongs to N; i=sqrt(-1)}

--------------------------------------------------
set of all real numbers is uncountable                           
open intervals are uncountable             
set of all irrational numbers is uncountable
--------------------------------------------------

#10 Re: Help Me ! » Prove set S is countable iff there exists a surjective/injective funct » 2010-04-11 17:33:17

Thanks both!

Yes, NOT all countable sets are of the same cardinality.

A set is countable if it is either finite or denumerable
1)  Two finite countable sets are not necessarily of the same cardinality
2)  Every two denumerable sets are of the same cardinality.

Set S is denumerable if there is a bijection f:N->S

So S could be either nonempty finite set or denumerable set
1)  If S is nonempty finite set, then we need to construct a surjection f:N->S where |N|>|S|, and construct an injection g:S->N such that |S|<|N|

I had an earlier post of asking how to prove the |S|<|N|, set S is a nonempty finite set, which means |S|=n, and the elements of S can be listed as S={s1, s2, ... ,Sn}, construct a function f:S->N to be injection where |S|<|N| but NOT surjection where |S|>|N|

2)  If S is denumerable set, since the cardinality of natural number is denumerable by Theorem, then |S|=|N|, so f:N->S would be bijection and the inverse of f donated by g:S->N would be bijection as well

Should I be doing both cases???  It make more sense to assume that set S is nonempty finite set right?

#12 Re: Help Me ! » Prove set S is countable iff there exists a surjective/injective funct » 2010-04-10 18:12:54

Oh my bet, I should have used the set S instead of A.  So how do I construct the bijective function f:N->S correctly then?

#13 Re: Help Me ! » Prove set S is countable iff there exists a surjective/injective funct » 2010-04-10 17:35:40

Okay, here is what I got so far.

There should be two steps that I need to prove to show |S|<|N|
step 1) to construct a injective function f:S->N
step 2) to prove the function f:S->N is NOT bijection (mainly NOT surjective function)

Step 1) I started with trying to contrust a injection f:S->N
Since S is finite nonempty set, then the elments of set S can be listed as S={s1, s2, s3,...,sn), and |S|=n
Since N is denumerable set by theorem (countable infinite set), then N={1, 2, 3,...,n,...}
Let f(s1)=1, f(s2)=2,...,f(sn)=n
In order to show the function is injecitive, I have to show two different elements have two different images which is if f(x)=f(y), then x=y (use proof by contrapositive method)
So Let f(x)=f(y), I need to show that x=y
[This is where I stucked, how should I go from there?]

For step 2) to prove the function f:S->N is NOT bijection (mainly NOT surjective function) seems quite complicated!
[I attemped to use the proof by contradiction first]
Assume by contradiction that there exists a bijective function f:S->N
[Then how I go from there? This is where I stucked again!]

#14 Help Me ! » Prove set S is countable iff there exists a surjective/injective funct » 2010-04-10 17:15:33

cxc001
Replies: 8

Question
(a) A nonempty set S is countable if and only if there exists surjective function f:N->S
(b) A nonempty set S is countable if and only if there exists a injective function g:S->N

In either case (a) or (b) |S|<|N| in order for surjective function f: N->S and injective function g:S->N to exist.  Do I need to prove |S|<|N|, cardinality of an countable set is less then the cardinality of natural number???  If so, how to prove it?  Well, I know that I need to construct a injective function f:S->N and show that the function is NOT bijective (mainly surjective since it needs to be injective)

There are two way proves for both (a) and (b)
(a-1) prove if a nonempty set S is countable, then there exists surjective function g:S->N;  (a-2) also prove if there exists surjective function g:S->N, then a nonempty set S is countable

(b-1) prove if a nonempty set S is countable, then there exists a injective function g:S->N;  (b-2) also prove if there exists a injective function g:S->N, then a nonempty set S is countable

How to proceed in detail if it's not such a hassle for those of you to show me?  It would be greatly appreciated!

#15 Help Me ! » Cardinality Problem: Prove |A| < |N| » 2010-04-10 16:03:12

cxc001
Replies: 2

Prove cardinality of every finite nonempty set A is less then cardinality of natural number N
|A|<|N|

set A is nonempty finite set
natural number N is denumerable (infinite countable set)

|A|<|N| if there exist a injective (one-to-one) function f: A->N, but NO bijective function, which means NO surjective (onto) function

How to prove it in detail???

Help please!!!

#16 Help Me ! » Function related Problem » 2010-04-09 15:37:53

cxc001
Replies: 1

Problem: Let function f:R->R defined by f(x)=x^2+3x+4

(a) Show f is NOT bijective(one-to-one/onto) {I got this one!)

(b) Find all pairs r1, r2 of real numbers such that f(r1)=f(r2)
Solve: Let f(r1)=f(r2), then r1^2+3r1+4=r2^2+3r2+4, r1^2-r2^2+3r1-3r2=0, (r1-r2)(r1+r2)+3(r1-r2)=0, (r1-r2)(r1+r2+3)=0, so r1=r2 or r1=-r2-3
It's a parabola graph, and symmetric at line x=-3/2, the lowest point of the parabola graph is at (-3/2, 7/4), only at the lowest point (-3/2, 7/4) of the graph r1=r2=-3/2, r1=-r2-3 for all the rest of the points on the graph. Am I explaining it or concluding it correctly?
[I don't know whether how I conclude is correct or not. Need assistant on this one!!! Is there any better way to state it more professionally???]

(c) Find the set S of all real numbers such that if s belongs to S, then there is no real number x such that f(x)=s
Solve: Let f(x)=s and solve for x, then x^2+3x+4=s, so x=(+/-)1/2sqrt(4s-7)-3/2, when s<7/4 there is no real number solution for x,
therfore the set S={s belongs to R: s<7/4} [Is my conclusion correct???]

(d) What well-known set is the set S in (c) related to?
[How to answer this one? I highly doubt my answer is correct!!!]
The set S in (c) is related to the range(f)???

Please Help!

Board footer

Powered by FluxBB