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)

0
votes
1answer
12 views

About the definition of axiomatizable theory and consistency

Definition: If $A$ is a theory and $B \subseteq A$ then $B$ is a set of axioms for $A$ iff 1) B is recursive and 2) $B \models C$ for all $C \in A$. We say $A$ is axiomatizable iff $A$ has a ...
0
votes
2answers
32 views

How to mathematically calculate the indistinguisable and distinct of the following permutation problems?

I'm having trouble calculating how many indistinguishable and distinct solutions there are for each problems. I'm pretty confident with some of my solutions, but could anyone show me mathematically ...
0
votes
2answers
35 views

Quantified Logic with miltuple variables

Problem: ∀y¬∃x¬(¬Fxy ∨ Fyx) ⊢ ∀y∀z(Fyz→Fzy) I don't really understand how to deal with multiple variables in instances like this. So far I have: ...
0
votes
1answer
60 views

Provable formulas in everyday Mathematics

Basically all statements ( lemmas, theoremas, corollaries ) in Mathematics can be expressed as a conditional statement in first-order language, or existential statement ( existence proofs ). Here ...
0
votes
1answer
71 views

Mathematical logic

Given: $[(A \lor B) \land (A \lor C)] \rightarrow [A \lor (B \land C)]$; $\lnot((x_1 < x_2) \rightarrow (x_1 \cdot x_3 > x_2 \cdot x_3))$ $\forall x_2:f_1^2(x_2, x_3) \rightarrow ...
0
votes
1answer
32 views

How to prove $\vdash (\forall v_1 \,\exists v_2\, fv_1=v_2)$

f is a one-place function symbol. I just don't know where to start. $\forall v_1 \,\exists v_2\, fv_1=v_2$ might come from $\exists v_2 \,fv_1=v_2$ Then I don't know how to deal with the "exists"
2
votes
2answers
80 views

How can the Gödel sentence be Pi_1

The Gödel sentence must be provable or unprovable by itself - you have to resolve all definitions until it only uses the elementary symbols of Peano arithmetic. What is the correct way to resolve ...
3
votes
0answers
24 views

Linear regression, reversing it back then.

This is my first Question. I am performing linear regression upon set of floating point between 0 and 1. there are few hundred points.once the slope and intercept is found for first iteration,the ...
4
votes
1answer
242 views

How can I prove that there is no set containing itself without using axiom of foundation?

I've already found some similar questions in here (and other sites), but in most of the case, the use of axiom of foundation is required to complete the proof. Is there any way to prove $\not\exists ...
0
votes
0answers
17 views

Basic questions about descriptive complexity

I'm trying to learn descriptive complexity, and I'm having trouble on a basic level wrapping my head around what it means for a logical formula to define a computational language. I've tried and ...
2
votes
0answers
31 views

3-Coloring a graph using propositional formulas

Hello everyone I am studying for an exam on logic and computability, I am trying to tackle a specific problem so any help would be greatly appreciated: Let $G = (V,E)$ be an undirected graph ...
2
votes
1answer
22 views

building truth-functional connectives

It is known that $NAND$ and $XOR$ are the only one $2$-argument truth-functional connectives that can be used alone to create every $n$-argument truth-functional connective for all positive integer ...
1
vote
2answers
28 views

Resolving a contradiction in the proof of expected value of Binomial distribution

I've seen this proof in a text. I have an issue with it and wanted to check its validity. Let $X\sim B(n,p)$, we seek the expectation. We let $q=1-p$ \begin{equation} E(X)=\sum_{j=0}^{n} j {n\choose ...
3
votes
2answers
71 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
2
votes
1answer
42 views

Is saying 'This statement is true' a logically valid statement?

I understand how 'This statement is false' is not logically valid, but what about 'This statement is true'? I've always heard self-referential statements are not logically sound, but I can't really ...
-2
votes
0answers
43 views

Boole's functions' domain is D = {1, 2, 3, 4}. Find ∃xF(x, 2), when F(x, y) = 1100 1111 0011 0101. [on hold]

The problem is, I actually do not understand this problem very well. When the logical function is given, making truth table is not a problem for me at all. I wonder, if this exercise requires to make ...
1
vote
1answer
31 views

