Infinite set, disjunction, and tautology

In summary, the conversation discussed the existence of a fixed number m such that A1 \vee A2 \vee ... \vee Am is a tautology, given an infinite set of formulas in propositional logic and the fact that for every valuation, there exists some n where v(An) = 1. The conversation also suggests considering a set of formulas and their valuations as infinite binary sequences in order to prove the existence of m.
  • #1
iambored
1
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
  • #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.
 

FAQ: Infinite set, disjunction, and tautology

What is an infinite set?

An infinite set is a set that has an infinite number of elements. This means that the elements in the set cannot be counted or listed. Some examples of infinite sets include the set of natural numbers, integers, and real numbers.

What is disjunction?

Disjunction is a logical operation that combines two or more propositions to form a new proposition. It is often denoted by the symbol "∨" and is read as "or". In a disjunction, at least one of the propositions must be true for the entire statement to be true.

What is a tautology?

A tautology is a logical statement that is always true, regardless of the truth values of its individual components. In other words, a tautology is a statement that is true by definition. An example of a tautology is "either it is raining or it is not raining".

How are infinite sets represented in mathematics?

Infinite sets are often represented using set-builder notation, which is a concise way of describing a set by stating its defining properties. For example, the set of even numbers can be represented as {x | x is an integer and x is divisible by 2}.

How do disjunction and tautology relate to each other?

Disjunction and tautology are related in that a tautology can be considered a special case of disjunction. This is because every tautology can be expressed as a disjunction of propositions, where all of the propositions are true. In other words, a tautology is a disjunction that is always true.

Back
Top