Questions about 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
3answers
167 views

Simplifying Equivalences in Łukasiewicz Logic

I am working on an inference system for infinite valued Łukasiewicz logic, using standard MV-algebras. As a pre-processing step, I would like to perform (non-exhaustive) simplification of formulae. ...
4
votes
1answer
301 views

Understanding the syntactical completeness

A formal system is syntactically complete if for each sentence (closed formula) $\varphi$ either $\varphi$ or $\lnot \varphi$ is provable. A formal system is semantically complete if every ...
2
votes
1answer
105 views

Under what conditions does $\forall x(\alpha \to \beta) \leftrightarrow (\forall x \alpha \to \forall x \beta)$ hold?

It's a logical axiom that $\forall x(\alpha \to \beta) \to (\forall x \alpha \to \forall x \beta)$. However, it's generally not true that $\forall x(\alpha \to \beta) \leftarrow (\forall x \alpha \to ...
6
votes
2answers
215 views

Can Arithmetic recreate the transinfinite hierarchy of Set Theory?

I asked this question in Philosophy.StackExchange whilst trying to get to grips on Badious declared philosophy on using mathematics as ontology. But was advised to ask it here because of the ...
4
votes
2answers
69 views

Can we prove that an extension to a structure is consistent if the original structure is?

As I understand it, there is no way to prove that $\mathbb{N}$, as modeled by P.A., is consistent - meaning it may be possible to demonstrate eg. $5 = 3$. Therefore it is presumably also impossible to ...
6
votes
1answer
169 views

Is there a useful Galois connection between Languages and Grammars?

I've just beginning to learn logic and proof theory - and the following rather vague and perhaps ill-formed question occurred to me. Given an alphabet it's straightforward to construct the Language, ...
2
votes
3answers
167 views

Why do the clauses in a semantics for quantifiers mention free variables?

In section 4 of the article on Generalised Quantifiers in the Stanford Encyclopedia of Philosophy http://plato.stanford.edu/entries/generalized-quantifiers/ the author writes: "Modern predicate ...
1
vote
1answer
676 views

Set of numbers pairwise relatively prime

Given a positve integer n, we can find infinitely many positve integers $b$ such that the $n-1$ integers in the set $\{b+1,\,2b+1,\,3b+1,\,...,\,(n-1)b+1\}$ are pairwise relatively prime. I assume ...
2
votes
1answer
79 views

What's the error in this argument that Fin$\le_m$Inf

There must be an error in the following argument since Fin is not many-one reducible to Inf, I can't seem to find it. Here it is informally (I hope it's straightforward and not confusing): Take any ...
0
votes
2answers
126 views

First Order Semantics and Logic Sentences

I'm trying to write a first order sentence, which if, interpreted the symbols in this natural manner in the set of Naturals, would assert that: Every even number is the sum of two prime numbers. ...
5
votes
3answers
467 views

How to show that $\vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\beta \to \alpha)$?

Assume $x$ doesn't occur free in $\alpha$, show that: $$\vdash (\forall x \beta \to \alpha) \leftrightarrow \exists x (\beta \to \alpha)$$ This is an exercise on page 130, A Mathematical ...
0
votes
1answer
106 views

Creative, recursively enumerable

I'm trying to show that the set $K$ is creative. $K$ has to do something with $\phi_x$ and the only thing I can get out of creative is if there is a total recursive $f$ s.t. $f(e)$ is an element of ...
0
votes
1answer
125 views

completeness and creative

I'm trying to show that any complete $\Sigma_1^0$ set is creative. The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
1
vote
1answer
155 views

recursive and creative theorem

How can we show that if A is creative, then A is not recursive. Only thing I can get out is the fact that if A is creative, if it is rec. enumerable and the complement(A) is productive. Thanks
1
vote
1answer
157 views

How does one prove that 1-generic set is not computable?

Without resorting to diagonalization proof of halting problem, how does one prove that 1-generic set is not computable?
2
votes
0answers
152 views

How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
2
votes
1answer
150 views

Proof of Kleene's T predicate being primitive recursive

