Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Consistent Families

  1. Feb 26, 2008 #1
    I define a consistent family, F, to be a set of intervals such that if I_1 and I_2 are in F then I_1 and I_2 intersect

    Now given two families F and G, we say F is consistent with G provided that each interval from F intersects with each interval from family G.

    My question:
    If you know that F is consistent with G, does this imply that either F or G is consistent itself?

    My gut feeling is that if F is consistent with G then at either F OR G must be consistent..
     
  2. jcsd
  3. Feb 26, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Suppose F is a family of vertical intervals from (x, 1) to (x, -1) with x between -1 and 1 and G is a family of horizontal intervals from (1, y) to (-1, y) with y between -1 and 1.
     
  4. Feb 26, 2008 #3
    Hey Halls,
    Great counterexample!

    I am working in a book that is constructing the real number system through these intervals. As such, I have been strictly thinking of these rational intervals as one dimensional along the real number line.

    If we restrict ourselves to the real number line then is my assertion true?
     
  5. Feb 26, 2008 #4
    Wee, I'd say, yes:smile:

    Proof: edited...proof wrong
     
    Last edited: Feb 26, 2008
  6. Feb 26, 2008 #5
    There must be something wrong Pere...
    If I am reading your proof correctly you are asserting that both F and G are BOTH consistent. However consider F the family {(1,5), (6,10)} and G the family {(3,7), (2, 8)} Here F is consistent with G because each interval in F intersects each interval in G, however F is not consistent.
     
  7. Feb 26, 2008 #6
    You're right, my "proof" was dead wrong, gee .... I'll think of sth. else

    Next try:

    Assume F is consistent with G but neither F nor G is consistent. Clearly, F and G contain more than one interval, otherwise they would be consistent.
    For two intervals v,w write v<w if [itex]\forall x\in v, \forall y\in w: x<w[/itex]. Our inconsistency assumption allows us to pick [itex]f_1, f_2[/itex] from F and [itex]g_1,g_2[/itex] from G such that

    [tex]f_1\cap f_2 = \emptyset[/tex]
    and
    [tex]g_1\cap g_2 = \emptyset[/tex]

    w.l.o.g. we take [itex]f_1<f_2[/itex] and [itex]g_1<g_2[/itex]. (If neither [itex]f_1<f_2[/itex] nor [itex]f_2<f_1[/itex] were true, there would be [itex]x, x' \in f_1,\quad y,y'\in f_2[/itex] such that x<y and x'>y'; this implies that the number
    [tex]
    t=\frac{y'(x-y)-y(x'-y')}{(x-y)-(x'-y')}
    [/tex]
    lies between x and x' as well as between y and y'.(I omit the calculation, it is rather obvious that one of two non-intersecting intervals has to be greater than the other one) Hence [itex]t\in f_1 \cap f_2[/itex] which is a contradiction.

    F being consistent with G implies


    [tex]f_1\cap g_2 :=h_2 \neq \emptyset[/tex]
    [tex]f_2\cap g_1 :=h_3 \neq \emptyset[/tex]

    Choose

    [tex]x\in h_2,\quad y\in h_3[/tex]

    There are now two cases:

    Case 1: x<=y: Since [itex]x \in g_2[/itex] and [itex]y \in g_1[/itex] this is a contradiction to our assumption [itex]g_1<g_2[/itex].

    Case 2: x>y: Since [itex]x \in f_1[/itex] and [itex]y \in f_2[/itex] this is a contradiction to our assumption [itex]f_1<f_2[/itex].

    Hence, if F is consistent with G, either F or G or both have to be consistent.
     
    Last edited: Feb 27, 2008
  8. Feb 28, 2008 #7
    Any objections to this proof?:smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?