Questions about 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
32 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
183 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
41 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
54 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 ...
0
votes
1answer
56 views

Consistency result vs. True in every model of Axiom X

Suppose a forcing extension of ZFC has been found which satisfies statement $A$. For example, say the extension is formed by Cohen or Laver forcing, so that the model satisfies $\neg$CH. At this ...
0
votes
2answers
55 views

Is this predicate expressing compactness?

I don't quite know why definitions of "compact" use the expression "arbitrary collection". Am I correct in thinking that the following predicate is a definition of compact? Let $X$ by a set with ...
0
votes
2answers
131 views

Help with really confusing venn diagram

So this is by far the most confusing venn diagram problem i've ever done. Can someone help me out? I know that Real numbers contain rational, and rational contain integers, but i get really confused ...
8
votes
3answers
976 views

Are all mathematical statements true or false?

I would like to know whether it can be possible for a statement to be neither true nor false. Consider the age old paradox. "This statement is not true" Clearly it cannot be true. If it is false. ...
0
votes
2answers
578 views

Using proof of equivalence

I just wanted to make sure whether I was on the right track or not with this. Let $r\in\mathbb{R}_{\ne0}$. Use a proof of equivalence to show the following: $$r\in\mathbb{Q} \iff ...
4
votes
2answers
352 views

Determining which pairs of quantified statements are equivalent

Sometimes, but not always, quantifiers distribute over logical operations. Determine which of the following pairs of statements are equivalent. In the case of nonequivalent pairs, give an example of ...
1
vote
6answers
430 views

Determine if tautology, contingency or contradiction

I have to determine if the statement is a tautology, contradiction or contingency. Been at it for days but didn't get too far. The original question is $$\left((\lnot p\vee z)\wedge(p\vee ...
2
votes
3answers
106 views

How to reduce predicate logic into propositional logic?

I read that predicate logic reduces into propositional logic. However, I couldn't find anything online that explains the process. Do you know where I could find an explanation? Thank you.
1
vote
3answers
58 views

Understanding the union operation

Suppose we have: $A = \{(x,v,w):x+v=w\}$ $B = \{(x,v):x=v\}$ $C = \{(w,u):\exists x 2x=w\}$ Can we say that $C = A \cup B$?
0
votes
1answer
150 views

How can a statement be known to be undecidable in ZFC without ZFC being inconsistent?

I'm attempting to understand the answer to the question, Is there a statement whose undecidability is undecidable (as in independent, not a decision problem)? The answer appears to be "Yes". However, ...
2
votes
3answers
78 views

Satisfiability Proof Question

Exercise: Prove that $\Gamma\models A$ iff $\Gamma\cup\{\neg A\}$ is not satisfiable. Proof: We must prove two clauses: $\Gamma\models A\Rightarrow \Gamma\cup\{\neg A\}$ is not satisfiable ...
2
votes
1answer
78 views

Question from Marker's book T3 has three models up to isomorphism

This question is from Marker's book. Let $ \mathcal L_3 = \left\{ {< ,c_0,c_1, \dots}\right\} $ where $c_0,c_1, \dots$ are constants symbols. Let $T_3$ be the theory of dense linear orders ...
0
votes
3answers
47 views

Simplify this Logic Function?

Have a Hardware Lab to do, and I need to reduce the following function before I actually hook it up to the Logic Trainer. (not ac) + (abc) + (a not c) Or: $\lnot (a \land c) \lor (a \land b ...
0
votes
4answers
84 views

$\lnot \exists x (\forall y (\alpha)\land \forall z(\beta) )\;$ is logically equivalent to which one of these?

These are the options: $\forall x(\exists z(\lnot \beta)\rightarrow \forall y(\alpha))$ $\forall x(\forall z(\beta)\to \exists y(\lnot\alpha))$ $\forall x(\forall y(\alpha)\to \exists z(\lnot ...
10
votes
5answers
6k views

Help: rules of a game whose details I don't remember!

In a probability course, a game was introduced which a logical approach won't yield a strategy for winning, but a probabilistic one will. My problem is that I don't remember the details (the rules of ...
1
vote
2answers
96 views

A question about consistent fragments of formalized mathematical theories with Natural Deduction

In Dag Prawitz, Natural Deduction A Proof-Theoretical Study (1965), we have the system I of intuitionistic (first-order) logic based on eleven introduction- and elimination-rules : the 3 couples for ...
0
votes
4answers
222 views

Get rid of an existential quantifier

I have to remove the existential quantifier from the following formula: $$\exists i\left[\left(i \geq 0\right) \land \left(z-2i = 0\right) \land \left(y+i=x\right)\right]$$ First I make some simple ...
3
votes
2answers
458 views

How to prove consistency of Natural Deduction systems

In Dag Prawitz, Natural Deduction A Proof-Theoretical Study (1965), we have the system I of intuitionistic (first-order) logic based on eleven introduction- and elimination-rules : the 3 couples for ...
2
votes
1answer
1k views

When do we use entailment vs implication?

I have seen both used and I have been unable to find by searching. They seem to have a similar meaning from what I have seen, however I have only seen entailment in relation to models.
1
vote
1answer
87 views

Show that $((p \rightarrow q) \vee (p \rightarrow r))$ and $p \rightarrow (q \wedge r)$ are logically equivalent.

Show that $((p \rightarrow q) \vee (p \rightarrow r))$ and $p \rightarrow (q \wedge r)$ are logically equivalent. I am wondering if my professor put the wrong symbol on our review guide because I ...
1
vote
1answer
154 views

Simplification of a Boolean Expression

I want to simplify this expression: ACD' + E(A+C)(A'+D') + A'C . The result must be a product of sums, where every sum should be consisted of just two variables. For example (A+B)(C+A)(Z+Y) ... ...
0
votes
2answers
238 views

Discrete Mathematics - Show that a conditional statement is a tautology.

I am trying to show that the conditional statement: $$[\mathord{\sim}p \land(p\lor q)] \to q$$ is a tautology without using truth tables. Could someone help me understand how to do this?
1
vote
1answer
29 views

Logical meaning to morphisms between prehilbertian spaces

I was wondering how one can give a logical meaning to morphisms between prehilbertian spaces. If I was to consider such a morphism $f$ as a logical morphism between two $L$-structures, I should have ...
9
votes
0answers
146 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
0
votes
2answers
41 views

Intro to Discrete Structures $\;\lnot A \rightarrow (A \rightarrow B)$

Im trying to use propositional logic to break this down but i have no clue. i know about the rule that if a wff ends in form ....implies (a implies b), the a can be ...
0
votes
2answers
53 views

simplify the boolean expression

I'm fairly new too boolean algebra. I've tried simplifying this equation but I'm not quite sure if I've done it correctly. Simplify to 1 literal, (X + Y + Y'Z)(Y + X)(Y + X') My attempt: ...
1
vote
2answers
177 views

Prove $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$

Let $A$ and $B$ be subsets of some universal set. Prove that $(A \backslash B)'\backslash (B \backslash A) = B \backslash A$ Given: Definition 3.3.1 states that $A$ and $B$ are sets. The complement ...
-1
votes
4answers
433 views

Prove $A \subseteq B \cap C$ if and only if $A \subseteq B$ and $A \subseteq C$

Prove the following for any sets $A,B$ and $C$. This is actually two sets that I'm trying the prove. The title character restriction wouldn't allow me to post both at the same time. a. $A \subseteq ...
6
votes
1answer
248 views

Problem 24 from Chapter 1 of Kunen's Set Theory: An Introduction to Independence Proofs

Just want to make sure I'm tracking Kunen here, and hopefully the proof I have is correct. Comments / Suggestions welcome. Thanks! Problem 24. Let T be any consistent set of axioms extending ZF. ...
4
votes
1answer
80 views

What is $\forall x P(x)$ equivalent to using the $\exists$ quantifer?

It is just $\neg \exists x \neg P(x)$? Which says there is no $x$ which makes $P(x)$ false?
3
votes
1answer
40 views

Given the graph of a relation R on a set of real numbers, how can you visually determine if R has the reflexive, anti/symmetric properties?

Answers: a. It must contain all points on the line $y=x$ where $x$ is in the domain of the relation. From a point on the graph, move vertically to the line $y = x$ and that point must be on the ...
2
votes
1answer
55 views

Let $T$ be a theory of Abelian groups where every element has order 2 find complete theory include T

This question is from Marker's book . Let $T$ be a theory of Abelian groups where every element has order 2 . Show that it is not complete . Find $T' \supset T $ a complete theory with the same ...
-2
votes
1answer
123 views

Using the methods of conditional proofs - logic

use method of conditional proof to show the statement is a tautology. check my solution please
1
vote
1answer
28 views

Help in writing contraposition

Help in writing contraposition for this statement
0
votes
1answer
49 views

Are these sets recursive, r.e. or none

Are the sets a) $\{x | \exists y \phi_x(y) = 0\}$ b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$ recursive, recursively enumerable (r.e.) or none of them? Please explain your solution. $\phi_x$ ...
1
vote
2answers
906 views

Exercise regarding boolean algebra?

We need to simplify $AC+A'B'C$ $Y=A'B' +A'B C'+(A+C')'$ For (1) I wrote $C(A+A'B')$ but the result must be $AC+ B'C$. How do I get that to happen? I tried to simplify (2) using deMorgan but no ...
2
votes
2answers
649 views

How to prove the validity of this argument using rules of inference?

The premises are: (P $\rightarrow$ J) $\rightarrow$ ($\lnot$C $\rightarrow$ M) $\lnot$J $\rightarrow$ $\space$ $\lnot$P ($\lnot$ J $\land$ E) $\rightarrow$ $\space$ $\lnot$C $\lnot$M $\rightarrow$ ...
3
votes
3answers
68 views

Show $\lnot(p\land q) \equiv \lnot p \lor\lnot q$

Show $\lnot(p\land q) \equiv \lnot p \lor \lnot q$ this is my solution . Check it please
0
votes
3answers
207 views

Can a premise imply contradictory statements?

Can a premise imply contradictory statements? Can two contradictory premises imply the same conclusion? Determine the answers to these questions by doing the following. Prove or disprove: the ...
0
votes
2answers
59 views

contrapositive of the following logical statement

What is the contrapositive of the following statement: $p|ab $ and $p|a$ or $p|b$ then $p$ is prime. number theory problem
2
votes
4answers
98 views

Mixing and Distributing Qualifiers ($\forall x$, $\exists x$)

Context I'm having trouble understanding the limited situations in which qualifiers can be distributed. I am given that the rules are: $$\forall x\left[P(x)\land Q(x)\right]\equiv\forall xP(x) ...
-4
votes
1answer
46 views

P($(A \lor B) \land C) \iff P((A \land C) \lor (B \land C))$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \land C) ...
0
votes
2answers
66 views

$(A \lor B) \land C \iff (A \lor C) \land (B \lor C)$?

Assume $A$, $B$, and $C$ are three independent predicates. Maybe $A$ stands for "my age is 20," and $B$ "stands for tomorrow is a good day." So is it true that $(A \lor B) \land C \iff (A \lor C) ...
0
votes
1answer
31 views

Using the resolution method in logic

Using the resolution method in logic, having these clauses $$\{ \neg M \vee S, \neg S \vee T, \neg W \vee T, W \vee M, \neg T, \neg T \vee S \}$$ is it possible to reach the contradiction directly ...
0
votes
1answer
89 views

Are the structure of logical expression based on formative constructions like sequences or trees ?

Recently, I get confused when reading the book Principles of Mathematical Logic written by D. Hilbert. How to define the term 'logical expression'? I just envisage that it might be defined as anyone ...
1
vote
2answers
88 views

A question regarding the meaning of propositional connectives in “natural deduction” and “tableaux method”

In Marcello D'Agostino & Dov Gabbay (editors), Handbook of Tableau Methods (1998) I've found in Ch.2 : Tableau Methods for Classical Propositional Logic, by Marcello D'Agostino, an interesting ...