Infinite set, disjunction, and tautology

  • Context: Graduate 
  • Thread starter Thread starter iambored
  • Start date Start date
  • Tags Tags
    Infinite Set
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 3K views
iambored
Messages
1
Reaction score
0
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.
 
Physics news on Phys.org
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.