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)

3
votes
1answer
61 views

Weakly Compact Cardinals are Mahlo Proof

I have a question about a corollary in Jech's set theory text which states: Corollary 17.19. Every Weakly Compact cardinal $ \kappa $ is a Mahlo cardinal, and the set of Mahlo cardinals below $ ...
2
votes
1answer
47 views

Rewriting ∃! using predicate logic expressions ( “=” excluded)

A(x) is a predicate logic formula. A is a property (predicate), x is a variable. ∃!A(x) would mean that exactly one x exists which has the property A. First thing that comes up is: ∃x( A(x) ∧ ∀y( ...
0
votes
1answer
45 views

Definability in $\Bbb N$ + $\Bbb Z$

Which elements are definable in $\Bbb N$ + $\Bbb Z$? Where an element, a, is definable if there exists a formula such that $\forall x(\phi(x) \rightarrow x = a) $. I have that all elements of $\Bbb ...
1
vote
2answers
45 views

Definability of the $<$ order relation on the natural numbers using addition. [closed]

Show that the usual order relation $<$ on the natural numbers is definable in the structure $(\mathbb{N}, +)$ with only addition. My teacher has clarified this for me and quantifiers can be used. ...
1
vote
1answer
30 views

How to arrange the following sets?

Given the set $\mathcal{P}(\mathbb{N})$ for the following order: For $A,B \in \mathcal{P}(\mathbb{N}) $ applies $A \leq_{set} B \Longleftrightarrow_{def} A = B$ or$ ~$ min$(A\triangle B)\in B$ We ...
1
vote
2answers
40 views

show that ∀ x P ( x ) ∨ ∀ x Q ( x ) is logically equivalent to ∀ x ∀ y ( P ( x ) ∨ Q ( y )) . (Domains for x and y are the same).

My attempt at a solution: Proof that $\forall xP(x)\vee\forall xQ(x)\equiv\forall x\forall y(P(x)\vee Q(y))$: Suppose $\forall xP(x)\vee\forall x Q(x)$ is true. Then $P(x)$ is true for ...
-2
votes
1answer
34 views

Vacation: how many days without rain

A boy talks about his vacation: "There were seven half-days with rain. When it rained in the morning, it was sunny in the afternoon. There were 5 mornings and 6 afternoons without rain. " What was ...
0
votes
2answers
31 views

How does this example agree with a common definition of ${\land}$?

Let ${\lnot}$, ${\in}$ and ${\implies}$ be undefined notions. Then, in the language of set theory, $p{\land}q{\iff}{\lnot}(p{\implies}{\lnot}q)$, where $p$ and $q$ are some WFFs. Let $p$ be ...
2
votes
2answers
46 views

What is $for$ and why isn't it an undefined connective in the language of predicate calculus?

Taking $\lnot$ and $\land$ as undefined notions, I have seen the following definitions $a\lor b\textit{ for }\lnot(\lnot a\land\lnot b)$ $a\implies b\textit{ for }\lnot(a\land\lnot b)$ ...
-1
votes
0answers
26 views

What are good strategies for logic proofs without premises?

I do have a specific one in mind: No premises RTP: (if A then B) or (if B then C) I know I only need to prove half of the disjunct to have a solution to the question, but I can't figure out how to ...
4
votes
3answers
65 views

Undefinability of evenness in first order logic

My question is to show there is no sentence $\psi$ in a language of first order logic without any non-logical symbols such that for every finite structure $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; ...
0
votes
0answers
39 views

Is there a standard notation for coding finite sets of numbers as numbers?

Hajek and Pudlak Metamathematics of First-Order Arithmetic use the Ackermann encoding of hereditarily finite sets, but they use no notation for codes. They let the reader see from context when a ...
0
votes
2answers
34 views

propositional calculus problem, how to prove this right or wrong?

$A$$\rightarrow$$(B$ $\vee$ $C$ ) , $B$ $\rightarrow$ $C$ $\vDash$ $A$ $\rightarrow$ $D$ I think it's wrong but I have no idea how to prove.
4
votes
3answers
1k views

Why can't Axiom of Choice be proven by Rule C

Rule C is appeared in the textbook: Introduction to mathematical logic by Mendelson (Page 81 in the fourth edition). It is said "It is very common in mathematics to reason in the following way. Assume ...
0
votes
1answer
20 views

Partial correctness while loop [closed]

I have some trouble with proving the partial correctness of the following while loop: $\{x=1\}$ while $x>0$ do $x:=x+1$ od $\{x=42\}$ The while loop works against my common sense and I tried to ...
0
votes
0answers
24 views

Integer Logic - The well ordering principle

I've been stumped with understanding the well ordering principle. When presented with a problem such as: $~~~~~~~~~~~~~~n \in\mathbb Z$ (integers), prove that there is no integer $x$ such that $n ...
0
votes
2answers
44 views

Prove this is a tautology with logical equivalence laws only.

$[(p \lor q) \land (\lnot p \lor r)] \to (q \lor r)$ is a tautology I'm not sure how to prove this is a tautology. Tried using $(p \to q)\equiv (\lnot p \lor q)$.
0
votes
0answers
14 views

Satisfiability and Consistency of a Set

Let $S:=\{R\}$ with unary $R$ and let $\Phi := \{\exists xRx\} \cup \{\neg \text{Ry | y is a variable}\}$. Show that: $\text{For no term } t\in T^S, \Phi \vdash Rt$ If $J=(S,\beta)$ is a model of ...
0
votes
1answer
27 views

How to solve ~(P → Q) : P & ~Q by natural deduction?

I'm trying to solve the following by natural deduction: ~(P → Q) : P & ~Q It's a trivial problem if identities are used, as can be seen by the following: {1} 1. ~(P → Q) ...
0
votes
1answer
16 views

$\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$

A set of formulas $\Sigma$ is maximally satisfiable $\iff$ there exists $M$ such that $\Sigma=\{\alpha \mid M\vDash \alpha\}$. I have easily proved that if $\Sigma$ is maximally satisfiable than ...
4
votes
1answer
64 views

Quantification over the set(?) of predicates

When learning set theory and logic, one fact that popped up a handful of times was that we did not quantify over predicates. To quote the notes I took in class on the axiom of unrestricted ...
0
votes
0answers
45 views

Range of a set.

In "Elementary Set Theory" Enderton says talks about the range of an arbitrary set - not necessarily a relation or function - but doesn't go into detail. Anybody know how the range of an arbitrary set ...
1
vote
1answer
33 views

Find $\Gamma$ such that any model of $\Gamma$ has an infinite domain.

As part of a homework assignment for a logic class, I'm supposed to find a finite set $\Gamma$ (I believe of wffs) such that any model of $\Gamma$ has an infinite domain. This is for the predicate ...
2
votes
1answer
34 views

Requirements for Diagonal Lemma

What are the axioms required for a formal system to be able to state the Diagonal Lemma or Fixed Point Theorem? If possible, could you please also relate with the following systems, if it applies to ...
1
vote
1answer
104 views

Loop invariants in logic

I am working on some questions about hoare calculus/logic. The given program $\pi$ is: $ x:=0; y:=1; WHILE \; \lnot x=n \; DO (y:=2y+x + 1; \; x:= x + 1) $ The hoare-logic rules that I can use are ...
4
votes
3answers
78 views

Help with proving a logical equivalence

How do I prove this using logical equivalences? $(p \rightarrow q) \lor (q \land r) \equiv \neg ((p \land \neg r) \land \neg q) \land \neg (r \land (\neg q \land p))$ Any suggestions or tips would ...
1
vote
1answer
31 views

Is this a correct natural deduction proof for $\{(\phi\vee\psi),\neg\phi\}\vdash\psi$?

I'm not sure I used RAA correctly by putting $\neg\psi$ next to $\bot$ and discharging it.
0
votes
1answer
47 views

The game of coins. [duplicate]

Two players play the game: There are two bowls, each of which can be fitted by some number of coins. In the beginning the first player puts in the first bowl some natural number of coins of his ...
0
votes
2answers
56 views

What's with this definition of ${\land}$?

Let ${\implies}$ and ${\lnot}$ be primitives. Let $p$ and $q$ be WFFs. I've seen a formal definition of $p{\land}q$ as ${\lnot}(p{\implies}{\lnot}q)$. How does this comply with the understanding ...
3
votes
1answer
58 views

If $x$ is even and $y$ is odd, then $x+y$ is even.

I was also asked to proof if I say the above statement is true and give a counter example if I say it is False. Moreover, I prefer the statement to be false because the sum of any even and odd number ...
0
votes
1answer
21 views

Why do people say RAA(Reductio Ad Absurdum) is the same as $(\bot E)$?

$(\bot E)$ is $\bot\vdash\psi$. RAA(Reductio Ad Absurdum) says If $\{\Gamma,\neg\psi\}\vdash\bot$, then $\{\Gamma\}\vdash\psi$. Yet, one of the solutions to my textbook exercises uses ...
1
vote
1answer
19 views

Rewrite “x > a” in Iverson brackets as Heaviside function

Let's say I have a Heaviside function defined like this: $$ H(x) = \begin{cases} 0, \text{ if } x < 0\\ 1, \text{ if } x \geq 0 \end{cases} $$ Then I have a so called Iverson brackets: $$ ...
0
votes
1answer
33 views

P if and only if Q means, (P then q) AND (q then p)

I was asked to state that the claim is true or false, I must give a prove to say it is true and counter example if it is false. However I say it is True;This is a bi-conditional statement which mean ...
1
vote
1answer
32 views

translating uniqueness quantifier algorithmically

Given a claim with a uniqueness quantifier $\exists$!, such as: $$\forall x \exists!y \ P(x,y) $$ A standard translation that uses $\forall$ and $\exists$ only (there are several possible ones) is: ...
0
votes
0answers
22 views

Prove by induction that $\Gamma \vdash \varphi \Rightarrow \Gamma[x/c] \vdash \varphi[x/c]$.

As the title says: I want to prove by induction that $\Gamma \vdash \varphi \Rightarrow \Gamma[x/c] \vdash \varphi[x/c]$. I’m struggling with how to write this proof. I think I need to do induction ...
1
vote
1answer
21 views

Showing that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements.

As the title says, I’m trying to show that $\lambda_n \vdash \sigma \Leftrightarrow \sigma$ holds in all models with at least $n$ elements. It’s from Logic and Structure, van Dalen (2013 edition). ...
0
votes
1answer
42 views

Use natural deduction to prove an easy logical statement

How to prove $(A \rightarrow ( B\vee C) ) \rightarrow ((A \rightarrow B) \vee(A \rightarrow C))$ when $\vee$ means or, using natural deduction? It is easy to prove the converse , but I didn't ...
1
vote
1answer
43 views

Truth table and induction

It is true that every truth table can be represented by some wff built using only the connectives $\neg, \implies$ and $\iff$ - let's call it "negation-arrow-wff" for convenience. I want to be able to ...
0
votes
1answer
26 views

Why isn't the contrapositive of the E proposition always valid?

If I have, for example, a statement: "No dog is a whale" I can take the obverse and say: "All dogs are not whales" And turn this into an implication: "If it is a dog, then it is not a whale" And ...
0
votes
2answers
91 views

Is there a difference between $x=0$ and $0=x$

Is there a difference between $x=2$ and $2=x$ One of my students asked this question . What would be a good answer for this ? Here $x$ is unknown. After calculating we get $x=2$
0
votes
1answer
38 views

The textbook's natural deduction proof for $\vdash(\neg(\phi\to\psi)\to\phi)$ seems to be wrong with regard to RAA(Reductio Ad Absurdum).

As you can see below, $\psi$ pops out of nowhere due to RAA(reductio ad absurdum). This is probably wrong. Is there really a proper natural deduction proof for $\vdash(\neg(\phi\to\psi)\to\phi)$? ...
4
votes
2answers
70 views

Non existence of Prime models

Let $L$ be a countable language. Let $T$ be a complete $L$ theory. We know that if $T$ is small, then there is a prime model of the theory. But $\text{Th}(\mathbb{N},+,\times,0,1)$ is not small but it ...
0
votes
0answers
13 views

Show that if X implies Y is valid, then X is unsatisfiable or Y is valid

How can I show that if X and Y are two formulas with no propositional variables in common, and (X ⇒ Y) is valid, then either X is unsatisfiable or Y is valid (or both). I know that (X ⇒ Y) is false ...
0
votes
0answers
33 views

Every Logical Expression is either a Tautology or Contradiction

The question ask if the above claim is True or False. if true I Must prove that and give a counter example if it is false. I prefer the claim to be false. since looking at every logical expression ...
0
votes
1answer
26 views

Showing a relation is primitive recursive, recursive, or semirecursive.

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive. The diagonal of ...
0
votes
2answers
18 views

Building a truth table for the following expression, confused on comma's within the expression.

{A $\rightarrow$ B, (C $\rightarrow$ A $\lor$ B), C} $\models$ B I'm confused on the commas and what their meaning is here. In my truth table, am I to OR them all together?
1
vote
1answer
32 views

Does False Entail True, and Vice Versa?

I have these two statements: False $\models$ True Reads as : False logicially entails True if all models that evaluate False to True also evaluate True to True. True $\models$ False Reads as : ...
2
votes
3answers
58 views

About definition of model

In Model theory, the definition of a model is a set. Can it be a proper class? ZFC has a model and maybe some models is a proper class. Definition of a model needs to include a proper class. Is it ...
0
votes
0answers
84 views

Gödel's incompleteness theorem applys to ZFC theory

When I assume ZFC's consistency, it is impossible to prove ZFC's consistency in itself from Gödel's incompleteness theorem 2. If ZFC's consistency have done, its proof need to be done in stronger ...
2
votes
0answers
82 views

How can I understand about ZFC and Gödel's Completeness theorem [closed]

English 1 ZFC could be formulated as First order logic. 2 Gödel's Completeness theorem is a theorem within ZFC. 3 I think a lot of books about set theory is implicitly assuming Gödel's ...