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

Infinite set, disjunction, and tautology

  1. Apr 18, 2010 #1
    Let {A1, A2, A3, ... } be an in finite set of formulas in propositional logic. Assume that
    for every valuation v there is some n (depending on v) such that v(An) = 1. Show
    then that there is some fixed m with A1 [tex]\vee[/tex] A2 [tex]\vee[/tex] ... [tex]\vee[/tex] Am a tautology.

    This is equivalent to showing that v(Ai) = 1 for at least one 1[tex]\leq[/tex]i[tex]\leq[/tex]m. But I'm not sure where to proceed from here.
  2. jcsd
  3. Apr 19, 2010 #2
    Start by considering the set [itex]\left\{A_1,A_1\vee A_2,A_1\vee A_2 \vee A_3\cdots\right\}[/itex] and assume that none of its elements is a tautology. Note also that any valuation may be identified with an infinite binary sequence.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook