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

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...
1
vote
0answers
76 views

Ultrapowers by extenders of potential premice

I have a problem with an argument in Fine structure and iteration trees by Mitchell and Steel. Let $E$ be a $(\kappa, \lambda)$-extender. Let $\dot E^{\mathcal{M}}$ the a unary predicate with is ...
1
vote
0answers
77 views

Generating Input Binary Combination Dynamically

this is probably right forum to post this question I am currently working on a application where there is a requirement to generate binary combination of input signals in a truth table. The signal ...
1
vote
0answers
112 views

Mathematical formulation of 'Indra's net'

Quoting Wikipedia: "Imagine a multidimensional spider's web in the early morning covered with dew drops. And every dew drop contains the reflection of all the other dew drops. And, in each ...
1
vote
0answers
75 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
1
vote
0answers
96 views

translation of a sentence in FOL using Skolem functions

Consider the first-order sentence (1) $\forall x\exists y(\forall z Dxz\to\exists z\neg Dyz)$ and interpret Dab as the two-place relation "a has doubts about b." On a recent exam, I translated the ...
1
vote
0answers
102 views

Proving that a formula cannot be proven (has no formal proof) in a given deduction system

In my homework I was asked to prove that a deduction system for modal logic with $\rightarrow$, $\neg$ and $\square$, with 4 axioms and 2 inference rules (MP and a $\square$-generalization rule), is ...
1
vote
0answers
157 views

Forcing and divisibility

I'm going to bring together a couple of seemingly unrelated questions that I've asked here. This may be silly. Or maybe not? Imagine that $n$ is some sort of infinitely large integer, and thus so ...
1
vote
0answers
165 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
71 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
184 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
196 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
23 views

Applying De Morgan's Law

I'm working on my assignment for Discrete Math and I'm not fully understanding how to do this question for it so I was wondering if anyone here could help show me how to do it properly; Use De ...
0
votes
0answers
10 views

how to do classification of topological space which a poset is a frame

is module in algebraic geometry for classification of topological space which a poset is a frame which invariant is for doing this classification of topological space? if want to do full combination ...
0
votes
0answers
35 views

Let T(x,y) mean “x is a teacher of y”. What do the following statements mean? Are they true?

∃!yT(x,y) ∃x∃!yT(x,y) ∃!x∃!yT(x,y) ∃x∃y[T(x,y) ∧ ¬∃u∃v(T(u,v) ∧ (u≠x ∨ v≠y))] For the first one, is the meaning: There is one and only student that has teacher x? Am I on the right track with ...
0
votes
0answers
22 views

proove logical consequence - my solution

I wounder if I have done right. You can find the question at Question 1b I know that $(1)$ $P_1∧(P_2∨P_3)$ ≈ $(P_1∧P_2)∨(P_1∧P_3)$ which means that these two formulas have the same thruth value in ...
0
votes
0answers
20 views

Expanding a logical expression

I need help understanding the following notation. I tried to expand it and that's where I realized I didn't quite get it. How do you expand the following: $${\underset{i=1}{\stackrel{3}{\bigwedge}}} ...
0
votes
0answers
34 views

Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...
0
votes
0answers
22 views

If an open sentence is always true for all values of the variable(s) in it, is it still an open sentence or is it considered a statement?

for example, x + y = y + x and 2(x + 7) = 2x + 14. Could they be considered as statements? also, is it possible a sentence considered as both an open sentence and statement?
0
votes
0answers
32 views

How can I represent these discrete math statements with predicates and quantifiers?

Use the predicate $A(x, y)$ that denotes ("$x$ loves $y$") Someone loves a person who loves everyone. Everyone loves someone who is loved by someone. I know I need to use nested universal and ...
0
votes
0answers
34 views

Logical Notations for Descriptive Mathematical Statements

I'm studying Discrete mathematics and I'm faced with a problem of converting a descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a). Any integer ...
0
votes
0answers
30 views

Understanding why a disjunctive normal form is equivalent to the proposition

I'm having trouble understanding the equivalence relation bet. a proposition and its disjunctive normal form (DNF). For example, in the example on p.51 ...
0
votes
0answers
28 views

LUB property in a predicative logic

Is there a formulation of real analysis in a predicative logical system such that the LUB property is available? Here is a quote from http://en.wikipedia.org/wiki/Impredicativity : "Kleene uses the ...
0
votes
0answers
31 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
21 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
24 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
70 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
44 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
53 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
27 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
25 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
49 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
26 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
31 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
35 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
63 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
28 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
72 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
41 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
70 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
45 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
20 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 ...