Show that there exists a satisfactory assignment for the unstandard language of arithmetic $\{\textbf{0}, ', <_1\}$

Consider: $A1: \textbf{0} \not = x'$ $A2: x'=y' \rightarrow x = y$ $A3: \neg x < \textbf{0}$ $A4: x < y' \leftrightarrow (x < y \vee x = y)$ $A5: \textbf{0} < y ...
0
votes
1answer
42 views

Show that $ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $ is, in general, NOT a theorem.

Show that $$ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $$ is, in general, NOT a theorem. My answer: First, I got the abstraction of the formula which is $ p \rightarrow A \lor q$ then ...
1
vote
1answer
41 views

Do all contradictory statements entail something self-referential?

"The house is all blue(B), and the house is all white(W)" Those statements are, ostensibly, not of the form p ⋀ ¬p. However, they do seem to entail p ⋀ ¬p. For example "The house is all blue" entails ...
1
vote
1answer
26 views

Can covering be done on two elements?

The covering rule is: $$B \bullet (B+C) = B$$ and $$B+(B \bullet C)=B$$ So does it follow from this rule that: $$B \bullet A \bullet \bar{C} + B \bullet D \bullet\bar{F} = B \bullet ...
1
vote
1answer
50 views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
1
vote
2answers
42 views

How to find the Equivalence class for a given set?

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and ...
3
votes
2answers
76 views

If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
2
votes
2answers
61 views

What does it mean for a set of sentences $\mathcal{T}$ to “secure” a set of sentences $\Delta$?

I know the standard interpretation is: $\mathcal{T}$ secures $\Delta$ iff every interpretation that makes all members of $\mathcal{T}$ true makes at least one member of $\Delta$ true. ...
1
vote
1answer
46 views

Give an equational proof $ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$

Give an equational proof $$ \vdash (\forall x)(A \rightarrow (\exists x)B) \equiv ((\exists x)A \rightarrow (\exists x)B)$$ I don't know where to start. Maybe I could start with $ (\forall x)(A ...
2
votes
2answers
94 views

Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
0
votes
1answer
43 views

First order logic tableaux with multiple quantifiers

I find very confusing to understand how combined qualifiers might expand on a tableaux. While for $\exists x\ p(x)$, I would just create a new term, a, and for $\forall x\ p(x)$ I would use an ...
3
votes
3answers
49 views

General Strategy for Derivations in Propositional Logic

In Propositional Logic, one is often tasked with showing that some particular formula is a theorem of a given deductive system, i.e. $\emptyset \vdash \psi$. These formulas can look very simple and ...
1
vote
1answer
49 views

What exactly does $\vdash_T G_T \leftrightarrow \lnot \exists y$ Prf$(\ulcorner G_T \urcorner, y)$ mean?

To me this translates to: $G_T$ is provable in $T$ if and only if there doesn't exist a $y$ such that $y$ is a witness to the provability of $\ulcorner G_T \urcorner$. But I'm not entirely sure what ...
1
vote
1answer
24 views

The approximation rule implies the equality rule in systems of type assignments

I'm reading Barendregt's Lambda calculi with types (1992). In Proposition 4.1.4.1., he "proves" a lemma which shows the approximation rule implies the equality rule in typed lambda-calculi à la ...
2
votes
2answers
50 views

Give a Hilbert-style proof $ \vdash ( x=y \rightarrow y = x) $

Give a Hilbert-style proof $$ \vdash ( x=y \rightarrow y = x) $$ I don't know where to start. I thought maybe I can use Ax5 (Identity axiom) $ x = x $ as a starting point. See George Tourlakis, ...
3
votes
1answer
37 views

Give an equational proof $ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $

Give an equational proof $$ \vdash (\exists x)(A \lor B) \equiv (\exists x)A \lor (\exists x)B $$ What I tried $(\exists x)(A \lor B)$ Applying Definition of $\exists$ $\lnot (\forall ...
42
votes
8answers
4k views

Is it possible that “A counter-example exists but it cannot be found”

Then otherwise the sentence "It is not possible for someone to find a counter-example" would be a proof. I mean, are there some hypotheses that are false but the counter-example is somewhere we ...
0
votes
1answer
43 views

Implication or Bidirectional in “x is a Prime”

I have a question regarding First Order Logic. I have to express the property "x is a Prime" in First Order logic. So far I have the following solution: $\forall x\;Prime(x) \leftrightarrow \neg ...
1
vote
1answer
27 views

Give an equational proof $ \vdash (p \lor \lnot r) \rightarrow (p \lor q) \equiv \lnot q \rightarrow (r \lor p)$

Give an equational proof $$ \vdash (p \lor \lnot r) \rightarrow (p \lor q) \equiv \lnot q \rightarrow (r \lor p)$$ What I tried $(p \lor \lnot r) \rightarrow (p \lor q)$ Applying De morgan ...
1
vote
0answers
31 views

Poisson process: Has my book used a necessary condition, when it should have used a sufficient condition?

My book says that if we know that if we are viewing a poisson process with length $t$, and know that $n$ events happened in that interval, than the time that any of those events happened is uniformly ...
3
votes
1answer
46 views

Equivalence of Deductive System $L_0$ and the Sequent Calculus

Let $\mathcal{L}_0=\mathcal{L}[\{\neg, \rightarrow\}]$. Define the system $L_0$ as follows: An axiom of $L_0$ is any formula of $\mathcal{L}_0$ of the form (A1) $(\alpha \rightarrow ( \beta ...
4
votes
1answer
74 views

In Whitehead and Russell's PM, are overlapping ranges of significance necessarily identical?

In Principia Mathematica summary of ✳63 In virtue of ✳20.8, we have $\vdash : \phi a ∨ \sim\phi a . ⊃ . \hat{x}(\phi x \vee \sim \phi x ) =t‘a$ i.e. if "$\phi a$" is significant, then ...
1
vote
2answers
53 views

Construct the truth table?

Any body help me .. How to solve this? (i) $(p\land q)\to (p \leftrightarrow (q \lor r))$ (ii) $(p \leftrightarrow q) \leftrightarrow ((p\land q) \lor (\neg q \land \neg p))$ (iii) ...
2
votes
2answers
76 views

How to write negation of statements?

How to write negation of following statements in words? ...
1
vote
1answer
39 views

Why exactly are NAND and NOR the only universal binary logic functions?

We know there are 16 possible binary logic functions: ...
2
votes
0answers
40 views

Simplify Product of Sums

Similar question to: Boolean Algebra - Product of Sums I was given a truth table and asked to give the sums-of-products and the product-of-sums expressions. I reduced the sums-of-products ...
3
votes
6answers
610 views

Question about the Continuum Hypothesis

The Continuum Hypothesis hypothesises There is no set whose cardinality is strictly between that of the integers and the real numbers. Clearly this is either true or false - there either exists ...
1
vote
1answer
65 views

How does one avoid circular reasoning? [closed]

How can you be reasonably assured that you are not engaging in circular reasoning when you invoke a theorem, lemma, etc.? For instance, what if you accidentally "prove" a theorem using a consequence ...
-3
votes
1answer
57 views

Give an equational proof $ \vdash p \land (q \equiv p) \equiv p \land q $

Give an equational proof of $$ \vdash p \land (q \equiv p) \equiv p \land q $$ How can I give equational proof for this formula ? See George Tourlakis, Mathematical Logic (2008) or this post for a ...
1
vote
1answer
49 views

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema?

Is $ (\forall x)(A \rightarrow B \land C) \rightarrow (\forall x)(A \rightarrow B) $ an absolute theorem schema ? If you think 'yes', then give a proof. If you think 'no', construct a counter model ...
0
votes
1answer
26 views

What is “Standardizing variables” in the procedure of converting First Order Logic to CNF?

What is meant by the step "Standardize variables" in the procedure of converting First Order Logic to CNF? The 6 all steps can be listed as, ...
1
vote
1answer
34 views

Converting statements with term 'only' and 'any' to predicate logic

How to convert following statement into predicate logic? 1)"Only dogs are mammals" 2)"Any dog is a mammal" Is there a difference between "Any dog is a mammal" ...
5
votes
2answers
117 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
1
vote
1answer
61 views

Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...