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)

1
vote
0answers
164 views

Does fiber product always exist?

Let $X,Y,S$ are schemes, and $f:X\to S, g:Y \to S$ are morphisms, does fiber product $X\times_S Y$ always exist in the usual sense(for example as defined in Hartshorne )? Here is an interesting ...
1
vote
0answers
70 views

Differential fields and rings

If one is to compute the derivative of $$ y=3x+2 $$ by $$ \frac{\mathrm{d}(3x+2)}{\mathrm{d} x} $$ Would I be working with differential fields? Since differential fields is a first-order ...
1
vote
0answers
182 views

Can the reduced product construction generate boolean-valued models?

In model theory, the reduced product construction contains a collection of structures or models, a set I that indexes the collection, and a filter U on I. Ultraproducts are a special case of reduced ...
1
vote
0answers
192 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, ...
0
votes
0answers
27 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
0
votes
0answers
20 views

Connection between quantifier rank and Ehrenfeucht-Fraïssé Games

"Two $\tau$-structures $\mathfrak{A}, \mathfrak{B}$ are $m$-equivalent ($\mathfrak{A} \equiv_{m} \mathfrak{B}$) when... $\mathfrak{A} \models \psi$ iff $\mathfrak{B} \models \psi $ for all ...
0
votes
0answers
21 views

computational complexity theory(factorial)

I wanted to ask which class does factorial problems belongs to? there is the naive algorithm that solves the factorial factorial(n) = factorial(n-1) * n. but it is exponential in the length of the ...
0
votes
0answers
30 views

Sum of function applied to parts not equal to function of total

The general goal is to determine the effectiveness of the test pill's ability to keep the test subjects from getting sick using the following data. | Test Subjects | Took Test Pill | ...
0
votes
0answers
62 views

Relation between existential and universal quantificator in category theory

Let $\mathscr C$ be a cartesian (i.e. with finite limits) category with subobject classifier $\Omega$ and generic subobject $\tau:I\to\Omega$ (here $I$ denote the terminal object). Let $f:X\to Y$ and ...
0
votes
0answers
42 views

predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
0
votes
0answers
51 views

I'm looking for a formula to be applied on a game

I've been working on a game and I need to implement a feature, but I still haven't found a good formula for it. The problem is the following: Each team has X points, and all teams are able to ...
0
votes
0answers
17 views

Analogue of Herbrand Disjunction for Negative Side of the Clark Completion?

For Horn clauses there is the following result. If T is a set of Horn clauses and p is a predicate, and if p is an existential consequence of T: ...
0
votes
0answers
25 views

When is the higher-order theory of a model categorical?

I'm interested in (classical) type theories $L$ with the following property. For $M$ any model of $L$ (in Set), let $T(M)$ be the type theory of $M$, i.e., the strongest extension of $L$ satisfied by ...
0
votes
0answers
22 views

Logical implication which is also known as rules of inference.

What is logical implication?? This is not a conditional connective -> . This is also known as rules of inference. Please explain it properly.
0
votes
0answers
140 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
0answers
48 views

Power of 3 Elimination Tournament Seeding

Most tournaments are $1$-on-$1$. They use seeding system where $1$ v $16$, $2$ v $15$... $1$ v $16$ $8$ v $9$ $5$ v $12$ $4$ v $13$ $6$ v $11$ $3$ v $14$ $7$ v $10$ $2$ v $15$ is correct assignment ...
0
votes
0answers
23 views

proof of quantifier elimination in theory of real closed field/reals and existential quantifier over atomic formula

Standard proof of quantifier elimination for theory of real closed field/reals uses induction, as in Wikipedia article (http://en.wikipedia.org/wiki/Quantifier_elimination#Basic_ideas). However, it ...
0
votes
0answers
41 views

simple exercise in Cylindric algebra

I am trying to gain a better understanding of cylindric algebra, so I made up this example. Given a general rule that someone's father's father is his/her grandfather: $\forall_X ~ \forall_Y ~ ...
0
votes
0answers
46 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
0
votes
0answers
30 views

Most suitable book after Bergmann Logic Book

I'd like to know what the best book would be to pick up after this one would be. Essentially, it covers basic logical concepts (validity, soundness, consistency) and goes on to sentential and ...
0
votes
0answers
32 views

Italic notation in logic

I have seen some books on formal logic where variables are written in italic, while statements are upright. Hence a statement could like like $\mathrm A(x_1, \ldots, x_n)$. How much of a standard is ...
0
votes
0answers
29 views

XOR with multiply operation.

can I do that $((A*5) \oplus A)==A*(5\oplus1)?$ and that $(A \oplus B/2) == ((2*A) \oplus B)$? Thanks.
0
votes
0answers
62 views

TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
0
votes
0answers
26 views

Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?

Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
0
votes
0answers
71 views

Primitive Recursive Predicate Challenge

I'm an Computer scientist, and I recently ran into a challenge. If we have primitive recursive predicate $P(x), Q(x)$, I think that all of following 4 expressions can be primitive recursive. Any hint ...
0
votes
0answers
46 views

Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
0
votes
0answers
40 views

The Major Weaknesses in Ramified Type Theory

I am reviewing a paper on the major weaknesses of Ramified Type Theory in predicative second-order arithmetic. These four are listed as "weaknesses." But, I have my doubts. It seems at least that 3) ...
0
votes
0answers
67 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
0
votes
0answers
44 views