As I am looking over Kleene's T predicate, I was unable to find why Kleene's T predicate is primitive recursive. Can anyone show why? (I know what primitive recursive is.)
0
votes
1answer
63 views

Finite alphabet logic

I am reading some logic books right now and I have problems understanding this problem: A "code" is an injective map $\phi:A^*\rightarrow \mathbb N$ where $A^*$ is the set of finite sequences with ...
6
votes
3answers
15k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
1
vote
5answers
1k views

Definition Of Symmetric Difference

The definition of a symmetric difference of two sets, that my book provides, is: Set containing those elements in either $A$or $B$, but not in both $A$ and $B$. So, in set builder notation, I figured ...
8
votes
6answers
2k views

How to demystify the axioms of propositional logic?

How might I go about getting some intuition on the typical axiom schemes given for propositional logic? They seem rather mysterious at first glance. For example, these are taken from: ...
0
votes
1answer
224 views

Recursively inseparable sets

I'm trying to show that there is a pair of $\Sigma_1^0$ recursively inseparable sets. From the definition, recursive inseparable is if there is no recursive set $C$ such that $A\subset C$ and $B\cap ...
1
vote
3answers
1k views

If $A \subseteq C$ and $B \subseteq D$ then $A \times B \subseteq C \times D$

Show that: if $A \subseteq C\,$ and $\,B \subseteq D,\,$ then $\,A \times B \subseteq C \times D.$ Can anyone help me with this?
9
votes
2answers
246 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
0
votes
3answers
279 views

Two easy proofs by contradiction

Check the validity of the statements below using contradiction method (i) p: The sum of an irrational number and a rational number is irrational (ii) q: If $n$ is a real number with $n ...
-1
votes
1answer
136 views

Mathematical reasoning: Sun rises or moon sets - the 'or' used is here is exclusive or inclusive?

State whether the "Or" used is "exclusive" or "inclusive"? Give reasons Sun rises or Moon sets
0
votes
1answer
117 views

A real number being computable

In my text, it says that a real number $r \in \mathbb{R}$ is computable iff given $n$ one can compute $q \in \mathbb{Q}$ such that $\left|r-q\right| \leq 2^{-n}$. Can anyone show why it is the case? ...
3
votes
1answer
328 views

What does it mean that a set S tautologically implies wff $\tau$

What does it mean that a set $S$ tautologically implies wff $ \tau$ ? in Enderton introduction to mathematical logic , in page 23 , it define that a set $S$ tautologically implies wff $ \tau$ iff ...
2
votes
2answers
100 views

$\omega_1^{CK} - \omega$ - infinite or finite set? And boundary

I am curious whether $\omega_1^{CK} - \omega$ would result in a finite set or infinite set. Does anyone know what happens? Edit: OK, let me add one more question: Suppose that we take $\omega \cdot ...
11
votes
5answers
428 views

what is the definition of $=$?

what is the definition of $=$? Above is the question that I would like to be answered, below are some of my thoughts. I've been thinking about what it means to say $A = B$ I came to this from ...
2
votes
1answer
926 views

As an Introduction - A Mathematical Introduction to Logic by Herbert B. Enderton?

I am attempting to study logic by myself. I acquired the book A Mathematical Introduction to Logic by Herbert B. Enderton. I want to ensure that this is a good introduction so, is this a good ...
3
votes
2answers
104 views

p-point ultrafilters on a countable linear order

