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)

2
votes
1answer
146 views

first order logic question model

suppose we have a model for a language in first order logic $ M=<D,I> $ such that D is the domain and I is the interpetation such that for every $ a \in D $ we have a closed noun (a noun with no ...
3
votes
1answer
67 views

Analytic, Coanalytic space of functions

I'm having trouble showing that the set of differentiable functions on $[0,1]$ is coanalytic ($\mathbf{\Pi}_{1}^{1}$) and the set of continuously differentiable functions of $[0,1]$ is analytic ...
1
vote
1answer
69 views

Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say: < is a strict partial order and R is an irreflexive and ...
3
votes
1answer
180 views

Is the arithmetic most mathematicans use a modelled within first or a second order logic?

I often read that arithmetic in first order logic has problems and you really want to do it in second order logic. However, aren't the Zermelo–Fraenkel axioms written down in the language of first ...
3
votes
3answers
163 views

Equivalence and Tarski

I am currently writing a paper on Tarski's Semantic Concept of Truth. His T-schema is as follows: 'X' is true if, and only if, 'p' Where 'p' is a sentence such as "snow is white" and 'X' is the name ...
4
votes
1answer
102 views

Is it possible to prove that the Grz axiom is valid in a modal frame iff the frame is reflexive and transitive?

We need to prove (or disprove?) that $ \square (\square (A \rightarrow \square A) \rightarrow A) \rightarrow A $ is valid in the Kripke modal frame $ F = <S, R> $ iff R is transitive and ...
10
votes
1answer
142 views

Saturated Boolean algebras in terms of model theory and in terms of partitions

Let $\kappa$ be an infinite cardinal. A Boolean algebra $\mathbb{B}$ is said to be $\kappa$-saturated if there is no partition (i.e., collection of elements of $\mathbb{B}$ whose pairwise meet is $0$ ...
3
votes
3answers
155 views

A non-arithmetical set?

A set is called arithmetical if it can be defined by a first-order formula in Peano arithmetic. I first encountered these sets when exploring the arithmetical hierarchy in the context of ...
2
votes
1answer
154 views

Proving an implication by proving its dual

My textbook "Discrete and Combinatorial Mathematics, an Applied Introduction" by Ralph P. Grimaldi contains the following definition: Let $s$ be a statement. If $s$ contains no logical connectives ...
-4
votes
3answers
274 views

How to be sure a contradiction is not possible?

I have written a formal proof of the theorem: $$\forall U \exists r(\forall a(a\in r \leftrightarrow (a\in U \wedge a\notin a)) \wedge r\notin U \wedge r\notin r)$$ See: ...
5
votes
3answers
595 views

Is there a difference between allowing only countable unions/intersections, and allowing arbitrary (possibly uncountable) unions/intersections?

As in the title, I am asking if there is a difference between allowing set-theoretic operations over arbitrarily many sets, and restricting to only countably many sets. For example, the standard ...
15
votes
3answers
958 views

Proof that $\mathbb N $ is finite

Obviously this is a false proof. It relies on Berry's paradox. Assume that $\mathbb{N}$ is infinite. Since there are only finitely many words in the English language, there are only finitely many ...
1
vote
1answer
149 views

Definition and meaning of “Proof Schema”, “Class Sign”

I'm a newbie in advanced mathematics, and I'm trying to understand Godel's theorem. I came across these two words which I couldn't understand clearly. "Proof Schema" and "Class-Sign" Can anybody ...
0
votes
2answers
83 views

Logic question proving something about compactness

Let $\Sigma$ be a set of formulas. There's a finite set $\Lambda \subseteq \Sigma$. I'm asked to prove or disprove that $\Sigma$ has a model if and only if $\Lambda$ has a model. It seems to me ...
5
votes
1answer
377 views

Is there any direct application of Gödel's Theorems outside of logic?

Gödel's incompleteness theorems was a major achievement with ramifications outside the field of mathematics itself. Are there any direct applications of the theorem(s), or any of the methods pioneered ...
-3
votes
4answers
249 views

What are some primary mathematical utilities of the axiom schema of separation?

I read a discussion concerning the axiom schema of specification, which I yet take as saying that for every set and a class-defining condition, those elements of the set satisfying this condition ...
13
votes
9answers
724 views

Learning Model Theory

What books/notes should one read to learn model theory? As I do not have much background in logic it would be ideal if such a reference does not assume much background in logic. Also, as I am ...
1
vote
1answer
409 views

hilbert system first order logic proof

i need to prove the following and i have no idea how to without using soundness and completeness $ \neg \forall x A \rightarrow \exists x \neg A $ using the following axioms: I1. $ A \rightarrow (B ...
0
votes
1answer
233 views

Definition of effective enumerability and empty set

Let $S$ be a set. We say that $S$ is effectively enumerable iff (by definition) there exists a function $f \colon N \to N$ which has $S$ as codomain. My question is: is the empty set an effectively ...
2
votes
2answers
72 views

Embedding of standard model of arithmetic to PA-model

I am working on the following problem: Let $ S_{Arithmetic} = \{+, *, 0, 1\}, \mathfrak{M} $ a model for PA (first-order peano axioms) }, and $ \mathbb{N} = (\mathbb{N},+ ^{\mathbb{N}}, ...
2
votes
5answers
392 views

Is my proof that $(p \wedge \neg p) \Rightarrow q$ correct?

I was asked by a professor a while ago to prove $(p \wedge \neg p)$ implies $q$. Whether through laziness or cleverness, I came up with the following proof: $p \wedge \neg p$ (by assumption). ...
1
vote
3answers
192 views

Diagonal Lemma justification

Given the diagonal lema stated as above: Diagonal Lema. Let $\mathfrak{T}$ be a theory wich is capable of representing the primitive recursive functions, and a codification schema for formulas in ...
2
votes
0answers
171 views

Sum and product of an ultrafilter

I know the following simple fact is true, but I can't find a good proof: Over the naturals, the only ultrafilter $\mathcal U$ such that $\mathcal U \oplus \mathcal U = \mathcal U \odot \mathcal U$ is ...
2
votes
1answer
241 views

How many maximal consistent sets are there on a $\mathscr{FOL}$

Let $\mathfrak L$ be a $\mathscr{FOL}$ with completeness and soundness. My question is how many maximal consistent sets on it? I know that every maximal consistent set can be dealt as an ...
11
votes
3answers
609 views

In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?

I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
4
votes
1answer
209 views

Lindenbaum algebra is a free algebra

The following is a continuation of this question. I would like to prove that the Lindenbaum algebra is a free algebra. Hopefully I would like to hear hints on how to proceed in the 'right' ...
4
votes
3answers
969 views

Natural deduction proof of $\forall x (\exists y (P(x) \vee Q(y))) \vdash \exists y (\forall x (P(x) \vee Q(y)))$

I'm trying to do a Fitch proof of $$ \forall x (\exists y (P(x) \vee Q(y))) \vdash \exists y (\forall x (P(x) \vee Q(y))) $$ Edit: using only the axioms on ...
2
votes
1answer
235 views

Free boolean algebra

Consider the following definition: Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X ...
4
votes
1answer
148 views

Are there simple counterexamples to a strengthening of omitting types theorem

The famous Ehrenfeucht's omitting types theorem states that for any countable set of nonisolated types (without parameters), there is a (countable) model such that it does not realize any of them. A ...
3
votes
1answer
301 views

Complete/incomplete theory

I am thinking about completeness and incompleteness of theory's, and to illustrate both properties i am thinking of how to build an complete system, and then turn it into an incomplete one. Example. ...
2
votes
1answer
180 views

Is there a relationship between the Compactness Theorem and the upward Lowenheim-Skolem Theorem in FOL?

Is there a relationship between the Compactness Theorem and the upward Lowenheim-Skolem Theorem in FOL? I was thinking of another post of mine "Why accept the axiom of infinity?" when I though, ...
0
votes
1answer
82 views

Relations of language/theory/signature

Say that the language of the first order logic is the collection of symbols that can be used in the formulas + the grammar (the rules that specify how they can be combined)? 1) However, the signature ...
2
votes
1answer
132 views

Theorems/entailment notation

When defining a predicate logic system with natural deduction, we can define the syntatic entailment with the operator $\vdash$. Generally, I see authors using the formula $\vdash \phi$ to say that ...
1
vote
1answer
126 views

Define a logical formula as another formula

I'm reading Dirk van Dalen's Logic and Structure and noticed that in many parts of his book he defines some formula to be an alias for another formula (he doesn't use the name alias, he just says that ...
10
votes
3answers
559 views

Solving P vs NP with computer

Is it possible to build a computer program that would (eventually) bring a solution to the P vs. NP question?
2
votes
2answers
180 views

How is uncountability characterized in second order logic?

How is uncountability characterized in second order logic? Also, why is this characterization of uncountability "absolute" in the way that FOL's characterization of uncountability is not? A very ...
4
votes
3answers
288 views

Impossibility of certain methods of proof?

There are many methods available for proving a given statement: direct proof, proof by induction, proof by contrapositive, proof by contradiction, etc. In some cases there is an obvious method that ...
3
votes
1answer
162 views

Explanation of how models can differ on $\omega$?

Assuming set theory (here, ZF) is consistent, there is a model $V$ of ZF, the universe of all sets. So, there is a $\omega^V\in V$. A set $A\in V$ is countable iff a bijection $f\in V$ exists ...
5
votes
2answers
179 views

Consistency strength: If Con($T+A$) implies Con($T+B$), can we infer anything about $A$ and $B$?

To be more specific, let $T$ be a first order theory and let $A$ and $B$ be two different first-order sentences, both in the same language as $T$ but independent of $T$. Additionally, suppose we have ...
3
votes
3answers
273 views

Proof Using Truth Tables

Pleae forgive the very basic question, but I know nothing really of formal logic and so would appreciate some feedback. The truth table defining the implication operator ...
2
votes
1answer
1k views

Formal proof of De Morgan's laws for quantifiers

Consider the set of inference rules for first order logic (analogous to the ones listed here : http://en.wikipedia.org/wiki/Sequent_calculus#Inference_rules) I am stuck in proving the following rule ...
4
votes
2answers
640 views

Logical implication vs Tautological implication

I'm reading Enderton's logic book and have arrived to his deductive calculus for first order logic. After defining it, he presents the following theorem: $\Gamma\vdash \varphi$ iff $\Gamma\cup ...
3
votes
2answers
167 views

dense linear orders DLO

I am asked to prove that if I have two models of dense linear orders DLOs WITH the minimum and maximum. must be izomorpic to each other by fining direct izomorphy. I seem to always get stuck ...
3
votes
1answer
266 views

mathematical notation for a logical statement

The proof of the statement below is a homework question, however I did not tag this question as such since I don't need the actual proof: I have already proved the statement wring and don't need a ...
2
votes
2answers
314 views

To show $A\implies B$, is that sufficient to show for all $C$ s.t. $C\implies A$ then $C\implies B$

my question is in the title: to show $A\implies B$ is it enough to show for any $C$ such that $C\implies A$ we have $C\implies B$?
0
votes
1answer
63 views

Logic - proving that if a predicate is provable then another is provable

I am asked to prove that $$K \vdash (a \rightarrow \exists x \beta ) \implies K\vdash \alpha \rightarrow \beta[t/x]$$ is true using deduction. I've failed to prove this and suspect there is an error ...
0
votes
1answer
128 views

what does that statement mean about the relation?

what does this mean about P? $$\forall x \exists y (p(x,y) \rightarrow p(y,x)) $$ i know that $$\forall x \forall y (p(x,y) \rightarrow p(y,x)) $$ means that P symmetric but what does the first ...
2
votes
2answers
118 views

help me define the connectives for 3 value logic

so basically i have a project about 3 valued logic ie truth=1 false = 0, unknown = 1/2 in a previous project I had to come up with formulae for 2 valued logic as follows: ...
8
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 ...
6
votes
2answers
136 views

Effective cardinality

Consider $X,Y \subseteq \mathbb{N}$. We say that $X \equiv Y$ iff there exists a bijection between $X$ and $Y$. We say that $X \equiv_c Y$ iff there exist a bijective computable function between ...