0
votes
0answers
22 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
1
vote
1answer
68 views

What is the point of (Compactness Theorem in the) Overspill Principle?

I am trying to understand the basics of computation theory. The Overspill Principle (also at google) basically says if you are cool you can do everything Let Г be a sentence of predicate logic ...
6
votes
1answer
194 views

New Axioms of Infinity

Axiom of Infinity says there is an inductive set (i.e. a set which includes $\emptyset$ and is closed under successor operator). Formally: $Inf:\exists x~(\emptyset\in x~\wedge~\forall y\in ...
2
votes
3answers
72 views

Can an infinite set be transitive, irreflexive, total, and have an upper and lower bound?

I need an infinite structure that can be put into an order with the following properties: The order must... be transitive, be irreflexive, be total (i.e., every two things share some sort of ...
0
votes
1answer
68 views

Countable and Uncountable sets

Is $\mathbb{N}\cup\{a\}$, for some $a\not\in\mathbb{N}$ countable or uncountable? $\mathbf{Attempt: }$ It is true that a set is countable if there exists an injective function $f : S → N$ from $S$ to ...
2
votes
2answers
109 views

How can we define infinitary proofs?

In the first order logic the usual notion of a formal proof for a sentence $\sigma$ from a theory $T$ is a "finite" sequence ($<\omega$ - sequeance) of sentences which each one of them is a valid ...
4
votes
1answer
61 views

Generlized Büchi Games and Closed under superset Muller Games

For a unique infinite play $p$ in a 2-Player game $G=(V_0,V_1,E)$. Let $$ \inf(p) \subseteq V_0 \cup V_1 $$ be the set of vertices which occur infinitly often in $p$. Generlized Büchi (GB) Games ...
2
votes
1answer
50 views

Statements true for all n Vs. statements true as n->infty

Let P be a statement. What are the necessary and sufficient conditions for the following statement to be true? (P is true $\forall n \in \Bbb N$)$\implies$(P is true as n$\to \infty$) As background ...
7
votes
6answers
1k views

Why accept the axiom of infinity?

According to my readings, Russell showed that a principle Frege used to reduce Peano arithmetic to logic lead to a contradiction. So, Russell tried to reduce mathematics to logic a different way but ...
1
vote
1answer
127 views

Can the ongoing need for a meta language be stopped by a loop?

As an afterthought to this question on sets in set theory, and more specifically to the observation that a (first-order) logic requires a meta-language to explain itself (i.e. there is already an ...
3
votes
1answer
277 views

What does universal quantification mean?

In ZFC, for example, there is no universal set, so what does it mean to write $\forall x (\cdots)$, i.e., for all sets something is true? Does it avoid the problem by quantifying over all elements but ...
2
votes
2answers
679 views

Infinite Disjunctions and Conjunctions

While doing work on propositional logic (namely, proving the Generalized De Morgan's Laws), I found myself wondering why precisely an infinite conjunction or disjunction are not permitted, due to the ...
56
votes
6answers
3k views

Why is $\omega$ the smallest $\infty$?

I am comfortable with the different sizes of infinities and Cantor's "diagonal argument" to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. ...