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)

1
vote
2answers
23 views

Question about the solution to Unexpected hanging paradox

The following is the unexpected hanging paradox: A judge tells a condemned prisoner that he will be hanged at noon on one weekday in the following week but that the execution will be a surprise to ...
0
votes
0answers
40 views

Two statements R and S are logically equivalent R $\iff$ S is a tautology.

How do prove the following statement: "Two statements R and S are logically equivalent R↔S is a tautology. without using a true table.Would I have to use cases? So far I have done so far is that I ...
2
votes
0answers
13 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
1
vote
2answers
33 views

What's the meaning of an element that belongs to the same element?

In classical set theory, if I consider that $x$ is an element, which means it is not a set, can I write $x \in x$ ? If yes, what this would mean? Correct me if I am wrong, but I don't need to have ...
1
vote
0answers
23 views

The pencils in a box of crayons always have the same color [duplicate]

I retrieved an old math book and I'm delighted to share following exercise. The pencils in a box of crayons always have the same color. Proof by induction on the number $n$ of pencils in the ...
7
votes
2answers
43 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
0
votes
3answers
33 views

How to convert a truth table to boolean expression?

If I have a huge truth table, it's hard for me to construct an expression. I know a problematic method, the Disjunctive Normal Form. But I found that I cannot reduce the huge expression. ...
2
votes
3answers
109 views

Negation of a logical statement

