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)

1
vote
2answers
30 views

What to conclude from $ x \in (A \setminus B \cap B \setminus C)$

I have been working on one of the proof of logical statement and one part of it is like this: $ x \in (A \triangle B) \cap (B \triangle C)$ $ x \in (A \setminus B\cup B \setminus A) \cap (B ...
-2
votes
1answer
18 views

how i can prove $P\land T = P$ with english logic statements. and with out truth table. [on hold]

plz help me to solve. how i can prove $P\land T = P$ with english logic statements. and with out truth table.
2
votes
0answers
26 views

Need to check if these logic answers are correct =)

Are my answers true or wrong or not even wrong? Exercises says translate the following english sentences into symbolic sentences with quantifiers quantifiers the universe for each is given in ...
0
votes
1answer
23 views

Logical Reasoning [on hold]

John is 4 years older than Sarah. Mark and John are Irish twins, both born in January. The sum of Sarah’s age and Mark’s age is 69. Mark is older than John. How old are John, Sarah, and Mark? Assume ...
7
votes
3answers
216 views

Axiom of Choice: What exactly is a choice, and when and why is it needed?

I'm having trouble understanding the necessity of the Axiom of Choice. Given a set of non-empty subsets, what is the necessity of a function that picks out one element from each of those subsets? For ...
3
votes
0answers
52 views

A question regarding a paper of M. Magidor [on hold]

