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
1answer
19 views

Simple Question on Quantifier Logic [closed]

is this a valid implication: $(\forall\epsilon>0.\exists x\in A.x>a-\epsilon)\implies(\forall\beta\epsilon>0.\exists \beta x\in \beta A.\beta x>\beta a-\beta\epsilon) $ $,\beta>0$
2
votes
3answers
47 views

Propositional calculus algebra

Can somebody explain me the following equivalence in propositional algebra(by the use of the laws of algebra): $$\lnot(p \lor q) \lor (\lnot p \land q) \equiv \lnot p$$ I get stuck after $$\lnot(p ...
0
votes
1answer
34 views

Is it correct that If $\mathcal {A } $ is a model of $\Gamma $, and if $\Gamma \models {\psi}$ then $\mathcal {A } \models \psi $?

I'm not certain that I have understood the definiton of $\models $ correctly. I this statement correct? If $\mathcal {A } $ is a model of $\Gamma $, and if $\Gamma \models {\psi}$ then $\mathcal {A } ...
0
votes
1answer
34 views

Prove the following $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ [duplicate]

How can I prove the following statements are equivalent using laws of set theory? $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ Using De Morgans laws to simplify the ...
1
vote
1answer
50 views

How to prove that $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$

How can I prove the following statements are equivalent using laws of set theory? $\neg((A\cap B)\cup (\neg A \cap C)) = (A\cap\neg B)\cup (\neg A\cap \neg C)$ I managed to use De Morgans laws to ...
0
votes
2answers
56 views

How to prove the following expression

Prove that if it takes you 5 minutes to solve any Sudoku puzzle and 14 minutes to solve a word search, you can completely occupy yourself on any flight of 52 minutes or longer provided that you have a ...
2
votes
1answer
95 views

Why are these logical statements not deemed to be equivalent?

I'm working through a book on my own which has just introduced the ideas of $A \Rightarrow B, B \Leftarrow A$ and $A \Leftrightarrow B$. It then gave 20 exercise questions to answer. I've correctly ...
1
vote
2answers
32 views

Negation of a statement

So I am trying to prove a proposition. It goes like this Let there be $\emptyset\neq X\subset\mathbb{R}$ which is bounded from above. The next two statements are equivalent about $s\in\mathbb{R} $ ...
1
vote
0answers
27 views

How do I know that min-term can't be combined any further?

I'm trying to learn (and implement) Quine-McCluskey algorithm for boolean function minimalisation. I'm learning the algorithm from wikipedia example. From that I understood the following: Take all ...
0
votes
3answers
34 views

Proving $x^2 < y^2$ by means of the Ordering Axioms [closed]

How do I prove $x^2 < y^2$, if $0 \le x < y$ with the ordering axioms? thanks!
3
votes
1answer
54 views

Propositional Logic: Conditions for a sequence to be an element of $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
0
votes
1answer
51 views

Analyzing logical form of ∀x∀yM(x, y)

I have been going through Velleman's How to prove book and in one of their sample problems they have used ∀x∀yM(x, y) for ...
0
votes
1answer
40 views

show that inverses $\pi_{1},\pi_{2}$ are recursive?

show that one can define inverses $\pi_{1},\pi_{2}$ for $ \langle.,.\rangle$ with$\pi_{1}(\langle m,n \rangle)=m,\pi_{2}(\langle m,n \rangle)=n\ \ \forall n,m$ wich are also recursive?
2
votes
2answers
62 views

Biconditional Introduction in natural deduction

I'm working on a first-order logic question and I'm a little stuck as to what I should be assuming in my first subproof (this is always my problem). I'm supposed to prove this biconditional argument ...
1
vote
1answer
67 views

The fundamental axioms of mathematics

Having known about what axioms are, I want to know whether there are some "fundamental axioms of mathematics" on which every branch of mathematics depends. If yes, what are they ? Or Do we have ...
1
vote
2answers
47 views

Can this be further simplified?

I had to analyse the logical form of some statements, one of them is this: $P \cup (Q \cap R) \subset A \cup(B \setminus C)$ which I analysed with these expressions: $\exists x (x \in ( P \lor (Q ...
-1
votes
2answers
60 views

Prove that $(A \cup B)−(A \cap B) = (A− B) \cup (B − A)$

Prove that $$(A \cup B)−(A \cap B) = (A− B) \cup (B − A)$$ by showing that the left hand side is the subset of the right hand side and vice versa. Progress Let $x$ be an element of LHS. Then x is ...
1
vote
1answer
71 views

Find a universe for variables x, y, and z for which the statement is true and another universe in which it is false.

Find a universe for variables $x, y$, and $z$ for which the statement $∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$ is true and another universe in which it is false. Is there a more ...
1
vote
2answers
66 views

Propositional Logic: For which natural numbers $n$ are there elements of $\mathcal{L_0}$ of length $n$?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
0
votes
1answer
39 views

Propositional Logic: 15-symbol (or more) elements of $\mathcal{L_0}$, sentences.

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
0
votes
1answer
26 views

Analysing the logical form of a statement where there's an $`if`$

One of the statements in the exercise is: If someone who knows to love and is loved by someone, then he feels the sun from both sides. that I did not know exactly how to translate, especially ...
1
vote
1answer
67 views

Use predicates and quantifiers to express this statement.

“Some students in this class grew up in the same town as exactly one other student in this class." I'm thinking there is a relation T(x,y) where the student x grew up the same town as student y. And ...
2
votes
1answer
28 views

Formula involving only $\neg$ and $\rightarrow$

I have to find a formula equivalent to $A \leftrightarrow B$ using just $\neg$ and $\rightarrow$ symbols. This is what I have tried, but from the truth table that I made, it seems not to be correct.. ...
0
votes
1answer
31 views

Demonstration of equivalence

I have this assignment: Show the following (DO NOT USE TRUTH TABLES, Truth tables are not allowed): Of course, I have checked the equivalence between the ...
0
votes
2answers
65 views

Proof of $(A \cap B) \cup (B \cap C) \cup (C \cap A) = (A \cup B) \cap (B \cup C) \cap (C \cup A)$

Prove that $(A \cap B) \cup (B \cap C) \cup (C \cap A) = (A \cup B) \cap (B \cup C) \cap (C \cup A)$ I have noted $\mathcal{A} = x \in A$, $\mathcal{B} = x \in B$, $\mathcal{C} = x \in C$ So in ...
3
votes
4answers
72 views

How to negate an implication in English?

How to negate this proposition: "If $xy$ is irrational then either $x$ is irrational or $y$ is irrational. " Because the negation of $p\Rightarrow q$ is $p \wedge \text{not } q$. If I translate this ...
1
vote
0answers
54 views

How to make a large cardinal unique?

A general form of questions regarding large cardinals is the following: Let $A(x)$ be the formula asserting "$x$ is a large cardinal of type $A$" then is the following true? ...
1
vote
1answer
49 views

Confusion in set-theory: Definition of formulas needs set

I am confused about some definitions in logic/ axiomatic set theory: We stated in our logic lecture the ZFC axioms and called the members of a ZFC-model "sets". But to define formulas and structures, ...
0
votes
1answer
67 views

What is the difference between logical and iterative set

Saphiro in his "foundations without foundationalism: a case for second-order logic" defends second-order logic by claiming that talking about subsets of domain is not problematic in case of SOL. He ...
0
votes
2answers
69 views

Proof by Contradiction? [closed]

How does one construct the proof by contradiction? I know Direct Proof and Proof by Contrapositive really well but just can't understand proof by contradiction.
0
votes
0answers
30 views

What's the correct logical conclusion after proving a value holds?

I had to prove that for every set $s$, the number of subsets with odd cardinalities is $2^{n-1}$. I concluded that this formula holds everytime $|s| \geq 1$ and then I used an inductive process to ...
4
votes
3answers
63 views

Seeking help to understand a simple Kripke model

I'm reading A Brief Introduction to the Intuitionistic Propositional Calculus, at page 7, there is a simple Kripke model represented by a graph, I interpret it as: $W = \{w_1, w_2\}$ $w_1 \ge w_2$ ...
2
votes
1answer
27 views

Help with the negation of a complicated(and poorly written, in my opinion) definition of almost periodic function

I am being asked to write the negation of the following statement: For every $\varepsilon > 0$ there is $T > 0$ such that for every $x \in \mathbb R$ there exists $y$ such that $x < y < x ...
1
vote
1answer
26 views

For integer $n$ prove that if there is no integer $m\le \sqrt{n}$ such that $ m | n$, then $n$ is prime.

At first I thought that the best way to prove this statement is to take the direct approach and show the subset {1, 2, 3,...sqrt(n)} and the subset {sqrt(n),... n/3, ..., n/2,...,n} and show that ...
1
vote
4answers
133 views

Logical problem in analysis

I'm holding a logical problem in real analysis. Let R with the usual metric be the metric space in consideration. Define a function $f : A \to R$ where $A \subseteq R$ and let p be a limit ...
0
votes
1answer
47 views

Logic question in Real Analysis

I thought about posting some minor insecurities and some main doubts i have on a particular topic. Let R with the usual metric be a metric space, $A \subseteq R$ , $f:A\to R$ and p is a limit ...
1
vote
1answer
33 views

Converting to clausal form for using Resolution on formulas with free variables

The resolution rule in first order logic is used with FOL sentences (formulas without free variables). Is it possible to do Resolution on general FOL formulas? If so, how does the conversion to ...
0
votes
1answer
40 views

Propositional Logic model

In propositional logic, "model" is defined as mathematical abstractions that fix the truth or falsehood of every relevant sentence? How is relevance defined in this case?
-2
votes
2answers
93 views

Best Mathematical Logic Books the Style of Which is Like a Mathematics Publication rather than a Logic Publication?

I found many good mathematical logic books are written like a publication in the field of Logic. For instance, in such books I would see such as "For every $x$, if $x$ is a real number then $x^{2} ...
0
votes
2answers
55 views

Is $\forall x [\exists y\ Q(x,y)\ \lor\ \forall z\ \neg Q(x,z)]$ valid?

Is $\forall x [\exists y\ Q(x,y)\ \lor\ \forall z\ \neg Q(x,z)]$ valid or merely a satisfiable formula? I would appreciate an explanation as to why, because it seems a bit counter-intuitive to me.
0
votes
1answer
16 views

How to express the number of subjects in a proposition by using predicates?

Let F(x,y) be the statement "x can fool y," where the domain consists of all people in the world. ...
1
vote
1answer
34 views

Is there a Fitch style system that works with some of the modal logics?

My prof taught us to use trees to prove modal logic arguments. Trees seem to provide a more efficient way to test arguments than Fitch does. However, I find that trees generally, and alethic (modal) ...
0
votes
2answers
72 views

Proofs in Propositional Calculus

$X \simeq Y$ reads as $X$ is equivalent to $Y$ If $X \simeq Y$, iff $X \leftrightarrow Y$ is a tautology. Now given $X_1 \simeq X_2$, how do I prove, $\tilde X_1 \simeq \tilde X_2$ $X_1 \cap ...
2
votes
3answers
90 views

natural deduction proof

Need help with the steps for natural deduction: P1. $(A \rightarrow B) \rightarrow (C \rightarrow A)$ P2. $A \wedge (C \leftrightarrow B)$ P3. $(A \lor C) \to (A \to B)$ ...
0
votes
3answers
61 views

Demonstration with Or elimination

I'm trying prove this statement $$(P \wedge Q) \vee (P \wedge R) \vdash P \wedge (Q \vee R)$$ And then : $$\frac{\frac{(P \wedge Q) \vee (P\wedge R) \,\,\,\,\,\,\,\,\,\,\,\,\frac{P \wedge ...
4
votes
1answer
91 views

When are extensional equivalence classes still sets?

Let $\sim$ denote extensional equivalence. That is, $y\sim x \Leftrightarrow \forall z(z\in y \leftrightarrow z\in x)$. Given a set $x$, let $[[x]] := \lbrace y:y\sim x\rbrace$. Clearly, ...
3
votes
1answer
93 views

Undefinable Real Numbers

Disclamer: I'm sure my definition of "definable" may be different than the/a established mathematical one, I am more than interested in learning why/how this is so, but that is not my question Part ...
0
votes
2answers
47 views

Give a formal derivation of ∃x~P(y) given the premises ~∃x(∀yP(y) ∧ Q(x)) and Q(b)

This is one of the question I was given for homework, and I'm not sure how to do it, I'm not even really sure how to start. I missed some classes, and I've been trying to figure it out for a couple ...
0
votes
1answer
13 views

Relation symmetric and antisymmetric

Let $A$ a non-empty set. If there is a complete relation on $A$ that is both symmetric and antisymmetric, does it imply that the relation is the "equality" and $A$ has one single element?
1
vote
3answers
57 views

Can I use Gödel numbering to prove a set is countable?

We're studying the basics of set theory (introducing ZFC, defining countability, etc.) and in one of my homework questions I am asked to prove that given a finite set of symbols $a_1, a_2, \cdots, ...