Collection of Well-Formed Formulas with no Equivalent, Independent Subset

Click For Summary
SUMMARY

The discussion centers on constructing a collection of well-formed formulas, denoted as Ʃ, that lacks an independent equivalent subset. The user initially identifies that Ʃ must be infinite and later proposes a specific construction: Ʃ = {A₁, A₁ ∧ A₂, ..., A₁ ∧ ... ∧ Aₙ, ...}. This formulation effectively demonstrates the required properties of Ʃ, confirming its validity in the context of logical frameworks.

PREREQUISITES
  • Understanding of well-formed formulas in propositional logic
  • Familiarity with logical conjunction (∧) and its properties
  • Basic knowledge of infinite sets and their implications in logic
  • Experience with logical equivalence and independent subsets
NEXT STEPS
  • Explore the concept of independent sets in propositional logic
  • Study the properties of infinite collections of well-formed formulas
  • Learn about logical equivalence and its applications in formal proofs
  • Investigate advanced topics in propositional logic, such as completeness and consistency
USEFUL FOR

Students of mathematical logic, researchers in formal systems, and anyone interested in the foundations of propositional logic and its applications in theoretical computer science.

jgens
Gold Member
Messages
1,575
Reaction score
50

Homework Statement



Find a collection of well-formed formulas Ʃ such that Ʃ has no independent equivalent subset.

Homework Equations



N/A

The Attempt at a Solution



So far I have been able to show that Ʃ must be infinite. However, after this, I get stuck. Could anyone give me a hint on how to construct such a Ʃ?

Thanks!
 
Physics news on Phys.org
I figured it out. If we take \Sigma = \{A_1, A_1 \wedge A_2, \dots, A_1 \wedge \cdots \wedge A_n, \dots\}, then that should work.
 

Similar threads

Proper form for geometric series with a neg inside
  • · Replies 4 ·
Replies
4
Views
2K
Isomorphisms preserve linear independence
  • · Replies 2 ·
Replies
2
Views
2K
What is the correct Fourier Series for f(x) = sinx on the interval 0 < x < ∏?
  • · Replies 2 ·
Replies
2
Views
2K
Probability Theory: Poisson Distribution
  • · Replies 3 ·
Replies
3
Views
2K
Taylor Series for Complex Variables
  • · Replies 2 ·
Replies
2
Views
2K
Hard infinite series converges problem (Real Analysis)
  • · Replies 7 ·
Replies
7
Views
2K
Linear Independence of a Set of Vectors
  • · Replies 6 ·
Replies
6
Views
2K
Proving Trace Independence in Linear Algebra Homework
  • · Replies 1 ·
Replies
1
Views
1K
Can Ʃ (anbn) be divergent if Ʃan and Ʃbn are both convergent?
  • · Replies 1 ·
Replies
1
Views
1K
Complex Analysis - Radius of convergence of a Taylor series
  • · Replies 2 ·
Replies
2
Views
3K