1
vote
2answers
54 views

Construct the truth table?

Any body help me .. How to solve this? (i) $(p\land q)\to (p \leftrightarrow (q \lor r))$ (ii) $(p \leftrightarrow q) \leftrightarrow ((p\land q) \lor (\neg q \land \neg p))$ (iii) ...
0
votes
1answer
26 views

Proving ∀x (0|x ↔ x = 0) (divisor by Zero) - Euclidean Algorithm

I am trying to proof the total correction of Euclidean Algorithm, so I am up to proof one of the following properties which is divisor by Zero. Given this Axiom: ...
0
votes
0answers
32 views

The unique model of cardinal $\kappa$ of a $\kappa$-categorical countable theory is saturated.

Let $T$ be a $\kappa$-categorical ($\kappa \geq \aleph_1$) first-order theory in a countable language $\mathcal L$. I try to prove that its unique (up to isomorphism) model of cardinal $\kappa$ is ...
2
votes
1answer
97 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
2
votes
2answers
72 views

Prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction

I am trying to prove P∧(Q∨R)→(P∧Q)∨(P∧R) from P∧(Q∨R) using Natural Deduction. Here is my attempt using JAPE application. ...
3
votes
2answers
102 views
0
votes
0answers
63 views

A is recursive iff A is the range of an increasing function which is recursive

Working a problem stated in Enderton, but stated better and apparently stronger in Soare. All citations hereon are for Soare (1987). Would appreciate help on the proof. I know there has to be a more ...
1
vote
4answers
85 views

If $(a-1),a,(a+1)$ are consecutive positive integers, $ (a+1)^3 \neq a^3 + (a-1)^3$

I had to prove the following statement: If $(a-1),a,(a+1)$ are consecutive positive integers, $(a+1)^3 \neq a^3 + (a-1)^3$ My attempt at the solution was to first expand each side to get $$a^3 ...
5
votes
3answers
163 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
1
vote
1answer
62 views

Problem from Cutland's Computability: 3.2. problem 3

The problem goes as follows. Let f: N --> N, such that f is partial, N is the natural numbers, and let m $\in$ N. Construct a non-computable function g such that g(x) = f(x) for x$\le$m. Proof: By ...
1
vote
1answer
61 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 ...
1
vote
2answers
135 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
99 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
1answer
73 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 ...
1
vote
5answers
55 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 ...
1
vote
6answers
80 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 ...
3
votes
1answer
59 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
2answers
95 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 ...
6
votes
1answer
179 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. ...
2
votes
3answers
57 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
1answer
115 views

Contradiction proof of the product of two irrational numbers

I am wondering what is wrong with my contradiction proof that "The product of two irrational numbers is irrational". I understand that there are examples where this is not true: $\sqrt{2} * ...
3
votes
3answers
73 views

Disproving $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$

Let $A,B,C$ be any sets. Tell if $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$ is true or false. I tried to prove by absurd. Suppose $A \subset B \wedge B ...
0
votes
1answer
60 views

Is there a rule to justify the following logical statement?

I have to derive the following expression and reach the second one: $$\begin{gather} ( ( \forall x , Q \Rightarrow \neg P (x) ) \wedge ( \forall x, \neg Q \Rightarrow \neg P(x) ) ) \\ \iff \\ ( ...
0
votes
0answers
34 views

Disproving a proof about the explosion principle for sets of sentences

Imagine that someone were to try to prove that every sentence is a consequence of an inconsistent set of sentences in the following way. Suppose that Γ is inconsistent. Then for some ϕ ∈ S, ϕ & −ϕ ...
1
vote
1answer
75 views

Correctly representing a $2^n < n!$ statement

$$2^n < n!$$ After an inductive proof I determined that $2^n < n!$ is valid only for values greater than or equal to $4$. So. How do I represent this conclusion? Is this correct? $$\forall n ...
2
votes
1answer
77 views

Generalized distributive laws proof feedback

I'm currently learning proofs and elementary set theory. I would like to have feedback on my proof since I'm self-studying. Are some part superfluous or unclear? My proof goes as follows: I will ...
5
votes
3answers
118 views

Can Peirce's Law be proven without contradiction?

Good evening, I heard the proof by contradiction is required for Peirce's law. AFAIK, truth tables are not related directly to proofs by contradiction, and if of an operation $\text {op}$ we have a ...
0
votes
2answers
194 views

A (too?) simple argument for the undefinability of definable sets

Preliminaries (see e.g. Jech, Set Theory, p. 5): To every formula $\varphi(x)$ of ZF set theory corresponds a class $C = \lbrace x : \varphi(x)\rbrace$, but only to some formulas corresponds a set. ...
2
votes
0answers
123 views

Non-Constructive Proofs

I have just started to read more about constructivism and its critique towards classical logic. As I was reading, I came across a passage about non-constructive results, that mentioned the following ...
2
votes
1answer
50 views

Proof via equivalence laws; $(a \lor b) \equiv (b \lor a)$?

Is this a correct progression to prove that $p \rightarrow (q \rightarrow r) \equiv q \rightarrow (p \rightarrow r)$? $$\begin{align} p \rightarrow (q \rightarrow r) & \equiv p \rightarrow (q ...
2
votes
1answer
37 views

Proof using logic consequence. Is this correct?

Try to proof this using the definition of logic consequence. $\forall x(\alpha \rightarrow \beta), \forall x \alpha \models \forall x \beta$ Let's say that: $\Gamma = \alpha \rightarrow \beta$, by ...
3
votes
1answer
91 views

Proof with quantifiers

$(\forall x)(\exists y)(x+y=0)$ $x$ and $y$ are real numbers The statement reads: for all $x$ there exists some $y$ such that $x+y=0$ is true. My proof is: take $y=-x$ Is this valid? I'm just ...
1
vote
1answer
58 views

Injectivity and Imdepotency implies Surjectivity

This question stem from Natural Deduction (FeedBack). The reason why I think it is justifiable to open this up as a separate question is that I am now considering other measures to show it, possibly ...
0
votes
3answers
133 views

Natural Deduction (FeedBack)

I am looking for feedback to three proofs (alternatively derivations) that I have constructed. The first is: Theorem. Injectivity does not imply surjectivity. Proof: Suppose $\{\phi\} \vdash ...
6
votes
2answers
140 views

Olympiad inequality: is this reasoning sound?

I am trying to show that for $a,b,c>0,\;abc=1:$ $$\underbrace{\frac{1}{b(a+b)}+\frac{1}{c(b+c)}+\frac{1}{a(c+a)}}_{X}\geq \frac{3}{2}$$ This problem is from the Zhautykov Olympiad of 2008. ...