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
3answers
32 views

A = {x/x^2+1 : x belongs to reals } Show that A is a subset of [-1/2, 1/2]

I am really stuck with this assignment and have very little idea on how to proceed. I think using derivative is not allowed. How should I proceed, could anyone give any tips? I've thought something ...
1
vote
1answer
209 views

Proving the symmetry of an equivalence relation

When proving the symmetry of an equivalence relation, must each equivalence class be closed under symmetry. for example: the relation both x and y > 10 or both x and y < 10 across all ...
4
votes
1answer
75 views

Prove using inference rules

I'm having trouble proving this using inference rules... $(A\to (B\to C)\to (B\to (\sim C\to\, \sim A ))$ Perhaps, I should start with $A\to (\sim B\lor C)$?? Help!
1
vote
1answer
59 views

Simple proof about XOR, (possibly a duplicate question)

Prove Whether this statement is True or False: Other than solving by Truth Table If $A \oplus b = A \oplus C$ then $A=C$ I saw this question online and I've been thinking about it for days now ...
4
votes
1answer
73 views

Is ordinal analysis a non-recursive project?

A recursive ordinal is an ordinal that is the order-type for some recursive relation (i.e. a recursive well-ordering). We can represent recursive ordinals as natural numbers using Kleene's $O$, an ...
2
votes
1answer
77 views

For the Compactness Theorem for Propositional Logic, show that the extension is not unique.

During the proof of the compactness theorem, from an arbitrary finitely satisfiable set $\Sigma$ of WFFs, we construct a finitely satisfiable set $\Delta\supseteq \sigma$ such that for every WFF ...
2
votes
1answer
291 views

Proof of the distributive law in implication

I am doing a practice exam and in it is the following question: Show without truth tables that the following logical equivalence holds: $$(p → q) ∧ (p → r) ≡ p → (q ∧ r)$$ I attempted to substitute ...
2
votes
2answers
114 views

Proving a Logic Equation

I have two information. $x+y = 1$ and $xy = 0$. Now,I need to prove this equation : $xz + x'y + yz = y + z$ What I tried: $z(x+y) + x'y = z + x'y$ Thats all What do you think?
8
votes
2answers
180 views

Set theory based on inclusion

There are several axiomatizations of set theory based on inclusion rather than membership. I found only two papers, but they are both in German, and I could not read them even using a disctionary. Can ...
-1
votes
1answer
57 views

I am having trouble negating quantified statements [closed]

I need help with my home work. Translate each of the following into a quantified statement in standard form, write its symbolic negation, and then state its negation in words. a. You can't teach an ...
5
votes
3answers
186 views

Foundations of Forcing

I am currently studying Forcing methods in order to understand some independence results and model's constructions. Now I am interested on formalizing the main notions around forcing such as ...
0
votes
1answer
76 views

Understanding truth values for logic w/ quantifiers

a) Determine the truth value of the statement $∃y∀x¬V(x,y)$ where $V(x,y) = x+y=2xy$ b) Determine the truth value of the statement $∃yV(1,y)$ where $V(x,y) = x+y=2xy$ My process for figuring out a) ...
1
vote
1answer
43 views

Predicates and quantifiers

Let $L(x,y)$ be the statement "x lives with y", where the domain for both x and y is all people. How would I describe the below using the above statement? Nobody lives with y becomes $¬∃xL(x,y)$ if ...
3
votes
1answer
113 views

Proving $A \wedge B \implies A$ in propositional calculus.

Consider the formal axiomatic theory, whose axioms are $$(B \implies (A \implies B))$$ $$((B \implies (A \implies C)) \implies ((B \implies A) \implies (B \implies C)))$$ $$(((\neg A \implies (\neg ...
2
votes
2answers
104 views

Rules of inference proofs

I have the following: Premise: {$p \lor q, q\rightarrow r,p \land s \rightarrow t, \lnot r, \lnot q \rightarrow u \land s$}, conclusion: $t$ I'm having a real hard understanding how to prove the ...
0
votes
1answer
152 views

Showing the every consistent set of sentences has a model

I want to do a short proof showing that every consistent set of sentences has a model. I am assuming the derivability version of completeness for first-order logic, in for form: $$\Sigma \models F ...
8
votes
1answer
187 views

Can we found mathematics without evaluation or membership?

In some sense, composition generalizes evaluation. The trick is, instead of writing $f(x)$ for $x$ an element of the domain of $X,$ we write $f \circ x$ for $x$ a function $1 \rightarrow X$. ...
1
vote
3answers
123 views

Converting statements with quantifiers

I'm having a little trouble understanding quantifiers and therefore doubting all my study answers. Since there is no where to check if the answers are correct, I'm very very worried I am just ...
5
votes
3answers
496 views

Is “The present King of France is bald” studied by maths?

Intuitively, "The present King of France is bald." is false. But Bertrand Russell said it would mean that "The present King of France is not bald.", which seems to be false. This apparently leads to ...
0
votes
1answer
224 views

Negation of double logic quantifiers

$$\forall a\forall b\ (a^{2}+4b-2=0)$$ How exactly would this be negated? would the $(a^{2}+4b-2 = 0)$ be negated twice (and as such remain the same? For example: $$\neg (\forall a\forall b\ ...
2
votes
2answers
573 views

What is the statement “If not p then q” called?

Let's say I have a statement: if p then q. The converse would be: if q then p. The inverse would be: if not p then not q. The contraposition would be: if not q then not p. What would you call the ...
1
vote
2answers
83 views

What is the purpose of implication in this scenario?

Consider the case: Let: S(x) = “x is a student” F(x) = “x is a faculty member” A(x, y) = “x has asked y a question” Dx and Dy = Consists of all people associated with your school. Use ...
0
votes
1answer
522 views

Definition about “infinitely often”

As we know, "$A_n \text{ i.o.}$" means $A_n$ happens infinitely often, where $A_n$ is an event. I'm not sure whether "the complement of $A_n$ happens for large $n$" is the complement of the preceding ...
0
votes
2answers
74 views

Proof: ((A or B) and (A or ~C) and (~B or ~C)) <=> ((A or B) and (~B or ~C))

How to prove the following using logical connectivities laws? ((A or B) and (A or ~C) and (~B or ~C)) <=> ((A or B) and (~B or ~C))
0
votes
2answers
49 views

Are these statements in logic form correct?

Let M represent the set of all Mathematics courses and S represent the set of all students. Predicates: ...
0
votes
2answers
341 views

What is the purpose of implication in discrete mathematics?

I would be obliged if you can show me an example of a truth table for implication where there is a also a real life aspect to it. (i.e., where would someone use the scenario to make F->F = T and also ...
3
votes
2answers
89 views

How can I quantify over the class of all cardinalities?

I'd like to quantify over all cardinalities of sets. My end goal is to make a category-theoretic arguement: For all cardinalities of sets, in the category of sets with maps as morphisms: the ...
5
votes
1answer
144 views

What is the proof-theoretic ordinal of the first-order theory of real closed fields?

I recently asked a question on MathOverflow, concerning a predicative second-order theory of real numbers. Now the standard way of developing predicativity in the case of second-order arithmetic is ...
1
vote
2answers
94 views

Tautological implication

Determine whether or not $((P\land Q)\implies R)$ tautologically implies $((P\implies R)\lor (Q\implies R))$ How do I determine that $((P\land Q)\implies R)$ tautologically implies $((P\implies ...
1
vote
2answers
136 views

Prove that this infinite planar map can still be colored with four colors.

Here is quite challenging problem from Enderton's popular textbook A Mathematical Introduction to Logic. In 1977 it was proved that every planar map can be colored with four colors. Of course, the ...
0
votes
1answer
30 views

How can I prove that: of A and ( not A or B) is equivalent to A and B

How can I prove that: A and ( not A or B) is equivalent to A and B It is easy to show with a truth table how can I do only using the properties of the logical ...
4
votes
2answers
97 views

Logic Mathematic Question

“This might interest you, master Yoda and master Obi-Wan,” said Anakin. “My age and the ages of each my three children are prime numbers, and the sum of our ages is 50.” “In that case,” said ...
1
vote
2answers
57 views

State Ned Conjecture using logic notation

How can the following conjecture be expressed using logic notation: "Every sufficiently large integer is an integer that can be expressed as the sum of five primes, with no prime appearing more than ...
4
votes
1answer
144 views

Describe a sound and complete proof system

I have a homework assignment that I am a little stumped on, the questions is: Describe a sound and complete proof system (axioms and proof rules) for proposition logic. Explain in detail why you ...
6
votes
3answers
298 views

Does a proof by contradiction always exist?

Good day, Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For ...
4
votes
3answers
195 views

How can one quantify on a function in ZFC?

I have read that $ZFC$ and first-order logic could formalize all the mathematics, but I do not manage to conceive that. First, let me show what my understanding of $ZFC$ is. I have read that $ZFC$ was ...
1
vote
1answer
685 views

How to convert this first order sentence into conjunctive normal form?

This is one of my homework, but it seems to be so complicated that I really do not know where to start :( $$ \exists x\;\forall y\;\forall z \Bigl({\rm person}(x)\land \bigl(({\rm likes}(x,y)\land ...
0
votes
1answer
121 views

Homework, how to use resolution to prove these inferences are valid?

I am kind of a layman in this area, and now I have to prove these: $P\rightarrow Q,\neg Q\vdash\neg P$ $P\rightarrow Q\vdash\neg Q\rightarrow\neg P$ $P\rightarrow Q, Q\rightarrow R\vdash ...
0
votes
1answer
78 views

Proving Formula Equivalence using Equivalence Laws

I'm taking Discrete Math for CS, and we went over Equivalence Laws the other day. Prove equivalence of f and g for: $f(x,y) = \lnot ((x \land \lnot y) \lor (x \land y))$ Test Case 1: $f(F,F) = ...
1
vote
1answer
40 views

X and Y are sets of sentences. If X is a subset of Y then Model(Y) is a subset of Model (X)

How do we show that for any sets sentences X and Y, and any sentences a and b, if X is a subset of Y then Model(Y) is a subset of Model (X)? Also, how to show that X union {a} is a tautological ...
1
vote
1answer
74 views

How many distinct functions for a set containing four elements? [closed]

How many distinct unary and binary functions can be defined on a set containing four elements? Edit: How many distinct unary and binary operations can be defined on a set containing four elements?
3
votes
3answers
159 views

$(∀x)(∃y)(x>y)$ is false. But then why is $ (∀x)(∃y)(x\geq y)$ true?

Given the Universe is the set of natural numbers, then $(∀x)(∃y)(x>y)$ is false. But then why is $(∀x)(∃y)(x\geq y)$ true? The first equation and the second equation is the same except for "=" in ...
1
vote
1answer
69 views

What is the logical interpretation of this set?

$\{f \in C : f(x)>d$ for each $x$ for some $d\}$ Do you read the above set as "the set of functions in $C$ such that there exists $d$ such that for each $x, f(x)>d$" or do you read the $d$ as ...
2
votes
2answers
121 views

Why is $\forall x \in A:P(x)$ equivalent to $\forall x (x\in A \to P(x)) $? [duplicate]

In the book that I'm studying from it defines $\forall x \in A: P(x)$ equivalent to $\forall x (x\in A \to P(x))$ without any explanation as to why it is that way. The same thing for the existential ...
1
vote
1answer
54 views

To validate the $ \exists x [E(x) \land C(x)]$

Show the validity of (1) $\forall x [M(x) \implies C(x)]$ (2) $\exists x[M(x) \land H(x)]$ (3) $\forall x [E(x) \implies H(x)]$ so, (4) $ \exists x [E(x) \land C(x)]$ ...
2
votes
1answer
44 views

Mathematical logic - alternative of conjuncion AND

I want to know if the word "also" do the same thing like "AND"? For example, there's a statement like this: All the students who are good at Maths also work hard. ...
1
vote
1answer
39 views

Proof for a stubborn nonstandard model

This a theory in the book Computational Complexity by Christos Papadimitriou, on Page 111, as a corollary of Godel's Completeness Theorem. It asserts: Corollary 3: If $\Delta$ is a is a set of ...
2
votes
2answers
121 views

The use of any as opposed to every.

This is a really basic question, but it is one I never really thought about until now. Let $\mathscr{G}$ be a tree. Then every pair of vertices in $\mathscr{G}$ is connected by a unique walk. We ...
1
vote
2answers
93 views

Proof $(P \land S) \rightarrow \lnot q$ in hilbert system

How can I proof $(P \land S) \rightarrow \lnot q$ using this principles : $p \rightarrow (q \lor r) $ $q \rightarrow \lnot r $ $r \leftrightarrow s $ in Hilbert system and modus ponens?
4
votes
1answer
137 views

Determining the truth value of certain quantifiers based on this proposition being false.

Can you help me verify if I answered this question correctly? Consider $[(\forall x)(P(x)) \land (\exists x)(\lnot Q(x))] \implies \{(\forall x)(P(x)) \iff [\lnot(\forall x)(R(x)) \lor ...