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)

1
vote
1answer
371 views

Well formed formulas of all mathematical proof

Last week, I asked the "automated proof-checking machine." Many answered that automated proof-checking machine already exists in first-order theory. However I have still question. For the operation ...
4
votes
3answers
288 views

Exercise in propositional logic.

Which of the following arguments is valid? A. If it rains, then the grass grows. The worms are not happy unless it rains. Therefore, If the worms are happy , then the grass grows. B. If the wind ...
3
votes
1answer
107 views

What is the (propositional) logic associated with an orthomodular lattice?

In Quantum Mechanics the space of projections on the associated Hilbert Space of States forms an Orthomodular Lattice. Von Neumann calls this a Quantum Logic. When projections commute they generate a ...
2
votes
2answers
321 views

Help with the proof that an initial proper segment of a sentence can't be a sentence

I'm reading Peter G. Hinman-Fundamentals of Mathematical Logic, I'm new with stuff like proofs, and as newbie I'm not used to proving anything, so I'm jammed in the exercises of the book of the ...
6
votes
5answers
228 views

$\forall m \exists n$, $mn = n$ True or False

Identify if the statement is true or false. If false, give a counterexample. $\forall m \exists n$, $mn = n$, where $m$ and $n$ are integers. I said that this statement was false; ...
3
votes
3answers
1k views

How to Negate These Statements Containing Logical Connectives?

I have a few questions that I am working on, that I supposedly answered incorrectly. I have the following statements that I am charged to express in symbolic form: $f =$ you are a full-time student; ...
0
votes
1answer
48 views

Does the term consistency (for equations) have some logical meaning?

Let $\phi(x_1,...,x_n)$ be a statement about an equality of two expressions having $x_1,...,x_n$ respectively. If there is no $(x_1,...,x_n)$ such that $\phi(x_1,...,x_n)$ is true, we call this ...
1
vote
1answer
211 views

Bijection and Natural elements

I'm trying to establish that the set of $L_{PA}$ terms and $p$ an element of the $N[x_1,\ldots,x_n]$ where $N$ = naturals, for some $n$ in the Naturals are in a bijection. Well, the $L_{PA}$ terms ...
2
votes
1answer
117 views

What would be arithmetic hierarchy of $\Sigma_1^0 \wedge \Pi_1^0$?

What would be arithmetic hierarchy of the form of formula like $\phi \wedge \psi$ where $\phi$ is $\Sigma_1^0$ and $\psi$ is $\Pi_1^0$? Prenex normal form seems to give me no answer for this.
2
votes
1answer
132 views

Are Horn clauses always universally quantified?

I know that the original publication ' Alfred Horn (1951), "On sentences which are true of direct unions of algebras" ' didn't require universal quantification. However, it didn't call these Horn ...
0
votes
1answer
228 views

Unconventional models and Peano Arithmetic

I'm trying to show that $\mathbb{Z}[x]^+ \models \mathsf{PA}^-$. What are the initial segments of this model?
1
vote
2answers
140 views

Models and Inconsistency.

I’m trying to show that a first-order theory $ T $ is inconsistent if and only if $ T \vdash \varphi $ for every w.f.f. $ \varphi $. I understand that there might be a need to use the axioms for $ ...
1
vote
2answers
185 views

Paradox - What is wrong with this proof that proves a false assertion?

Theorem: Let $a_{n}=a_{n-1}+1, a_1=1$. For any $n$, in order to compute $a_n$, it is necessary to compute $a_i$ for each $i=1,\dots,n-1$, which takes $\Theta(n)$ time. Proof: This is vacuously true ...
2
votes
2answers
160 views

Proving if Boolean Equations are valid

I need to prove algebraically that: $$ab + abc'd + abde' + abc'e + a'b = b$$ $$(wxyz)(wxyz' + wx'yz + w'xyz + wxy'z) = 0$$
27
votes
7answers
2k views

Are there infinite sets of axioms?

I'm reading Behnke's Fundamentals of mathematics: If the number of axioms is finite, we can reduce the concept of a consequence to that of a tautology. I got curious on this: Are there infinite ...
-1
votes
2answers
162 views

How many possible operations are there of arity n? (N-ary) [closed]

Not sure about this one! Can someone please help? Thanks
13
votes
1answer
337 views

Do you need the Axiom of Choice to assert that every real vector space has a norm?

Math people: This question is 95% answered (the first answer) at Does every $\mathbb{R},\mathbb{C}$ vector space have a norm? and Vector Spaces and AC . The questions, answers, and links found there ...
0
votes
1answer
100 views

Computability function - how to express it in set theory/arithmetic hierarchy

Let's say that $f$ is computable function such that for particular inputs $x$ and $y$, $f(x) = 0$ and $f(y) = 0$. If we want to express this in logical form (arithmetic hierarchy formula), what would ...
1
vote
5answers
247 views

There are four possible operations of arity 1. What are they?

I know negation is one but cant think of anything else? I need three more!
1
vote
1answer
104 views

function that cannot be expressed using finite characters

There are functions that cannot be expressed using finite characters. For example while function $x^3$ can be written using finite characters there exists a sequence of cartesian pair, describing ...
2
votes
1answer
55 views

Can expressing there is an edge that connects two vertexes be expressed using only first-order logic?

Suppose that we want to express "there exists two vertexes that can be shown to be connected by an edge." in first-order logic. Can this statement be expressed using only first-order logic? Or does ...
2
votes
2answers
189 views

Help understanding $\exists x \exists y (x\neq y \wedge \forall z ((z=y)\vee (z=x)))$

I'm not sure how to interpret this problem. Find a domain for the qunatifiers in: $$\exists{x} \exists{y}(x\neq y \wedge \forall{z}((z=y)\ \lor(z=x))) $$ such that this statement is false. So, the ...
4
votes
1answer
106 views

Which categories correspond to the untyped and typed lambda calculus?

Simply typed lambda calculus is the internal language of Cartesian Closed Categories. What category has its internal language the typed lambda calculus? And the untyped lambda calculus? Can we in ...
1
vote
2answers
566 views

Elementary question regarding sentential logic

Sorry if this question is too elementary than usual for this site, but I'm trying to analyze the logical form of the following statement: 3 is a common divisor of 6, 9, and 15. I'm not sure how to ...
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. ...
5
votes
1answer
311 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
216 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
170 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
168 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
683 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
81 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
130 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
469 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
159 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
153 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
64 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
225 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
248 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
281 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
140 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