Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

3
votes
3answers
259 views

Interpretation of a formula and truth

I just started self-studying Mathematical Logic by Ebbinghaus. I already knew something about formal languages, but nothing about model theory. There is something I don't understand: Exercise 3.3, ...
3
votes
1answer
336 views

Can it be shown that ZFC has statements which cannot be proven to be independent, but are?

I am familiar with the concept that a statement can be proven indepent such as in the case of the continuum hypothesis where both ZFC+CH and ZFC+(CH is false) are both proven consistent, but I would ...
1
vote
1answer
209 views

Expressing P = NP as a first order formula

I want to express P = NP in a completely formal way. My first try: There exists an algorithm A and a polynomial bound p such that for all input i, A(i) = true iff i is a satisfiable formula and ...
2
votes
2answers
224 views

Can logic be defined in terms of sets? Can sets be defined using logic?

Can logic be defined in terms of sets? Can sets be defined using logic? If both answers are positive, is one reduction preferable to the other? In what sense?
2
votes
1answer
330 views

Translation of a mathematical statement formulated in words to one formulated in predicate logic

I want to express the fact that for all $x \in A$ that have the property that for all $y\in x$ $T(x,y)$ is true and there exists an $u \in B$ such that $P(y,u)$ is true AND for all $v\in C$, $Q(y,v)$ ...
2
votes
1answer
62 views

Is $\left\{ F\subseteq V | P(F) \right\} = \emptyset$ or $= \left\{ \emptyset \right\} $, if no $F$ satisfies $P$?

Let $V$ be a set and let $P$ be a property, such that for no $F\subseteq V, \ P(F)$ is true. Is then $\left\{ F\subseteq V | P(F) \right\} = \emptyset$ or $= \left\{ \emptyset \right\} $ ?
2
votes
3answers
359 views

Example of infinite proof

Is there a reasonably simple example of an infinitary proof in logic? I need mostly an example in which the total height or level of a derivation is infinite, i.e. there is at least an axiom from ...
3
votes
1answer
175 views

Can somebody explain to me how we define an isomorphism between structures?

I was reading this definition from journal article 'fixed-point logics with nondeterministic choice' by Anuj Dawar and David Richerby. On page 505 it says 'Classes of structures are assumed to be ...
2
votes
1answer
240 views

Question about maximally consistent sets in logic

Problem: Σ is "proofwise stronger" than a set Γ if {$\alpha$: Σ ⊢ $\alpha$} $\supseteq$ {$\alpha$ : Γ ⊢ $\alpha$ }. Show that for every maximally consistent set of propositions Σ, for every set Γ, ...
6
votes
3answers
715 views

Assumption about elements of the empty set

Is there any axiom or theorem of any part of math/logic that states the fact: "Every assumption about the elements of the empty set is true." ? If no, can you imagine why it is not true?
2
votes
0answers
116 views

Cut-elimination (transfinite induction base step)

I am having problems with the base step in a proof by transfinite induction. Consider a certain language $Z_{\infty}$, a language similar to PA but with an $\omega$-rule and a cut rule among its ...
1
vote
2answers
150 views

Under a different form this proposition appears to be (oddly) true. Why?