My question is that when I negate the statement $$(\forall x\in \mathbb{R})( \exists n \in \mathbb{N})(x < 1/n),$$ do I negate all of the statement or just the first part $(\forall x \in ...
-4
votes
0answers
22 views

word problem based on the highest common factor [on hold]

Three pieces of timber 42 metres,49 metres and 63 metres long,have to be divided into planks of the same length.What is the greatest possible length of each plank?
1
vote
2answers
33 views

How to show that $[(p \rightarrow q) \rightarrow r] \Rightarrow [p \rightarrow (q \rightarrow r)]$

To show that $[(p \rightarrow q) \rightarrow r] \Rightarrow [p \rightarrow (q \rightarrow r)]$ without using a truth table. That is, using logical laws.
1
vote
3answers
60 views

How to prove a logical implication?

Question: Using the Laws of Logic and Rules of Inference, prove that $$(\neg(\neg p \lor q) \lor r) \Rightarrow (\neg p \lor (\neg q \lor r)).$$ I just don't know how to apply the Rules of ...
7
votes
4answers
121 views

mathematical proof vs. first-order logic deductions

For a long time I thought that the standard mathematical proofs, only were an informal or imperfect way of writing the proof in the language of first-order logic. When I say standard mathematical ...
5
votes
4answers
227 views

Is there a possibility that ZFC is inconsistent and, if it is, do we have to throw out our old proofs? [duplicate]

I have learned that ZFC has not been proven consistent, and that further more if one were to start from ZFC and prove ZFC consistent, this would imply that ZFC is not consistent, due to Gödel. A few ...
0
votes
0answers
13 views

Cyclical counting quantifiers

In counting logic, how does one assign a meaning to statements such as "There exists $x$ $y$'s such that there exist $y$ $x$'s such that $x>y$. My mind hurts as I try to imagine how to evaluate ...
-3
votes
0answers
26 views

What are the truth tables for the following logical statements? [on hold]

NOT ($P$ and $Q$) (NOT $P$) or (NOT $Q$) $P$ and (NOT $Q$) (NOT $P$) or $Q$ Also: Is the statement "Some girl is not good at math" the negation of the statement "All girls are good at math?"
2
votes
0answers
20 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
0
votes
1answer
27 views

N-bit-String contains of zeros and one “1” bit [on hold]

Design a circuit contains of only basic logical gates (2 bit gates such as AND, OR, XOR, NAND and NOT gate) and constants: Input: n bit string A[0:n-1] Output: two bits: Y=1 only if all bits are 0 ...
1
vote
2answers
68 views

How to negate: not a limit point (symbolic logic)

1.There are few I have seen here. $\forall N(x), \exists x'\in B, (x'\neq x\wedge x'\in E)$. $\forall N(x), \exists x'\in B, (x'\neq x\to x\not\in E)$. $\forall r>0, \exists x'\in N_r(x)\cap E, ...
0
votes
1answer
29 views

most natural formulation of the $\vee$-eliminating rule

There are several (equivalent) ways to formulate the eliminating rule of $\vee$ ("or") Here are two of them: $\begin{array}{c} A\vee B \quad A\vdash C \quad B\vdash C\\ \hline C \end{array}$ ...
1
vote
1answer
33 views

$\kappa$-categoricity in the language of identity

I have the following exercise from Dirk Van Dalen's Logic and Structure: Here with language of identity we mean the language with no extralogical symbols (i.e. no symbols of predicates, functions ...
2
votes
1answer
61 views

Number of non-isomorphic models

Let $C$ be the class of cardinals. Define by recursion $C_0 = C$, $C_\alpha = C_\beta\cup P(C_\beta)$ if $\alpha=\beta+1$ and $C_\alpha = \bigcup_{\beta<\alpha}{C_\beta}$ for limit $\alpha$ (Here ...
1
vote
2answers
20 views

Is there a difference between these statements about natural numbers?

Can i say that $(\forall x \in \mathbb{N}:x^2=x) \vee(\forall x \in \mathbb{N}:x>1)$ is the same statement as:$\forall x \in \mathbb{N}:(x^2=x)\vee(x>1)$ ? If not, why? Thanks.
0
votes
0answers
53 views

proof with 3 quantifiers? [on hold]

Problems: $$∃x ∈ S \text{ s.t. } ∀y ∈ S, ∀z ∈ S, \text{ if } z > y, \text{ then } z ≥ x + y.$$ $$∀x ∈ S, ∃y ∈ S \text{ s.t. } ∀z ∈ S, \text{ if } z > y, \text{ then } z ≥ x + y.$$ What I have ...
4
votes
1answer
100 views

Is Alfred Tarski's Introduction to Logic still helpful for self study?

I am trying to setup a self study path to enhance my knowledge of mathematical logic. I haven't taken a logic course for a few years and my confidence on mathematical proofs is unnerving. I am ...
1
vote
2answers
37 views

Logically Equivalance - Proofs

In terms of logical statements, is ($\exists$n $\in$ N)($\forall$ x $\in$ A)(nx >= 1) equal to ($\forall$x $\in$ A)($\exists$ n $\in$ N)(nx >= 1)? Also consider the following statements $\forall x ...
2
votes
2answers
51 views

Logical Statements - Proofs

Let $f$ be a real-valued function (a function with target space the set of reals). Let $P(x, M)$ stand for $|f(x)| \leq M $, let $N$ be the set of positive real numbers, and let $\mathbb{R}$ be the ...
0
votes
1answer
24 views

Eliminating rule of existential quantifier

Why is the rule $\begin{array}{c} \exists x(\varphi(x))\quad \forall x (\varphi(x)\rightarrow A)\\ \hline A \end{array}$ valid? Why does this rule hold? How can one verify this rule intuitively?
3
votes
2answers
52 views

Intuitionistic Proof of $(a \Rightarrow b) \Rightarrow (\lnot b \Rightarrow \lnot a)$

I'm trying to prove $$(a \Rightarrow b) \Rightarrow (\lnot b \Rightarrow \lnot a)$$ A seemingly natural way to start is by assuming the left side, as well as assuming a. This ends up proving what I ...
2
votes
1answer
31 views

Axiomatizability of the algebra of (a fragment of) calculus

Consider the set $S$ of all infinitely-differentiable functions on the reals. Consider the structure $(S,+,-,*,0,1,Id,D)$, where $+$,$-$, and $*$ are function addition, subtraction and multiplication ...
3
votes
3answers
87 views

Explaining the meaning of equality

I've been tasked with explaining to a group of people what the notion of equality means in mathematics, I've come up with a working explanation, but would appreciate some input, suggestions etc. ...
0
votes
1answer
61 views

Can the solvability of a single Diophantine equation be undecidable (in any sense of the word)?

Apologies in advance for asking the following "philosophical" question, which falls dramatically short of any reasonable standards of mathematical rigour: Is it possible that there should exist a ...
6
votes
1answer
130 views

What proof uses both the Riemann Hypothesis and its negation?

Some time ago I happened to see a proof that was remarkable in that it used both the Riemann Hypothesis and its negation. That is, it considered the two cases: RH is true, and RH is false, obtaining, ...
4
votes
4answers
85 views

Is it possible to assign probability to a set $X$ with $|X|>2^{\aleph_0}$?

Is it possible to assign probability to a set $X$ with cardinality $|X| > 2^{\aleph_0}$? Example would be a set $|X| = 2^{2^{\aleph_0}}$.
1
vote
1answer
55 views

What are the meanings of the various turnstiles

It is easy to find the meanings of $\vdash$ and $\models$ (see this question and Wikipedia) but what of the (triple?) turnstile $\Vvdash$ and the (vertical double?) turnstile $\Vdash$? Do they have a ...
2
votes
4answers
79 views

Non-standard model of $Th(\mathbb{R})$ with the same cardinality of $\mathbb{R}$

Let $\mathfrak{R}= ⟨\mathbb{R},<,+,-,\cdot,0,1⟩$ be the standard model of $Th(\mathbb{R})$ in the language of ordered fields. I need to show that there exists a (non standard) model of ...
-1
votes
0answers
22 views

Logical consequence and resolution rule

Which of this are false? a) If some formula H results from premises D, then H could be derived from D with using (reapetedly) resolution rule. b) If some formula H results from premises D, then we ...
0
votes
1answer
16 views

Replacing a fractional quantity by one in inequalities

I was looking through proofs for the product law for limits and I stumbled upon a very clear one and managed to follow all the steps involving algebra and limits, but, near the end, in the proof, a ...
0
votes
1answer
39 views

Can you write down a chain of derivabilities?

Suppose you have a sentence $A$, from which you can derive $B$, from which you can derive $C$. What is the best way to write this down? I would like to write $$ A \vdash B \vdash C, $$ but I'm not ...
1
vote
2answers
20 views

Convert form form CNF to DNF

i have few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can i convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can i convert this to CNF $(p \wedge q) \vee ...
-1
votes
1answer
53 views

Does $\mathcal{P}(\mathbb{N})$ contain infinite sets?

I know that $\mathcal{P}(\mathbb{N})$ is infinite and uncountable. However, is the power set of the natural numbers considered to contain only finite sets of natural numbers, or infinite ones as well? ...
0
votes
2answers
49 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
8
votes
2answers
146 views

Why do we know that Gödel sentences are true in the standard model of set theory, but do not know if the continuum hypothesis is?

By what methods can we identify sentences that are true in the standard model of set theory, but not in other models? In particular, how do we prove that Gödel sentences are true in the standard ...
2
votes
1answer
69 views

A math puzzle about slow clock

You have the misfortune to own an unreliable clock. This one loses exactly 20 minutes every hour. It is now showing 4:00am and you know that is was correct at midnight, when you set it. The clock ...
0
votes
2answers
46 views

If $P$ is true then not $Q$

I'm trying to solve the following problem: "If this sentence is true then tomorrow will not rain". tomorrow will rain tomorrow will not rain the sentence is a paradox What I thought is: $P ...
-2
votes
2answers
42 views

Problem on elementary logic and set theory

Let A and B be sets with B is a subset of A. Prove that A \ (A\B)=B. I start by saying that suppose x is in A \ (A\B). By definition, x is in A and X is not in (A\B) . However, x is not in A\B ...
-5
votes
0answers
21 views

how can we make 20 using onlynand only two 3s and we can use any mathematical function as and when required [closed]

how can we make 20 using onlynand only two 3s and we can use any mathematical function as and when required
0
votes
3answers
38 views

complete the proof for this statement

$$\forall x \in \mathbb{R}, x \neq 0 \implies \frac{1}{x^2\:+3}\:<\:\frac{4}{5}\: $$ I thought of doing the contrapositive but not sure what to do next. $$ \frac{1}{x^{2\:}+3}\:\ge ...
-1
votes
0answers
33 views

Universum, interpretation few question.

i have few questin about predicate logic and interpretation : I have formula like this: 1) $(\forall x: \neg p(x) \vee q(x)) \Leftrightarrow \neg (p(x) \wedge q(x))$ No i must choose is either of ...
1
vote
3answers
65 views

Implies in a truth table, unclear. [duplicate]

In my textbook, we have the following truth table: $P$ true and $Q$ true means that "$P \implies Q$" is true. $P$ true and $Q$ false means that "$P \implies Q$" is false. $P$ false and $Q$ true ...
2
votes
1answer
45 views

define the “optimal” automatic theorem prover

my question is : is it possible to define in some way what should do an "optimal automatic mathematician" ? There are two points of view of an automatic theorem prover / automatic mathematician : ...