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
134 views

Converting a QBFs Matrix into CNF, maintaining equisatisfiability

I have a fully quantified boolean formula in Prenix Normal Form $\Phi = Q_1 x_1, \ldots Q_n x_n . f(x_1, \ldots, x_n)$. As most QBF-Solvers expect $f$ to be in CNF, I use Tseitins Tranformation ...
2
votes
4answers
919 views

First order logic and higher order logics?

I hear that Prolog is based in first-order logic. This makes me wonder, C/C++ are based on which higher order logics? If this question is incorrect, please point out that. and how are these logics ...
-2
votes
2answers
1k views

Example of function which is not computable

I am looking for a concrete example of a function $$f: N^k \rightarrow N$$ $$(n_1, n_2, \cdots n_k) \mapsto f(n_1, n_2, \cdots n_k)$$ which is not computable. Source: Computability, An introduction ...
1
vote
1answer
2k views

Translating English to Symbolic Logic - Multiple Quantifiers

Any hints on translating this English sentence into symbolic logic: Something is between everything.
2
votes
1answer
194 views

Multiple quantifier translation

Having some difficulty translating into English from Symbolic logic (the mixture of the quantifiers are confusing to me): ∀x(¬∃yBackOf(y, x) → Large(x)) Any suggestions would be appreciated. Thanks! ...
19
votes
4answers
2k views

Where did mathematicians learn how to do truth tables?

I'm trying to find out who invented truth-tables. Here is what I have so far. Leibniz 'invented' binary arithmetic, or at least is the first one recognized to have codified and explained a base 2 ...
7
votes
2answers
329 views

The first-order theory of linear orders given by closed subsets

[ This question can be seen as a second part to my question A question on linear orders and elementary equivalence ] The question is whether the following conjecture is true or false. I am interested ...
10
votes
2answers
480 views

A question on linear orders and elementary equivalence

