Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

2
votes
1answer
44 views

Functor between ordered sets.

(a) Let $f : K \rightarrow L$ be a map of sets, and denote by $f^* : \mathscr{P}(L) \rightarrow \mathscr{P}(K)$ the map sending a subset $S$ of $L$ to its inverse image $f^{-1 }[S] \subseteq K$. ...
2
votes
1answer
73 views

In meta-math does the sequence matter for $\bf ∀x$?

For example, if I have an axiom starting with $\bf ∀x∀x'\dots$ , would it still be an axiom if the only difference is that the sequence has changed to $\bf∀x'∀x\dots$?
1
vote
0answers
21 views

If $T$ is a set, $P(x)$ denotes x is a hard worker and $D(x)$ denotes that $x$ is a worker, how to translate the following to English sentence?

So $T$ is a set of workers and materials in a tower, $P(x)$ denotes that $x$ is a hard worker and $D(x)$ denotes that $x$ is a worker $\forall x \in T: [D(x) \rightarrow [\exists y \in T: P(y)]]$ ...
0
votes
1answer
25 views

Definition of variables in propositional calculus

Let $\tilde P$ be a first order algebra, and consider the definitions below: I'm confused about the very last thing: what $y\not\in V(c)$ means. $c$ has a free variable, so what does it mean to say ...
3
votes
1answer
29 views

What is a “prime implicent”?

What is a "prime implicent"? I guess it's also the "prime implicant". The wiki page is too hard for me to understand. Can someone explain it in simpler terms?
1
vote
0answers
34 views

Translate from logical expression to regular expression

I have a type of exercise in which I want to translate a formal logical expression to regular expression. Now my question is, is there a set of rules which I can learn so I will be able to do this ...
0
votes
1answer
33 views

Extension of a theory vs conservative extension

I'm not sure whether I get the difference between extension $T'$ of some theory $T$ and conservative extension $T''$ of this theory. Extension $T'$ of $T$: Language $L\{P\}$ and it's theory $T$ ...
1
vote
0answers
37 views

Checking if $p$ tautologically implies $q$

What is the difference between $p\Rightarrow q$ and $p\to q$? Is $p\to q$ a necessary and sufficient condition for checking $p\Rightarrow q$ is a tautology? Are there alternative approaches?
3
votes
2answers
38 views

Multiple possible interpretation for negation of a statement

For the statement below: One of my two cars was stolen. What is the negation? For me, it seems like there are two ways of interpreting this. First, if we interpret the statement as: $N = $ ...
1
vote
3answers
78 views

Propositional Logic- Prove sentences (a) and (b) entail (c)

I'm given three sentences: (a) If Frodo destroys the ring, then the world will be saved. (b) Gollum stole the ring from Frodo or Frodo destroyed the ring. (c) The world will be saved or Gollum stole ...
0
votes
1answer
17 views

Reducing propositional logic statements

I am having some trouble with reducing some propositional logic statements. The first one is as follows: $\neg(P \lor Q) \lor \neg (P \lor \neg Q)$. I used deMorgan's law to change this to: ...
0
votes
1answer
34 views

Verification of Lindenbaum's Lemma proof for the Mendelson system and a question of maximally consistent sets.

In this proof I will use Mendelson's axiom system (the one in this book). Question 1: Could someone check my work? I feel some parts are a bit hard to see/read, but I think the general idea ...
1
vote
1answer
39 views

Have some trouble proving $(1-x)^n \geq 1-nx$

Here is the question: Prove that $(1-x)^n \geq 1-nx,~\forall n\in\mathbb{N}~and~x\in(0,1)$. My proof by induction: Base Case: when $n=1$, $(1-x)^1\geq 1-1\cdot x$ Induction Hypothesis: $\forall i \in ...
1
vote
1answer
32 views

Logic - Proving or disproving a formula is satisfiable