Similar question to this question (This question was actually the motivation for the other question, which - if I haven't got it wrong - generalizes this one): I have to prove a proposition of the ...
2
votes
2answers
181 views

Logical squabbles

I need some help with the follwing: Lets suppose that the sentence $\forall x: x\in I \rightarrow P(x)$ is false. Now consider the sentence $$\forall x: x\in I \rightarrow (P(x) \ \& \ Q(x) ) \ \ ...
4
votes
2answers
415 views

True, false, or meaningless?

Are the following two assertions always true, always false or meaningless? $\exists i \in \emptyset$ $\forall i \in \emptyset$ Because it seems that one encounters expressions of this kind fairly ...
9
votes
3answers
816 views

What is the intuition behind the “par” operator in linear logic?

I'm $\DeclareMathOperator{\par}{\unicode{8523}}$ trying to wrap my mind around the $\par$ ("par") operator of linear logic. The other connectives have simple resource interpretations ($A\otimes B$ ...
1
vote
3answers
193 views

How to manage without specifying a particular algebraic system?

My long standing question: How to eliminate writing $\cap^L$ instead of plain $\cap$ when we deal with more than one lattice? (and likewise with other (finite and infinite) structures) It is ...
3
votes
3answers
141 views

“Contradiction-free” in logic vs. “Contradiction-free” in plain mathematics

In our course we have defined a theory $T$ to be contradiction-free, if there are no formulas $\alpha_1,\ldots \alpha_n\in T$ such that $\neg ( \alpha_1 \& \ldots \ \& \alpha_n )$ is provable ...
3
votes
3answers
285 views

Distinguishing between valid and fallacious arguments (propositional calculus)

I am having some difficulties understanding logical arguments. I was taught that the notion of a valid argument is formalized as follows: "An argument $P_1, P_2,\cdots , P_n ⊢ Q $ is said to be ...
5
votes
4answers
1k views

Implication and equivalence arrows, when to use them?

In my course book we have something called implication arrows $\Rightarrow$ and equivalence arrows $\Leftrightarrow$ and I have never managed to understand them. When do I know which to use and how ...
4
votes
1answer
340 views

A Logic for Digital Circuits

To put it simply, what i'm looking for is a logic that models sequential circuits. If i understood correctly, digital circuits are often categorized in two distinct categories, combinatorial and ...
4
votes
1answer
119 views

A technique for deciding satisfiability in fragments of first-order logic

By Goedels completeness theorem satisfiability in first-order logic is $\Pi_1$. So to obtain decidability in some fragment, it is enough to show that satisfiability is $\Sigma_1$ in this fragment. I ...
9
votes
3answers
1k views

Proper way to read $\forall$ - “for all” or “for every”?

I was asked in class the other day by a professor for whom English is a second language why $\forall$ is sometimes read "for all" while other times read "for every." Is there a rule for this? I was ...
0
votes
1answer
86 views

Idea for proof that this $\Sigma$-formula holds in every nonempty structure

Can someone give me a hint, how to prove that the $\Sigma$-formula $$ \neg (\psi_{x \rightarrow t} \ \& \ \exists x \psi)$$ where $\psi$ is an arbitrary $\Sigma$-formula, $t$ is a ...
2
votes
1answer
153 views

If $f$ is primitive recursive (but not necessarily bijective) and $M$ primitive recursive, is $f(M)$ primitive recursive?

In this post I wondered, whether a language over a finite alphabet is “stable” with respect to primitive recursiveness, recursiveness and recursive enumerability under different enumerations of the ...
2
votes
1answer
100 views

Language over a finite alphabet is “stable” with resprect to primitive recursiveness ( & etc.) under different enumerations

I'm trying to prove the following proposition: The fact that a language $L$ over a finite alphabet $A$ is primitive recursive, recursive or recursively enumerable does not depend upon the enumeration ...
4
votes
1answer
417 views

Difference between formulas and sentences in formal language?

I know that formulas contains free variables and sentences only contains bounded variables. Am I right to say that sentences are equivalent to the properties that structures may have or have not. As ...
15
votes
2answers
896 views

Gödel's incompleteness theorem and real closed fields

I am familiar with the result of Gödel's incompleteness theorem. I find it hard though, to convince myself that when we replace normal number arithmetic with real closed fields, that there is an ...
3
votes
1answer
477 views

About the pointwise infimum of a continuous piecewise linear function

I am reading the logic paper "Interpolation in fuzzy logic" by Matthias Baaz and Helmut Veith http://www.springerlink.com/content/654wl9u5mcj7qtva/ On page 479 it is claimed that "It suffices to show ...
1
vote
2answers
265 views

What is the importance of mentioning —U? (Turing 1936)

I'm trying to get my head around page 252 of Turing's "On Computable Numbers [...]", specifically near the end of the page where he talks about -U (logical negation of U, the German blackletter U). ...
7
votes
4answers
430 views

Difference between a “theory” in logic and a “system of axioms”

In logic, a $\Sigma$-theory $T$ is just a set of sentences obtained from the signature $\Sigma$. As I understand, what logician calls "theory" is what a mathematician calls "system of axioms". But ...
1
vote
0answers
184 views

Same same but different: Coextensive relations in model and set theory

The definition of a structure in model theory can be summed up like this (for simplicity's sake without individual constants and functions): Def. 1 A structure is a triple of sets $\langle A, ...
5
votes
2answers
2k views

Can conjunction be expressed via implication?

Exercise 1.5 from Arnold Milner Logic Notes: While disjunction is easily defined via implication (p v q = p->(q->p)) I have trouble defining conjunction and ...
36
votes
16answers
3k views

In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: ...
5
votes
1answer
152 views

How can I prove that this set is not arithmetic?

Let $\Sigma = \left\{ 0,1,+,\times , < \right\}$ be a signature, where the last 3 symbols have arity 2 and all except the last symbol are functions symbols. How can I prove that the set $X=\left\{ ...
4
votes
3answers
700 views

Is there a natural number between $0$ and $1$?

Is there a natural number between $0$ and $1$? A proof, s'il vous plaît, not your personal opinion. (Assume the Peano Postulates.)
0
votes
1answer
117 views

Which strings are in this set?

I have a question which formulas are in the set $\kappa$ (which is defined below). Sadly, for this I have to introduce some definitions and I apologize in advance for making the reader go through ...
2
votes
1answer
437 views

Proof by induction that $\Sigma$-formulas are uniquely readable

My question is how to prove that $\Sigma$-formulas are uniquely readable (in our course this was wasn't really proved - in the proof it said just "proof by induction", but I'm confused what was meant ...
12
votes
1answer
662 views

(Why) is topology nonfirstorderizable?

Is it the right point of view to say, that topology is nonfirstorderizable (only) because the union of arbitrarily many open sets has to be open? And if "arbitrarily many" was relaxed to "finitely ...
2
votes
1answer
277 views

Set-theoretical definitions of the notion of “structure”

What general set-theoretical definitions of the notion of "structure" are there? By general definition of "structure" I mean a formula $\Phi(x)$ in the first-order language of set theory such that ...
3
votes
2answers
139 views

Gap the lemma: satisfiable theory implies contradiction-free theory

I have a question about a gap in lemma. First how things were defined in the course I'm taking (I'm sorry to be making the readers going through this list of definitions, but I don't know how to make ...
4
votes
4answers
477 views

Exists iff for all

I have a theorem of the following scheme: $Q \Leftrightarrow \exists x\in Z: P(x) \Leftrightarrow \forall x\in Z: P(x)$. How to simplify it (not to write $P(x)$ twice)?
3
votes
3answers
375 views

if $s \implies \lnot w$, does $\lnot s \implies w$?

Quick question. I'm given a set of logical statements: 1) $l \lor s$ 2) $\lnot c$ 3) $l \rightarrow b$ 4) $s \rightarrow c$ 5) $s \rightarrow \lnot w$ Now $l, s, c, b$ and $w$ represent certain ...
3
votes
2answers
229 views

Programming Logic: - Splitting up Tasks Between Threads

I asked this question at stackoverflow and instead of addressing the math required in the problem, they wanted to talk about why setting up 5 threads is no good, or question my intentions. I just want ...
4
votes
2answers
389 views

Model existence theorem in set theory

From the FOM newsgroup I learned: It's a theorem of (first-order) set theory that every consistent first-order theory has a model. What's the exact formulation of this theorem in purely ...
6
votes
1answer
313 views

What do coherent topoi have to do with completeness?

There is a theorem of Deligne that a "coherent" topos (e.g. one on a site where all objects are quasi-compact and quasi-separated) has enough points (i.e. isomorphisms can be detected via geometric ...
6
votes
2answers
449 views

Brouwer's Fan Theorem

I am not a mathematician, but I really would like to understand/know the following: What is so special about Brouwer's "Fan Theorem"? Is there an easy to undestand proof somewhere? Why was Brouwer ...
17
votes
7answers
589 views

What's the deal with empty models in first-order logic?

Asaf's answer here reminded me of something that should have been bothering me ever since I learned about it, but which I had more or less forgotten about. In first-order logic, there is a convention ...
5
votes
4answers
392 views

Question about using disjunction rule of inference to obtain material implication?

I'm seeing math logic and I have a question. Let $p$ be a proposition. Let's suppose I have $\lnot p$. By disjunction rule, this implies $\lnot p \vee q$, where ...
4
votes
0answers
215 views

Interesting applications of the cofinite topology?

Background: I'm doing some expository writing on intuitionistic logic and I have been toying with the idea of demonstrating its applicability via models where the denotations are taken from a Heyting ...
5
votes
4answers
126 views

assignment of variables…only if we deal with a non-empty set

If $L$ is a signature, $\mathbb{V}$ a countable set of variables, $\Phi$ a $L$-sentence, $S$ a structure with domain of discourse $\underline{S}$ and $\mu:\mathbb{V}\rightarrow \underline{S}$ a ...