Infinite set, disjunction, and tautology

  • Context: Graduate 
  • Thread starter Thread starter iambored
  • Start date Start date
  • Tags Tags
    Infinite Set
Click For Summary
SUMMARY

The discussion focuses on the properties of infinite sets of formulas in propositional logic, specifically addressing the scenario where for every valuation v, there exists an n such that v(An) = 1. It concludes that there exists a fixed m such that the disjunction A1 ∨ A2 ∨ ... ∨ Am is a tautology. This is demonstrated by assuming that none of the elements in the set {A1, A1 ∨ A2, A1 ∨ A2 ∨ A3, ...} are tautologies, leading to a contradiction. The identification of valuations with infinite binary sequences is also noted as a key concept in the proof.

PREREQUISITES
  • Understanding of propositional logic and tautologies
  • Familiarity with infinite sets and their properties
  • Knowledge of valuations in logic
  • Basic concepts of disjunction in logical expressions
NEXT STEPS
  • Study the concept of tautologies in propositional logic
  • Explore the properties of infinite sets in mathematical logic
  • Learn about valuations and their role in propositional logic
  • Investigate the implications of disjunctions in logical expressions
USEFUL FOR

Logicians, mathematicians, and students of formal logic who are interested in the properties of infinite sets and their implications in propositional logic.

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.
 

Similar threads

Undergrad Thinking about equality of infinite sets
  • · Replies 5 ·
Replies
5
Views
3K
MHB Testing the Properties of a Relation on Nonnegative Real Triples
  • · Replies 2 ·
Replies
2
Views
2K
High School The Paradox of 1 – 1 + 1 – 1 + 1 – 1 + …
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Intersection of sets with infinite number of elements
  • · Replies 3 ·
Replies
3
Views
8K
Graduate Undergraduate mathematical logic questions
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Formal axiom systems and the finite/infinite sets
  • · Replies 10 ·
Replies
10
Views
2K
Is There an Infinite Set Smaller Than the Natural Numbers?
  • · Replies 2 ·
Replies
2
Views
4K
Graduate Somewhat difficult set theory proof
  • · Replies 6 ·
Replies
6
Views
2K
High School Unbounded Logical Trees: Constructing Natural Numbers with Logical Trees
  • · Replies 7 ·
Replies
7
Views
2K
MHB Partial Order Relation where the Set is not Necessarily Finite
  • · Replies 6 ·
Replies
6
Views
3K