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
2answers
116 views

Restate a logical claim using logical symbols

Proposition: Strictly between any two distinct rational numbers lies another rational number. How may I present this statement using logical symbols? My answer: $\forall x, y \in {\mathbb{Q}}. ...
0
votes
2answers
99 views

Curry-Howard isomorphism for disjunction elimination

I am trying to find out how the disjunction elimination rule of natural deduction relates to the Curry-Howard isomorphism. The rule: $P \vee Q, P \Rightarrow C, Q \Rightarrow C \vdash C$ I have been ...
0
votes
1answer
42 views

NAND Logic Function Help

I have a 4 input logic function (ABCD) that I have to construct on a logic trainer using ONLY NAND and Inverter Gates. We were originally given the following function: ...
1
vote
1answer
52 views

Hasse graph of a poset.

Let $S = \{a, b, c, d, e, f\}$. The graph of a poset $(S,\lesssim)$ looks like this: Except vertices of the graph in my textbook are represented by letters. The letters correspond to the numbers in ...
1
vote
5answers
287 views

$(A_1\rightarrow\wedge A_2)$ is not a well-formed formula

Let $A_1,A_2$ be sentence symbols. Could anyone advise me how to prove $(A_1\rightarrow\wedge A_2)$ is not a well-formed formula? Thank you.
0
votes
1answer
70 views

Getting auxiliary assumptions from a conclusion

In the book I'm reading they say they want to deduce $(p \rightarrow q) \rightarrow (p \rightarrow r)$ from $p \rightarrow (q \rightarrow r)$. Now, as far as I understood, $p \rightarrow (q ...
2
votes
2answers
135 views

Circuit Logic NAND

I have to build a circuit using only NAND gates. But I wasn't given an equation. Instead I was given this formula: F(wxyz)= E m(0,1,2,3,4,5,7,14,15) Function of (wxyz) = Sum m(0,1,2,3,4,5,7,14,15) ...
1
vote
1answer
68 views

how do I convert AND to NAND using logic?

I could convert OR to NAND, but I am stuck on AND. I can convert AND to interms of XOR, but still find no way to convert it to NAND
3
votes
2answers
60 views

The “disjunction” of two theories

I have three first-order theories $A,B,C$ at hand such that every model of $A$ either satisfies $B$ or satisfies $C$ (or both). Presumably, none of these theories is finitely axiomatizable. I ...
4
votes
2answers
168 views

Is Paraconsistent Negation Really Negation?