Proof: All recursive functions are arithmetic (logic)

So I'm trying to understand the proof of the following statement: > All recursive functions are arithmetic The proof begins with: "It is sufficient to show that all arithmetic functions satisfy ...
0
votes
0answers
25 views

What are all of the computable or semidecidable properties of a first order sentence?

I'm interested in features of first order theories that can be used to differentiate first order sentences from each other in hopes there might be some way of measuring what makes one sentence more ...
0
votes
0answers
44 views

How do I convert the following sentences in first-order logic?

How do I convert the following sentences in first-order logic? Someone bought a bike and they are driving it. Peter and Mary met. Whoever runs, falls. John doesn't love Mary but ...
0
votes
0answers
19 views

Find a depending formula

I cant find a literature that can help me with this question. We have x1, x2, x3 and y (over 1000 examples). x1 x2 x3 y 1 2 3 10 1 10 0 2 etc y is ...
0
votes
0answers
44 views

Finding simpler implied formulas while preserving contradiction

I have two Presburger formulas A and B such that $A\land B \equiv \text{False}$. From these I need to find shorter formula $A'$ such that $A \rightarrow A'$ and $A' \land B \equiv \text{False}.$ The ...
0
votes
0answers
89 views

Dividing line between useful ( for non-foudational Math ) and unnecesary, in Foudational Math.

I started studying mathematical logic because I was curious about the behind-the-scenes of proofs, theorems and axiom systems of math. I'm interested in understanding the big picture that ...
0
votes
0answers
36 views

A knight, a knave and a normal. I am gonna ask one of them a question that can be replied using yes or no.

They are each named a, b, c. What could I ask to determine their identities. One of the diagram I learn about logic with plus and minus sign, is ++=--=+. Does anyone know the trick of using this sort ...
0
votes
0answers
32 views

Algorithm for determining whether one formula in propositional logic is a substitution of another?

In propositional logic, one formula A is a substitution instance of another formula B just in case A is obtainable from B by a series of uniform substitutions. A uniform substitution is obtained just ...
0
votes
0answers
43 views

Write theorem conditions concisely

Let $Z$ be a set, $x$ be some object. Let the following statements hold (for some logical formulas $P,P_1,\dots,P_n$ and some logical formula $Q$): $\forall z\in Z:(P(x) \Leftrightarrow Q(x,z))$ ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
0answers
36 views

Representing a relation in True Arithmetic

How to write a formula $A(x, y)$ which represents the relation $(y=f(x))$ in True Arithmetic? The formula for $A(x, y)$ can use a formula $B(c, d, i, y)$ that represents the graph of Godel $β$ ...
0
votes
0answers
60 views

Brute-force searches for counterexamples

Gödel's completeness theorem says that for every statement in first-order predicate caluculus with equality, there is either a proof that it holds in all structures, or a counterexample --- a ...
0
votes
0answers
62 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
0
votes
0answers
58 views

What do we call functions that are definable by expressions?

Let $X$ denote a model of an algebraic theory $T$. What do we call the functions $f : X^n \rightarrow X$ that are definable by some expression in the language of $T$? e.g. If $S_3$ is the symmetric ...
0
votes
0answers
50 views

The unique model of cardinal $\kappa$ of a $\kappa$-categorical countable theory is saturated.

Let $T$ be a $\kappa$-categorical ($\kappa \geq \aleph_1$) first-order theory in a countable language $\mathcal L$. I try to prove that its unique (up to isomorphism) model of cardinal $\kappa$ is ...
0
votes
0answers
26 views

Logic and Circuits Proof

How would you go about proving that a circuit can be constructed from AND, OR, and NOTs with certain restraints? For example, how would you prove it possible to construct a circuit with $n \geq 2$ ...
0
votes
0answers
86 views

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
0
votes
0answers
47 views

Proof within Hilbert system

I'm trying to proof a formula in the Hilbert system. First of all, I have a question whether a certain step is allowed. Provided that the theorem ⊢A→A has already been proven in the Hilbert system. ...
0
votes
0answers
45 views

Number of Interpretations in First Order Predicate Logic

I'm interesting in understanding how to calculate the number of interpretations in first order predicate logic using: a) at most one property variable b) at most two property variables. I'm trying to ...
0
votes
0answers
54 views

Non-Standard Arithmetic - order

Recently I try to figure out some facts about one specific way of "constructing" a non-standard model for (peano) arithmetic. I guess there are answer to my question already out there, but somehow I ...
0
votes
0answers
39 views

logic - how to model or diagram conditional probabilities of multiple related scenarios.

I am interested in modeling questions and specific outcomes so that i can evaluate conditional probabilities and mathematical expectation. I am looking for a way to diagram or otherwise describe the ...
0
votes
0answers
47 views

Translate n xor expressions to CNF?

I have n xor expressions: a xor b xor c xor d... I want to translate to cnf: The answer of cnf can be found here: http://www.wolframalpha.com/input/?i=a++XOR+b++XOR+c+XOR+d+ I want to write a ...