Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [discrete-mathematics]

The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

Discrete mathematics is not the name of a branch of mathematics, like number theory, algebra, calculus, etc. Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

The term "discrete mathematics" is therefore used in contrast with "continuous mathematics," which is the branch of mathematics dealing with objects that can vary smoothly (and which includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous objects require real numbers.

Though there cannot be a definite number of branches of Discrete Mathematics, the following topics are almost always covered in any study regarding this matter −

  • Sets, Relations and Functions
  • Mathematical Logic
  • Group theory
  • Counting Theory
  • Probability
  • Mathematical Induction and Recurrence Relations
  • Graph Theory
  • Trees
  • Boolean Algebra

For an overview, see the Wikipedia entry on Discrete mathematics.

and http://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf

Consider using a more specific tag instead, such as: , , , , , , , , etc.

32903 questions
1
vote
1 answer

fundamental theorem of arithmetic help

Show that $\sqrt{10}$ is irrational using the Fundamental theorem of arithmetic. I know I can prove it by way of contradiction. But I also want to know how to do this with this method. By contradiction, $\sqrt{10}$ is rational. Then we can write…
DezTop
  • 41
1
vote
1 answer

Element of, subset of and empty sets

I am trying to make sense of these. To me a is false because the set isn't empty. Is that correct? b is true because the empty set is an element of that set. c is false because the set the empty set isn't an element, it is a subset or proper…
Paul the Pirate
  • 1,566
1
vote
1 answer

Sum of factorials equation

Could you explain why constant $c \gt 0$ can't satisfy equation $c + \frac{c \cdot n!}{\varphi } \le 1$ , where $\varphi = \sum_{i=0}^{n-1}i!$, where $n \to \infty$
Machiaweliczny
  • 489
1
vote
1 answer

Proof by contradiction: If $x$ is a real number and $x^2 + x - 2 = 0$, then $x \neq 0$

Here's the problem again: Use a proof by contradiction to prove the following universal statement: If $x$ is a real number and $x^2 + x - 2 = 0$, then $x \neq 0$ Here's my attempt at it: Let $p$ be "$x^2 + x - 2 = 0$" and $q$ be "$x \neq…
Camille
  • 11
1
vote
2 answers

How to prove that if $X$ is a subset of $Y$ , and $X$ is infinite, then $Y$ is infinite

How do I prove this? Prove that if $X$ is a subset of $Y$ , and $X$ is infinite, then $Y$ is infinite. Thanks in advance.
Johan S
  • 203
1
vote
2 answers

Transition to advanced mathematics

I need help understanding the layout of proofs, I find myself lost after hours of trying to work it either if I know how the problem needs to be worked or not. I am taking probability and transition to advanced mathematics. I am struggling in both…
James
1
vote
1 answer

If c divides a, then prove cx divides ax.

I have a = ck for some integer k and ax = cxj for some integer j. I am not really sure where to go from here. If I put a into the second equation it would become ckx = cxj, and so the implication would only be true when k = j.
user2041391
  • 49
1
vote
2 answers

Proving equivalences of mod

I need to prove that $$(ab)\bmod m = \bigl((a \bmod m)(b \bmod m)\bigr)\bmod m,$$ but I don't know why the last "$\mathop{\bmod} m$" is there.
Emilio B.
  • 79
  • 5
1
vote
1 answer

Bijections, how to prove?

So I'm not sure how bijection and modularity are related, I know that bijection is one to one and onto. So my questions are; Is $f(x) \equiv x^{−1} \pmod{p}$ a bijection from $\{1,...,p−1\}$ to $\{1,...,p−1\}$? And how about $f(x) = x^2…
whatdidthefoxsay
  • 111
  • 1
  • 1
  • 7
1
vote
2 answers

Is $\{1, 2, 3\}\times \Bbb Z$ uncountable?

$\Bbb Z$ being the set of integers. My understanding is that a set is uncountable if it's greater than the set of $\Bbb N$. Might it be that I'm misunderstanding the question, and misinterpreting the '$\times$' which I'm currently interpreting as…
Ceelos
  • 375
1
vote
1 answer

Defining bijective function $f:\mathbb{N}\times\mathbb N\to\mathbb N$

I want to prove that $\mathbb N\times \mathbb N$ is countable set using cantor first diagonal method: where every-time we count the elemnts on the digonal with the direction of the arrow ($(1,1)\mapsto1,(2,1)\mapsto 2,(1,2)\mapsto3,(3,1)\mapsto4$…
user65985
1
vote
0 answers

How many ways students can take their bikes without the keeper having to use his own money to pay?

After school hours, all students will take their bikes and pay 1 dollar. Supposing that there are m students with 1-dollar bills, k students with 2-dollar bills (every student has either 1-dollar or 2-dollar, there is no one with both) and the…
Kii
  • 172
1
vote
3 answers

Proof of $\forall$ statement given interval notation.

I'm working on my discrete math homework, and I'm blanking on how to write a proof for a logical statement involving the quantifier $\forall$ The statement I need to prove is as follows: $\forall x\in \Bbb R,$ if $x \in [1,2],$ then $(3x-1) \in…
Hayden
  • 97
1
vote
1 answer

$A \cap B = A \cap (B' \cap A)'$ if both $A$ and $B$ are subsets of the universal set $U$.

$A ∩ B = A ∩ (B' ∩ A)'$ if $A,B ⊆ U$ (universal set) so to prove it I need to show that both sides are a subset of each other. I did the right side in the following steps: De Morrigan: $A ∩ (B' ∩ A)' = A ∩ (B'' ∪ A') $ Universal set laws: …
Abdallh Bder
  • 21
  • 5
1
vote
1 answer

Prove that $mn < 0$ if and only if exactly one of $m,n$ is positive

I need to prove that $mn < 0$ if and only if $m > 0$ and $n < 0$ or $m < 0$ and $n > 0$. So I need to prove two cases: 1. If $m < 0$ and $n > 0$ or, in the alternative, if $m > 0$ and $n < 0$, then $mn < 0$. 2. If $mn < 0$, then $m < 0$ and $n > 0$…
user92986
1 2 3
…
99 100