Let a logic be paraconsistent, if $\phi \wedge \neg \phi \not \models \psi$ for some $\phi, \psi$ (where $\models$ is the logic's consequence relation). There are different ways to prevent a ...
16
votes
3answers
721 views

Mathematical Notation and its importance

You can see how mathematical notation evolved during the last centuries here. I think everyone here knows that a bad notation can change an otherwise elementar problem into a difficult problem. Just ...
1
vote
2answers
92 views

How is this disjunctive form found through propositional algebra

I'm learning about disjunctive normal form and the algebra of propositions. The text is Discrete Mathematics with Graph Theory, 3rd Edition by Goodaire and Parmenter (it wasn't highly recommended on ...
1
vote
0answers
59 views

Use equational proofs to solve the problem

Use equational proof to solve the problem. $ \vdash A \lor (B \rightarrow A) \equiv B \rightarrow A $ These are the axioms and theorems.
2
votes
1answer
95 views

Use equational proofs to solve problems (Logic)

Use equational proofs to solve the problem: $ \vdash A \lor B \equiv A \lor \lnot B \equiv A $ These are the Axioms and the theorems :
0
votes
2answers
98 views

How do I break down this derivation further?

I'm trying to prove the following is a tautology by using logical derivation and without the use of truth tables: $$((P \vee Q) \wedge (P \vee (\neg Q))) \to P.$$ So far I got: $$(\neg ((P \vee Q) ...
1
vote
3answers
213 views

Using quantifiers to express this sentence.

These are from a study guide, just checking my work. Let $F(x,y)$ be the statement "$x$ and $y$ are friends." where the domains consists of all people in the class. Use quantifiers to express the ...
1
vote
1answer
98 views

Exercise 17.6 of Sacks' Saturated Model Theory

I'd like to know whether my proof is correct. Exercise goes as follows. 17.6. Let $T$ be a model completion of some $\forall$-theory. Show there exists $T^* = T$ s.t. every member of $T^*$ is of the ...
2
votes
4answers
1k views

Recommendation on a rigorous and deep introductory logic textbook

In this post, I don't mean any word by its somewhat "mathematical or logical" meaning but just "literally". It's been three years since I started "formal" mathematics, and now I'm familiar with set ...
18
votes
3answers
2k views

Polynomial map is surjective if it is injective

A friend of mine told me the following fact: If $k$ is any algebraically closed field, then a polynomial map $f\colon k^n\to k^n$ of affine space $k^n$ is surjective if it is injective. The ...
0
votes
1answer
66 views

On Counted Languages

In my recent question on Godel Completeness I mentioned that there was a related question I wanted to ask, but would keep separate. I have been recently studying "non-well ordered sets" and Chapter 7 ...
3
votes
6answers
1k views

$(P\implies Q) \implies [(R ∨ P)\implies (R ∨ Q)]$ is a tautology

I'm currently trying to work on the proof for this tautology. But every time I derive the right side, I end up with a lone $R$ that will never cancel out. Like I always end up with $$(P\implies Q) ...
1
vote
1answer
213 views

Use Hilbert style proofs to solve problem

Solve this problem by using Hilbert style proof: $ A,B \vdash A \equiv B $ my try : (1) A (hyp) (2) B (hyp) (3) $ A \land B $ (merge) (4) $ A \land B \equiv A \equiv B \equiv A \lor B $ (golden ...
11
votes
2answers
642 views

Constructiveness of Proof of Gödel's Completeness Theorem

As a mathematician interested in novel applications I am trying to gain a deeper understanding of (the non-constructiveness of) Gödel's Completeness Theorem and have recently studying two texts: ...
5
votes
1answer
56 views

Transforming Nested Fixed-Point Formulas into Infinitary Logic Formulas with Finitely many Variables

There is a definition (actually a description of how it could be defined) of a fixed-point logic formula. The formula is in inflationary fixed point logic (IFP) in this case but it could also be ...
0
votes
2answers
409 views

Prove $A+(B+C) = (A+B) +C$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the following statement: f.$A+(B+C) = (A+B) +C$ We need to ...
7
votes
2answers
224 views

A truth definition, wrong, but where

Consider the theory ZFC of language with connectives $\neg$, $\rightarrow$, predicative symbol $\in$ and quantifier $\forall$. Assume that we are working in ZFC. Let $\mathcal{V}$ be the class of ...
4
votes
1answer
171 views

How to derive this equivalence in propositional logic

This is a homework assignment from a discrete math class that I never took - it asks how to prove the statement $\neg \neg p \equiv p$. The catch is that only the following equivalences can be used: ...
0
votes
1answer
66 views

Can the sheffer stroke do the work normally done with sets?

It seems to me that the sufficiency-necessity relation is effectively the same as the set-member relation. Using a concrete examples to make the point: A rain drop ⊃ a bit of water A rain drop → ...
2
votes
2answers
120 views

Natural Deduction rules for $\lnot$ in classical and intuitionstic logic

Following the very useful answer by Peter Smith to my prevoius post , I'm still reflecting about the "imperfection" connected with the Intro- ans Elim-rules for $\lnot$ in Natural Deduction (I mean ...
0
votes
3answers
587 views

Prove $A + (B+C) =B+(A+C) = C+ (A+B)$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the following statement $A + (B+C) = B+(A+C) = C+ (A+B)$ ...
1
vote
1answer
53 views

Logical Proposition simplification

I'm Trying to simplify this: $$ [(¬p \vee ¬q)\to¬(r \vee s)] \wedge ¬s \wedge r$$ so far, I got into this: $$ [(p \wedge q) \vee (¬r \wedge ¬s)] \wedge r \wedge ¬s$$
1
vote
2answers
509 views

Prove $A+B= A \cup B$ if and only if $A \cap B = \emptyset$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove $A+B= A \cup B$ if and only if $A \cap B = \emptyset$. My ...
2
votes
1answer
211 views

Prove $A+ \emptyset = A, A+A = \emptyset$, and $A +A' = U$ using the definition of $A+B$

I need to know if I'm on the right track on this Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the ...
1
vote
3answers
48 views

Can you see if i made a mistake in my check for tautology?

I need to prove that the following is a tautology: [(P -> Q) ∧ ¬ Q ] -> ¬P so my solution was: ...
1
vote
3answers
1k views

How to write there exists exactly 1 x in a domain with property p without the unique quantifier? [duplicate]

I need to write the statement 'there exists exactly one x in a domain such that p(x) is true'. This needs to be done without using the uniqueness quantifier $\exists!$. I've been staring at this ...
1
vote
1answer
134 views

Exercise 16.7 from Sacks' Saturated Model Theory

Question / exercise goes as follows: $M'$ is said to be finitely generated if there exists a finite $|X|\subset |M'|$ such that $M'$ is the least substructure of $M'$ whose universe $|M'|$ contains ...
2
votes
2answers
58 views

On provability within minimal logic

In its most naive form my question boils down to this: when is a proposition that is provable "by contradiction" also provable "directly"? IOW, is it possible to know, a priori, that a ...
2
votes
1answer
43 views

Can every order-preserving function $\mathbb{B}^n \rightarrow \mathbb{B}$ be represented using only {AND, OR, TRUE, FALSE}?

Write $\mathbb{B} = \{0,1\}$ for the Boolean domain. Then those functions $\mathbb{B}^n \rightarrow \mathbb{B}$ representable by an expression in the language of bounded distributive lattices are ...
0
votes
3answers
517 views

Using rules of inference (Leibniz) to prove theorems.

Leibniz: If $A \equiv B$ is a theorem, then so is $C[p:= A] \equiv C[p:= B]$. Note: p is "fresh" means p doesn't occur in $A, B, C$. I am trying to understand how to use Leibniz rule of inference for ...
1
vote
2answers
102 views

How to compare Peano numbers?

How do you compare Peano numbers? I thought about something like this, but it does not seem to be correct: $bigger(s(0),0)$ $bigger(x,y) \to bigger(s(x), s(y))$ Then I thought about using a ...
1
vote
1answer
56 views

Boolean equation simplification

This is the problem: XY’ + XYZ + XY'Z= X + Y'Z And so far I have this, XY’ + XYZ + XY'Z= X + Y'Z X(Y’ + YZ + Y’Z) Factor out X X(Y’ + Z + Y’Z) De Morgan Any tips on how to proceed? I know ...
2
votes
0answers
161 views

Semantic Proof of Tarski's Undefinability of Arithmetic Truth

A few years ago I took a logic course and I've since lost my notes. I seem to remember a very semantic proof of Tarski's theorem on the undefinability of arithmetic truth, one that didn't use the ...
6
votes
4answers
641 views

What is the “correct” reading of $\bot$?

I have some doubts about the "natural" interpretation of $\bot$ in Natural Deduction and sequent calculus. In Prawitz (1965) $\bot$ (falsehood or absurdity) is called a sentential constant [page 14] ...
2
votes
5answers
164 views

Prove that $A \ne B$ is equivalent to the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$

Prove that $A \ne B$ is equivalent to the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$. Given: P: $A \ne B$ is equivalent Q: the logical ...
0
votes
6answers
125 views

Prove the following statement: If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set.

If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set. Edit: Thanks for the \emptyset Latex command. Given: P: $E$ is an empty set and $A \subseteq E$ Q: $A$ is an empty set. We ...
2
votes
1answer
221 views

Prove the following statement: If A is any set, then $A \subseteq A$

I'm doing some practice problems and I'm wondering if I got this right. I think this is a very short proof, but I'm not sure. Given: P: A is any set Q: $A \subseteq A$ We have a $P \rightarrow Q$ ...
0
votes
1answer
33 views

nested quantifiers clarification

If I let $F(x, y)$ be "$x$ can see $y$" be the correct syntax for "Everyone can see John" equate to $$\forall x(\exists \mbox{John} \enspace F(x,\mbox{John}))$$ and/or $$\forall x(\exists y \enspace ...
1
vote
6answers
198 views

Logic - Is $A \rightarrow ( B \rightarrow C) $ equivalent to $A \rightarrow C$?

I know that $A \rightarrow B$ and $B \rightarrow C$ resolves to $A \rightarrow C$ but does $A \rightarrow (B \rightarrow C)$ also resolve to $A \rightarrow C$?
2
votes
1answer
42 views

Maximum size of a set containing logical expressions

Can you please help me with this problem? "What is the maximum size of a set A of logical expressions that only use →, p, q : each pair of elements of A are not equivalent?" I've found 6 different ...
0
votes
1answer
74 views

Negate Implication Written as a Sentence without “If …, Then …” [Chartrand P246]

P246 Theorem 10.4: Every infinite subset of a denumerable set is denumerable. P252 Theorem 10.10: Let $A \subseteq B$ be sets. If $A$ is uncountable, then $B$ is uncountable. I'm aware how ...