Does anybody know whether the following statement is true or false? Conjecture: For every linear order $\langle A, \leq \rangle$ there is a (topologically) closed subset $X$ of $\mathbb{R}$ (the real ...
2
votes
3answers
532 views

Can the negation introduction rule of inference be used instead of the usual rule?

Can the negation introduction rule of inference, $$\begin{array}{c} a\\ b\longrightarrow \neg a\\ \hline \neg b \end{array}\qquad\qquad\qquad (1)$$ be used instead of the usual $$\begin{array}{c} ...
1
vote
2answers
424 views

Help with Law of Excluded Middle

I've got a problem with the law of excluded middle, and have a homework question surrounding it. I normally would never ask, and this is my first time, but I can't for the life of me find an example ...
2
votes
1answer
175 views

Expressing Quantifications

I have to equations: P(x)=student x knows calculus, and Q(y)=class y contains a student who knows calculus. For something like "Some students know calculus" would it be enough to write $\exists x ...
4
votes
3answers
2k views

Different ways to express If-Then

What are some different ways to write the conditional statement $p\implies q\,$, but in English? There's the obvious "If p, then q", but are there any other ways to write it? I'm looking for another ...
1
vote
1answer
95 views

Idea for a proof involving an identity of term functions on $\sigma$-structures [x]

I have some problems with the following theorem: Fix an signature $\sigma$ and a set of variables $\mathbb{V}$. We call $t$ and $t_1$ "equivalent", if for every $\sigma$-structure $S$ and every term ...
3
votes
1answer
132 views

Find a first order sentence in $\mathcal{L}=\{0,+\}$ which is satisfied by exactly one of $\mathbb{Z}\oplus \mathbb{Z}$ and $\mathbb{Z}$

I'm re-reading some material and came to a question, paraphrased below: Find a first order sentence in $\mathcal{L}=\{0,+\}$ which is satisfied by exactly one of the structures $(\mathbb{Z}\oplus ...
2
votes
3answers
281 views

logic question: enumerating propositions

Is it possible to enumerate all propositions (ie, sentences containing no quantified or free variables) that are true given a set of formulas in higher-order logic? (ie, those propositions entailed by ...
3
votes
2answers
126 views

Slick way to define p.c. $f$ so that $f(e) \in W_{e}$

Is there a slick way to define a partial computable function $f$ so that $f(e) \in W_{e}$ whenever $W_{e} \neq \emptyset$? (Here $W_{e}$ denotes the $e^{\text{th}}$ c.e. set.) My only solution is to ...
4
votes
4answers
158 views

**symbol** of a mapping vs. mapping itself /understand the definition of “structure”

I am having problems understanding the definition of a "structure" in universal algebra. In my course in was introduced in the following way: "A structure $S$ consists of an underlying set ...
0
votes
2answers
683 views

Help me to solve with equivalent functions to Disjunctive.normal.form

How I can solve this? I'm really stupid in this logical "math", but if I see example maybe I will understand. Help me with using logical equivalences. Show me please every step; and let's try to ...
11
votes
0answers
367 views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
3
votes
1answer
470 views

Practice Problems on the Elimination of Quantifiers

In a recent answer, JDH gave a remarkable proof that the integers are not definable in the structure $(\mathbb{Q},+,<)$ using Quantifier Elimination. Since I already have the old Enderton book, are ...
7
votes
1answer
139 views

Are there any strongly axiomatizable logics that are not compact?

I mean here a logic in the sense of a language and semantics. By strongly axiomatizable I mean strongly sound and strongly complete. So I'm basically asking if there is a particular deductive system ...
4
votes
1answer
121 views

What's wrong with this inference in natural deduction?

Could anybody explain to me what's wrong with the following inference? Thanks. $--- u$ $P(a)$ $---- {\forall}I^a$ $\forall x . P(x)$ $---- {\forall}E$ $P(b)$ $------ {\supset}I^u$ $P(a) ...
5
votes
3answers
182 views

Test whether an interval contains integer points

I want to make a non-complex (for algorithmic implementation) logical condition to test whether some real interval contains any integer points. Let $x$ be an interval with bounds $l, r$; Let ...
2
votes
1answer
194 views

Superposition calculus and equality factoring

Superposition with equality resolution and equality factoring is said to be a complete calculus for first-order logic. The purpose of equality factoring is basically to get rid of paraduplicate ...
4
votes
4answers
151 views

What is the symmetry between the definitions of the bounded universal/existential quantifiers?

What is the symmetry between the definitions of the bounded universal/existential quantifiers? $\forall x \in A, B(x)$ means $\forall x (x \in A \rightarrow B(x))$ $\exists x \in A, B(x)$ means ...
21
votes
1answer
358 views

FO-definability of the integers in (Q, +, <)

With $Q$ the set of rational numbers, I'm wondering: Is the predicate "Int($x$) $\equiv$ $x$ is an integer" first-order definable in $(Q, +, <)$ where there is one additional constant symbol ...
1
vote
1answer
61 views

How to show that a set does not contain a specific string

If I have a set $S$ defined as the smallest set $S$ over an alphabet $A=\left\{ \star, \urcorner,(,), a_0,a_1, \dots \right\}$ ( $S\subseteq \cup_{k \in \mathbb{N}} A^k$) satisfying: $\bullet \ a_0, ...
2
votes
1answer
303 views

What does it mean: “the closure of the axioms”?

«As we shall see, the logical axioms are so designed that the logical consequences (in the semantic sense, cf. p. 56) of the closure of the axioms of $K$ are precisely the theorems of $K$.» Page 60 ...
2
votes
3answers
200 views

A question on logic - where intuition can fail

Suppose I have two predicates $P(x)$ and $Q(x)$, such that $\overline{P(x)\wedge Q(x)}$ holds for all $x$. Now, if $\displaystyle \bigwedge_{x\in A}P(x)$ for a set $A$, it must be certainly true, ...
4
votes
1answer
4k views

Logic Puzzle of the age of three sons

There is a puzzle, it goes something like this: Someone talks to a guy, and asks, Give me the age of my three sons, The other guy asks for some clues: The product of the age of the three sons (of ...
2
votes
1answer
226 views

Nash equilibrium and common knowledge

If NE is a CK? It seems that yes since given all information about payoffs/strategies players can derive NE based on the procedures similar to that of in the common knowledge, but I'm not sure.
6
votes
4answers
697 views

A naive inquiry of Godel's incompleteness--or why does mathematics need proofs of unprovability?

My question stems from reading Swetz, 1994 (mostly excerpts from the journal Mathematics Teacher) and Berlinski, 2005 (a popular book on 10 most important mathematical breakthroughs in history). 1) ...
1
vote
2answers
159 views

Informal Equivalents of Mathematica “Set” and “SetDelayed”

How would one distinguish between what is meant by Mathematica's "Set" and "SetDelayed" functions in informal mathematical notation? Is there a way to make this distinction any any reasonably standard ...
1
vote
4answers
477 views

Logic problem - what kind of logic is it?

I would be most gratefull, if someone could verify my solution to this problem. ...
4
votes
2answers
4k views

What is the difference between a predicate and function?

I need to to understand the difference between predicates and functions in the context of Clasual Form Logic in order to define the Herbrand universe. If I have p(x) :- q(f(x)) would I be right in ...
8
votes
1answer
343 views

Common knowledge as a fixed point

I read on a wikipedia page that from the modal logic formalization CK can be formulated as a fixed point. If it also holds for the set theory formalization? If it does, where I can find about it? ...
2
votes
1answer
183 views

Construction of a sequence of theorems with increasing and unbounded “difficulty”?

Let's define the "difficulty" of a theorem as the logarithm of the size of its shortest proof divided by the logarithm of the size of the theorem itself. For example, if a theorem has difficulty less ...
11
votes
3answers
796 views

Why truth table is not used in logic?

One day, I bought Principia Mathematica and saw a lot of proofs of logical equations, such as $\vdash p \implies p$ or $\vdash \lnot (p \wedge \lnot p)$. (Of course there's bunch of proofs about ...
6
votes
2answers
203 views

Boolean algebras without atoms

Why is the theory of Boolean algebras without atoms $\omega$-categoric?
5
votes
2answers
266 views

$\omega$-saturation of $(\mathbb{R},<)$

Could anyone of you explain me why $(\mathbb{R},<)$ is $\omega$-saturated? EDIT: do you know also why the theory of Boole algebras without atoms is $\omega$-categoric? Added: The added question ...
5
votes
3answers
220 views

Recursive function that outputs its own code

This problem is probably a rather trivial one, since I have the impression, that it is a textbook-style one, but nonetheless somehow it won't give in. Here it is: I have to show that there exists a ...
9
votes
2answers
263 views

How to show the existence of an infinite set of independent undecidable sentences?

How to show the existence of an infinite set of independent undecidable sentences? By "independent" I mean that no implication between any two elements is provable. A finite set that satisfies the ...
7
votes
5answers
1k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
7
votes
1answer
202 views

Understanding an Easy Relative Consistency Proof

When proving that $(ZF-Reg)\vdash CON(ZF - Reg)\rightarrow CON(ZF)$ we start by defining the class $WF=\cup_{\alpha \in ORD} V_{\alpha}$. Then we prove with $ZF-Reg$ that actually $WF$ is a model for ...
5
votes
1answer
100 views

Basic constructibility question

I'm currently reading J. D. Hamkins' paper "Unfoldable cardinals and the GCH," and I've run across a comment that I think I ought to find trivial, but I don't. On page 1187, he says that ...
11
votes
7answers
9k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
3
votes
2answers
2k views

Finding Boolean/Logical Expressions for truth tables

I need to find the Boolean expression for the truth table below where $P$, $Q$, $R$ are inputs, and $S$ is the output. Does anyone have a cool easy way of solving such problems please? Your help will ...
3
votes
3answers
87 views

Induction on logic formula

The term $((\bigvee_{i=1}^{n} p_i) \wedge (\bigwedge_{i=1}^{n} (p_i \to p)) \to p$ should be proven through induction. I'm relatively new to it, but I started with: basis: $p(1): (p_1 \wedge (p_1 \to ...
0
votes
1answer
95 views

computable function

Let $f$ be the function that maps the godel number of each proposition P in PA to 0 if P is provable false and 1 if P is provable true and 2 if P is independent of PA. Then $f$ is not computable. Is ...
4
votes
1answer
349 views

Does the Huntington axiom follow from $x \vee x = x$ and $\neg \neg x = x$?

Let’s consider algebras with the following axioms in addition to commutativity and associativity: $$x \vee x=x$$ $$\neg \neg x = x$$ Does the Huntington axiom ( $\neg (\neg x \vee y) \vee \neg (\neg ...