I am interested in the following paper of M. Magidor: "On the role of supercompact and extendible cardinals in logic", Israel Journal of Mathematics, 05/1971; 10(2): 147-157. The abstract (which I ...
3
votes
1answer
54 views

Would this be an acceptable translation of the English statement as well?

This is an except from my textbook (Discrete Mathematics and Its Applications 7th Edition) This was my initial stab at the problem (with domain of both variables being all real numbers) Would it ...
1
vote
1answer
23 views

Would these two statements be logically equivalent?

This is an excerpt from my textbook(Discrete Mathematics and Its Applications 7th edition) When I tried doing this example on my own, my answer was "There is a student x in this class and that ...
3
votes
0answers
34 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
5
votes
3answers
229 views

What is the first order axiom characterizing a field having characteristic zero?

In this thread on the axioms of $\mathbb Q$ it's stated that a field having characteristic zero can be written down in first-order logic. The definition in the logic lecture notes I work with (by ...
2
votes
1answer
49 views

Is this a correct solution to determine as to whom I should invite for the party?

I was working my way through some Propositional Logic Questions in Discrete Maths by Rosen, when I came across the following question: When planning a party you want to know whom to invite. Among ...
0
votes
1answer
39 views

A Model of Dense Linear Orders without Endpoints

Hopefully this question is well defined. Consider the following linear order in the language $\{<\}$: Step 0: Begin with $\mathbb{Q}$. Step 1: Create a new model $Q_1$ by realizing all the ...
4
votes
1answer
74 views

Logical proof gone wrong

I'm trying to establish a logical proof to the fact that the following statement is false: $2x+1$ is prime if and only if $x$ is prime. There are several ways to prove it of course, but I'm trying ...
0
votes
1answer
46 views

Does a statement being true for $n>N$, imply that varying a fixed number of parameters it will eventually hold anyway, at worst for $n>M>N$?

Let $a_n$ be a constant sequence and set $a'_n$ to differ only in a fixed number of elements, the first $m$ of them. Now suppose $P(n,a_1,\ldots,a_n)$ is true for sufficiently large $n$. Does this ...
1
vote
0answers
42 views

Diagonalization

So off and on I've been studying basic recursion theory and I've realized that, at least when restricted to the basic stuff I've been learning, recursion theory is essentially the study of uses of ...
1
vote
0answers
29 views

Confusion between categoricity and indiscernability

From wikipedia: Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Is this because ...
0
votes
1answer
44 views

Indiscernibility of indiscernibles in second order logic

It is not clear to me if the statements in $0^\#$ remain indiscernible when we move to second order logic. Or are there second logic formulas that can discriminate between first order indiscernibles?
27
votes
12answers
2k views

Why not both true and false?

Why can't some mathematical statement (or whatever is the correct term) be both true and false? For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive ...
-4
votes
0answers
42 views

Most predominant philosophical attitude toward mathematics [on hold]

What is the most predominant philosophical attitude toward mathematics among mathematicians? I am talking about things like mathematical platonism, formalism, logicism etc. In some circumstances I ...
4
votes
1answer
97 views

Is there any identity which cannot be proved

For example, if we want to prove that $a^2+b^2\ge 2ab$ for all $a,b\in\mathbb{R}$, we will start from something which is true (axiom or something that is already proved). In this case we will use fact ...
1
vote
3answers
85 views

Elementary embeddings vs isomorphisms

I'm trying to get a better handle on the concepts of literal embeddings, elementary embeddings and isomorphisms, as the show up in logic. This is the problem: It seems to me, (and is, according to my ...
0
votes
1answer
25 views

Which of the following conditions must necessarily be true?

Suppose that $\{A, B\}$ is a set of mutually exhaustive conditions, and that $\{C, D\}$ is another set of mutually exhaustive conditions. If the following implications are true: $$A \Longrightarrow ...
8
votes
1answer
90 views

Examples of Forcing in Model Theory

My question is exactly my title: What are some examples of (set theoretic) forcing in model theory? I have been studying (combinatorial) set theory and model theory (independently of one another) for ...
17
votes
3answers
948 views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
4
votes
1answer
54 views

Rewriting $X\leftrightarrow Y$ using only $\neg$ and $\lor$

Note: The book I'm using doesn't have any solutions/answers so I will be posting some of the questions I'm unsure about in the hope that someone will check it for me. Question: Re-write ...
2
votes
1answer
40 views

Statement calculus

Turn the statement 'either $X$ or $Y$' into an iterated composition. I'm not sure if my answer is correct, can someone please check for me? : $$\text{either }X\text{ or }Y \equiv (X\vee Y)\wedge ...
1
vote
1answer
37 views

o-minimal structures and definable functions

Consider the following definition of an o-minimal structure: An o-minimal structure $O=\{O_n\}$ is a sequence of Boolean algebras $O_n$ of subsets of $\mathbb{R}$ which satisfies the following ...
3
votes
2answers
106 views

A ⊆ B ∪ C -> x ∈ B or x ∈ C.

This is one of the problem I have been working from Velleman's How to Prove it book: Theorem: Suppose A, B, and C are sets and A ⊆ B ∪ C. Then either A ⊆ B or ...
1
vote
1answer
41 views

Proof in sequent calculus without cut

I met an exercise in Gaisi Takeuti, Proof Theory [Exercise 2.7, page 14]. How to construct a cut-free proof of$\ \forall xA(x)\rightarrow B\vdash \exists x(A(x)\rightarrow B)$, where A(a) and B are ...
3
votes
1answer
27 views

How to prove that predicate is expressible?

I have to prove, that predicate "x is transposition" in $S_5$ group. I can use such symbols, as *, 1, -1, =. However, I don't know any algorithm or way, which can ...
3
votes
2answers
39 views

Translate sentences in first-order logic

I need to translate the following sentence: "All mothers love their daughters". I thought: $\forall X \forall Y (mother(X) \wedge daughter(Y, X)) \Rightarrow love(X, Y)$ but on my book I found this ...
1
vote
1answer
46 views

Is this a correct solution to determining which of two people is the liar using one question?

I am a newbie to Stack-Exchange and if there is any problem in my question -- I apologize beforehand . I was working my way through some Propositional Logic Questions in Discrete Maths by Rosen , ...
4
votes
2answers
69 views

Logic - Prove the following

Here's the Problem: Which one of these is true? A) All of the below B) None of the below C) Some of the above D )None of the above E )None of the above My attempt: Suppose ...
1
vote
1answer
68 views

2 Questions regarding Relative Consistency Proofs

First Question: Let IC be the statement "There is an inaccessible cardinal." I have read that one cannot prove (in ZFC) the relative consistency of ZFC + IC w.r.t. ZFC. i.e. $ Con(ZFC) \rightarrow ...
3
votes
2answers
37 views

Establishing the validity of an argument.

I've been trying to determine the validity of a particular argument for some time now and I've had no luck in figuring it out. The argument in question goes as follows: \begin{align} & p \wedge q ...
4
votes
2answers
47 views

Proving or disproving $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$

Prove/disprove: $\{\{a\},b\}=\{\{c\},d\}\iff a=c \land b=d$ I know the LHS isn't like in the definition of ordered sets so it's probably false but I can't find any numbers as counter example, nor ...
1
vote
2answers
30 views

proof for propositional logic

I am unable to prove the following proposition logic. $(p \lor \neg r) \land (r \lor \neg p) \leftrightarrow (p \leftrightarrow q) \land (q \leftrightarrow r)$ My solution is given in the image. ...
1
vote
1answer
73 views

Existence of nonstandard elementary extensions of $PA$?

My question follows from the 1958 result of MacDowell–Specker (located originally in Modelle der Arithmetik, J. Symbolic Logic Volume 38, Issue 4 (1973), 651-652) of the proof of the following ...
1
vote
2answers
30 views

Can we ignore predicates in a statement if they aren't used?

Prove/disprove: $$\forall a>0:a\in\mathbb R: \exists N\in\mathbb R:\forall x\in \mathbb R:\exists z\in\mathbb R:\forall n\in \mathbb N:|n-99|<N\Rightarrow n>10 \vee \frac {n^2} 4 \le 25$$ ...
3
votes
0answers
74 views

Is this a valid proof for $1+1=2$? [duplicate]

I am extremely new to proofs, and quite bad at them. In studying and practicing the different types of proofs, I developed this very rough proof that $1+1=2$, one of the simplest mathematical truths I ...
1
vote
2answers
73 views

Clarification regarding Drinker's paradox [duplicate]

This is the informal proof of Drinker's paradox The proof begins by recognising it is true that either everyone in the pub is drinking (in this particular round of drinks), or at least one ...
2
votes
2answers
70 views

Infinite sets having no RE subsets

I'm back trying to learn recursion theory on my own. I'd like to prove the following result: There exists an infinite set having no infinite R.E. subset. Constructive comments are appreciated. Proof: ...
4
votes
0answers
81 views

Is there a logic to formalize the concept of “understanding”

The question may seem little bit weird given that philosophers have been struggling to have a full grasp on the concept of "understanding". But I'm wondering if there are any logics (modal-based or ...
2
votes
2answers
54 views

All Vatican anarchists are honest and dishonest at the same time if there is no anarchists in Vatican! How to resolve this contradiction? [duplicate]

Lets suppose we want to investigate proposition "All Vatican anarchists are honest". We can transform this proposition into implication "If a citizen of Vatican is an anarchist then he/she is honest". ...
0
votes
1answer
34 views

doppler effect… how does this image explain it? [closed]

http://www.wechselwild.com/sites/default/files/styles/detailseite/public/motif-images/2012-0/33/08/dopplereffekt_0.jpg?itok=RqqxSN-1 Yeah, I see this image everywhere when it's about the doppler ...
1
vote
2answers
41 views

when does $a\in\mathbb{R}$ does $\neg(a\leq 15\implies a>1)$ hold? [duplicate]

How can I formally write down for which $a\in\mathbb{R}$ the statement $\neg(a\leq 15\implies a>1)$ holds?
1
vote
4answers
77 views

Help with proposition whether it's true or false [closed]

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why?
0
votes
2answers
43 views

Simple rewrite of a question to mathematical form

Simple rewrite of a question For all real numbers x with $x^2-3 x+2\leq 0$, $1\leq x\leq 2$ I am trying to put this into a better form, Could someone give me feedback : stands for: "Such that" ...
1
vote
3answers
58 views

Extended Socratic Syllogisms?

I'm not entirely sure where I might ask this, but there is a logic tag, so I guess this fits the budget. I am taking an introductory course on logic, mainly revolving around Syllogisms, or a logical ...
2
votes
1answer
46 views

Flattening quantification over relations

I already asked this question in stack overflow here and somebody suggested to post it here. I repeat the question again: I have a Relation f defined as $f: A \to B × C$. I would like to write a ...