Suppose that $(P,\leq)$ is a countably infinite linear ordering, and $U$ is a p-point ultrafilter on $P$. Show that there is an $X\in U$ such that $X$ has order type $\omega$ or $\omega^*$. (This is ...
11
votes
3answers
582 views

Gentzen Cut elimination: Why do we have to “go infinite”?

I found some slides here that say you can't do cut elimination on PA with axioms like $$\frac{P(Z)\;\;\;\;\;\forall n,\,P(n) \implies P(Sn)}{\forall n,\,P(n)}$$ (which denotes infinitely many axioms ...
1
vote
1answer
53 views

analytical hierarchy and individual variable quantifiers

For analytical hierarchy, $\Sigma^1_0$ is usually defined as the class of formula that does not have any set quantifier - but does this mean that there can be any number of quantifiers for individual ...
2
votes
1answer
2k views

Translating a sentence into symbolic form.

If G(x) = "x is green" and the sentence is "Some animals are green and some are not green." Then is my symbolic sentence correct? $$\exists x G(x) \land \exists y \lnot G(y)$$
3
votes
0answers
106 views

The Logic of Satisfiability?

I am aware of some study into the logic of provability. It is generally taken to be intermediate in strength between S4 and S5 modal logics. Is there corresponding study into something like the logic ...
1
vote
1answer
586 views

The truth value of quantified statements

I just took an exam and the following problems were asked: Determine the truth value of each of these statements if the domain consists of all real numbers. $\forall x \forall y \; ...
4
votes
2answers
1k views

Predicate vs function

In logic, what is the difference between a predicate and a function? To be specific, I am just interested in First Order Logic. Thanks!
0
votes
1answer
360 views

Why are the rational numbers an elementary substructure of the reals?

I read that the natural numbers ($\mathbb{N}$) are not an elementary substructure (ES) of the integers ($\mathbb{Z}$) , the integers ($\mathbb{Z}$) are not an ES of the rational numbers ...
3
votes
2answers
226 views

how to create the set of hyperreal numbers using ultraproduct

As title says, can anyone explain how to create the set of hyperreal numbers using ultraproduct from the set of real umbers?
1
vote
2answers
80 views

structure in context of ultraproduct

Ultraproduct is defined as $$\prod_{i \in I} M_i $$ I know that structure is usually of form $(A, \sigma, I)$, but in this context, what exactly is structure, and how do we get the cartesian product? ...
3
votes
1answer
81 views

is the Hyperarithmetical hierarchy second order arithmetic but NOT second order logic? and if so why?

I was told in a previous answer (but dont remember by whom but he then didnt answer back), that the hyperarithmetical hierarchy is second order arithmetic but not second order logic. Is this so? what ...
14
votes
3answers
480 views

When we say, “ZFC can found most of mathematics,” what do we really mean?

ZFC works as a foundation because it can prove many sentences that are "translations" of theorems from "standard" mathematics into the language of ZFC. But there's a subtlety. When we say, "ZFC can ...
7
votes
2answers
528 views

How does (ZFC-Infinity+“There is no infinite set”) compare with PA?

How does (ZFC-Infinity+"There is no infinite set") compare with (first order) PA? Intuitively, neither theory should be more powerful than the other.
5
votes
2answers
380 views

a good text for a first course in mathematical logic

in last two months , i asked many people about good text for first mathematical logic . after that a chose some text , first order mathematical logic , angelo magrais , it is ok but the text uses ...
4
votes
1answer
104 views

Naming objects when existence and uniqueness was proven

Let's take ZF and let $e(X)$ be the sentence $\forall Y. Y \notin X$. From the axioms, we can prove $\exists X. e(X)$ and $\forall X, Y. e(X) \wedge e(Y) \implies X=Y$. So far so good. Now, we assign ...
8
votes
1answer
171 views

what does it mean that constructible universe is definable from ordinals?

I know how constructible universe is created, but I also separatedly read that the universe is definable from ordinals - so I am wondering what it really means.
1
vote
1answer
548 views

Gödel, Escher, Bach: $ b $ is a power of $ 10 $.

I’d like to verify if my formula correctly expresses that a number is a power of $ 10 $, using the $ \sf{TNT} $ language provided by Hofstadter in his famous book Gödel, Escher, Bach: An Eternal ...
1
vote
1answer
2k views

Reduce following expression to one literal, boolean algebra

$$W'X(Z'+Y'Z)+X(W+W'YZ)$$ The goal is to reduce the following to one literal So after I expanded it out, i got the following: $$W'XZ'+W'XY'Z+WX+W'XYZ$$ Now from here, I got stuck and didn't know ...