I want to find out if the formula $\{p\implies(q\land r),(p\lor r)\implies q,\neg r\}$ is satisfiable. (meanings each clause is satisfiable. there is an $\land$ between the clauses. The problem is ...
0
votes
2answers
60 views

In the structure $\langle \mathbb{Q}, < \rangle$ which of the ZF axioms hold?

In the structure $\langle \mathbb{Q}, < \rangle$ which of the following axioms hold? How about when we use the weak versions of the axioms (all $\leftrightarrow$ replaced with $\rightarrow$ )? ...
1
vote
0answers
22 views

Question in regards to representing propositons with P/~P

In a standard Frege-System does it break any rules to have 'P' stand for, say "Smith is not president"? Is it mandatory that such a statement be represented by '~P', or can it indeed be represented ...
0
votes
1answer
47 views

writing a formal proof

If B is a statement form involving only negation, conjunction and disjunction, and B' results from B by replacing each conjunction by a disjunction and each disjunction by a conjunction, show that B ...
0
votes
1answer
35 views

Prove that if an existential formula A is satisfiable in a countable structure, then it's valid

Question Prove that if an existential formula A is satisfiable in EVERY countable structure, then it's valid. Proof: My proof is that $B=\lnot A$ is universal so if B is not satisfiable in any ...
1
vote
1answer
62 views

Is the definition of recursive function unchanged if we restrict substitution to binary composition?

When defining recursive functions, are the following two statements equivalent?$$f:\mathbb{N}^n\rightarrow\mathbb{N}^m, g:\mathbb{N}^m\rightarrow\mathbb{N}^k \text{ recursive}\implies g\circ f \text{ ...
1
vote
2answers
47 views

Can't find a theory which meets conditions

I'm trying to solve this problem. There is a language $L = \{f\}$ with equality (we can use '$=$'), where $f$ is a unary function. Our goal is to decide and prove, whether there is a theory $T$, ...
1
vote
2answers
57 views

What is L-implication?

So I'm reading The GUHA Method of Automatic Hypothesis Determination by P. Hajek, and he talks about something called "L-implication". Forgive the stupid question, but what does that mean? I'm not a ...
5
votes
2answers
84 views

Is there a symbol for ‘equal if defined’

Can anybody recommend a symbol for ‘equal if defined’ as an asymmetric concept? In contexts where one might write down notation for an undefined quantity (such as $1/x$ when $x$ might be $0$), ...
0
votes
2answers
46 views

Proving that if $\Gamma \cup \{\gamma\}$ is inconsistent, then $\Gamma\vdash \neg\gamma$.

Definition Let $\gamma\in \text{Form}$. A proof of $\gamma$ is a sequence of formulas $\phi_1,\phi_2,...,\phi_n=\gamma$ where each $\phi_i$ is an instance of an axiom or was obtained by modus ponens ...
0
votes
0answers
20 views

Example CNF for FOL

I don't understand this example: $\forall x [\forall y\ Animal(y)\Rightarrow Loves(x,y)] \Rightarrow [\exists\ y Loves(y,x)] \\$. After, I must eliminate biconditionals and implications. In the ...
3
votes
1answer
103 views

$\sqrt{x}$ is a constant function?

I just "proved" something ridiculous and can't find the fault in my logic. It's probably something really simple and obvious that I'm just overlooking, or maybe not because none of my friends can find ...
7
votes
0answers
111 views

What can the reals of an inner model be?

This is probably a silly question. Call a set of reals $X$ a constructibility ideal (in analogy with a Turing ideal) if $X$ is closed under effective join $r\oplus s: n\mapsto 2^{r(n)}3^{s(n)}$ and ...
0
votes
1answer
52 views

Proof of the deduction theorem explanation

I'm reading through this proof of the deduction theorem, and there are a few things I don't understand. The basic idea is to show that if $\Gamma\cup \{A\}\vdash B$, then we have a proof of $B$ with ...
2
votes
2answers
60 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let ...
26
votes
2answers
2k views

When writing proofs, is logical notation a crutch?

I'm near the end of Velleman's How to Prove It, self-studying and learning a lot about proofs. This book teaches you how to express ideas rigorously in logic notation, prove the theorem logically, and ...
0
votes
2answers
52 views

For all $x$ and some of $y$

Prove that this works for all $x$ and and only some $y$ $$\sqrt{(x-1)^2-(y+2)^2}=0.$$ This is as far as I got so far Difference of squares: $\sqrt{(x-1-y-2)(x-1+y+2)}=0$ ...
0
votes
2answers
47 views

Is it false or it cannot be proven to be true

On a re-reading of D.J.Vellemann's book - "How to prove it" (2nd edition, pg. 69), it reads It should be clear that if $A =\varnothing$, then $\exists x \in A P(x)$ will be false no matter what ...
0
votes
0answers
49 views

Mr.Smith commute word problem. Solved through logic, where is the argument unsound?

Mr. Smith commutes to the city regularly and invariably takes the same train home which arrives at the his home station at 5 pm. At this time, his chauffeur always just arrives, promptly picks him up ...
1
vote
1answer
23 views

How to find a formula that is true for the given model in the First Order Logic?

I think I might get lost in the definitions. I am not sure if this is the right way to deal with models and formulas in the First Order Logic. I am not looking for the solution for this particular ...
1
vote
1answer
33 views

How to draw a triangle on a sphere surface where each angle has 90°?

The problem statement says this: Explain how to draw a triangle, on a sphere surface, where each of its angles 90 degrees. In this right triangle, do the hypotenuse and the sides (adjacent and ...
0
votes
1answer
33 views

Logical translation with possibly one or two premises

I'm trying to translate an argument into sentential logic. It's of the form $$\text{sentence }1:\text{ } p\\\text{sentence }2: \text{ If so, then } q$$ What I want to know is, do I translate this as a ...
0
votes
1answer
19 views

Why these propositional statements are (basically) identical?

I have this two statements: $A$ if and only if $B$. (Not $A$) if and only if (not $B$). One of requests is to determine when these statements are true. Here is what I done: Then, it is also ...
1
vote
1answer
25 views

If a set $S$ is inconsistent, does $S\vdash \alpha$ for all $\alpha$ in this system?

Let $S$ be an inconsistent set of propositional formulas. If our system consists of the axioms: \begin{align} AX1&\quad (P\implies (Q \implies P))\\ AX2&\quad (((P\implies(Q\implies ...
0
votes
1answer
38 views

Completeness of Propositional Logic: Help understanding a proof.

I'm reading through wikipedia's proof of the completeness of propositional logic and I'm having trouble understanding the last parts of the proof: At part III, why is "if $G^*$ contains $C$ and ...
0
votes
1answer
29 views

Proving that a certain function is not recursive

Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where ...
1
vote
1answer
12 views

Exercise of conditional and converse clarification

I have this exercise in logic and discrete mathematics: *It's a common error to confuse the following statements: If $A$, then $B$. If $B$, then $A$. Describe two conditions $A$ and $B$ such as ...
0
votes
2answers
65 views

Is it possible to formalize $T \models \sigma$ within the deductive calculus?

I know that the notion of $T \vdash \sigma$ is formalizable within any sufficiently powerful theory $T$ but is $T \models \sigma$ formalizable as well? How is this possible if there are infinitely ...
3
votes
2answers
80 views

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...
0
votes
1answer
39 views

Counterexample for the reverse implication of Rice's theorem

Here is the version of Rice's theorem I use: Rice's first Theorem: For every non-trivial, language invariant property $P$ of a set of Turing machines it holds that the set $$\{M | P(M) \}$$ is ...
6
votes
1answer
81 views

How can one prove the axiom of collection in ZFC without using the axiom of foundation?

Say I want to prove the axiom(s) of collection from the axiom(s) of replacement. If you have the axiom of foundation, then you can use Scott's trick to do this. But suppose I'm working in a context ...
1
vote
1answer
22 views

On the existence of finite substructures when sufficient chain conditions are met

Let $L$ be a language and $T$ and $L$ theory. Suppose that for any $M\models{T}$, we have $M\subseteq{\bigcup{C_{n}}}$, where each $C_{n}\models{T_{\forall}}$ is finite. I want to show that for some ...
1
vote
1answer
19 views

1-model complete

For $L$ structures $A$ and $B$ we write $A\preceq_{1}B$ if $A\subseteq{B}$ and $A\models{\varphi(a)}$ iff $B\models{\varphi(a)}$ for any finite tuple (of the correct length) $a$ from $A$ and for any ...
0
votes
3answers
36 views

Equivalence between “a iff b” and “(a → b)^(b→a)”

so I have gotten a bit lost on this. "a iff b" suggests to be that "a" can be the case only if "b" is the case so that having "a" be true and "b" be false would be contradictive. From this line of ...
0
votes
1answer
64 views

Proof in Propositional Logic of Peirce's Law

How can I proove in Propositional Logic (using only the basic axioms of P.L. and not a valuation function like it's used in Propositional Calculus) that : $\vdash$ ((($\phi$ $\to$ $\psi$ )$\to$ ...
0
votes
2answers
41 views

A Simple Set Theory Question

If B is a subset of A, then does A imply B or B imply A? Our solution says B implies A, but since B is a subset of A, shouldn't B is included in A, and when A occurs B must occurs? Could someone tell ...
1
vote
2answers
48 views

What does this deduction involving provability imply?

I recently asked this question asking why my reasoning for ZF being inconsistent was wrong. I didn't realize that we have to account for models with non-standard integers. However, I'm left with the ...